Python进阶_序列构成的数组

Posted on 2020-07-11 In Python Views:

Symbols count in article: 7.7k Reading time ≈ 7 mins.

《流畅的Python》笔记。

[TOC]

数据结构

序列构成的数组

容器序列：储存对象的引用，可以存放多种类型的数据。
扁平序列：储存值，只能存放一种类型的数据。
可变序列：list、bytearray、memoryview、…
不可变序列：tuple 、str、bytes

列表推导式

list comprehension (listcomps)

1	[ord(s) for s in words if ord(s) > 20]

在 []、{}、() 中，换行会被忽略。

也可以用 map filter 完成：

1	list(filter(lambda x:x > 20, map(ord, words)))

哪一个效率更高？

通过以下程序可以粗略估计，列表推导式效率更高。

import timeit
# Repeat time per test
TIMES = 10000

SETUP = """
symbols = '$¢£¥€¤'
def non_ascii(c):
    return c > 127
"""

def clock(label, cmd):
    res = timeit.repeat(cmd, setup=SETUP, number=TIMES)
    print(label, *('{:.3f}'.format(x) for x in res))

clock('listcomp        :', '[ord(s) for s in symbols if ord(s) > 127]')
clock('listcomp + func :', '[ord(s) for s in symbols if non_ascii(ord(s))]')
clock('filter + lambda :', 'list(filter(lambda c: c > 127, map(ord, symbols)))')
clock('filter + func   :', 'list(filter(non_ascii, map(ord, symbols)))')

输出：

listcomp        : 0.020 0.020 0.021 0.020 0.020
listcomp + func : 0.033 0.033 0.032 0.031 0.032
filter + lambda : 0.041 0.038 0.028 0.028 0.030
filter + func   : 0.033 0.039 0.026 0.028 0.026

生成器表达式

generator comprehension (gencomps)

生成器 generator，逐个产出元素，能够节省内存。方便初始化元组、数组等序列。

圆括号()，作为参数时省略

1 2	(ord(s) for s in words) print("{:2d}".format(a) for a in A)

元组拆包

元组重要的特点是“不可变”。

但是元组不仅储存了元素的信息，还储存了元素的位置信息，适合记录数据。

元组拆包 tuple unpacking：

平行赋值

1 2	lax_coordinates = (33.9425, -118.408056) latitude, longitude = lax_coordinates

* 拆包可迭代对象

1
2
3

t = (20, 8)
divmod(*t)
divmod(20, 8)

* 获取剩余元素

a, b, *rest = (1, 2, 3, 4)
>>> rest
[3, 4]
*rest, a, b = (1, 2, 3, 4)
>>> rest
[1, 2]

% 匹配元组元素

1
2
3

traveler_ids = [('USA', '31195855'), ('BRA', 'CE342567'), ('ESP', 'XDA205856')]
for passport in sorted(traveler_ids):
    print('%s/%s' % passport)

嵌套元组拆包

1	a, b, (c, d) = (1, 2, (3, 4))

关于占位符 _：很多时候是一个很好的占位符，但是在国际化软件里，_也是 gettext.gettext 的常用别名。

具名元组

collections.namedtuple：构建带字段名的元组和一个有名字的类。

用元组作为数据的记录，还少了字段的命名。因此使用具名元组。

1	card = collections.namedtuple('Card', ['rank', 'suit'])

具名元组还具有一些专有属性：

from collections import namedtuple 
City = namedtuple('City', "name country population coordinates")
tokyo = City('Tokyo', 'JP', 36.933, (35.689722, 139.691667))

>>> City._fields
('name', 'country', 'population', 'coordinates')

>>> tokyo_data = ('Tokyo', 'JP', 36.933, (35.689722, 139.691667))
>>> tokyo = City._make(tokyo_data)

>>> tokyo._asdict()
OrderedDict([('name', 'Tokyo'), ('country', 'JP'), ('population', 36.933), ('coordinates', (35.689722, 139.691667))])

_fields：字段名
_make(iter)：接受一个可迭代对象作为参数，构造具名元组
_asdict()：返回该实例的 collections.OrderedDict 形式。

序列切片

为什么切片会忽略最后一个元素？

1
2
3

a = [1,2,3,4]
>>> a[:3]
[1,2,3]

方便知道切片中有多少元素
快速计算切片长度（末尾 - 起始）
用一个下标分为两部分 [:a] [a:]

切片对象 slice object

从 a 到 b，以 c 为步长进行切片。

A[a:b:c]

1 2	a:b:c => slice(a, b, c) A[a:b:c] => A.__getitem__(slice(a, b, c))

多维切片

对于矩阵等二维数组，可以使用多维切片：

1	[m:n, k:l]

实质上是 __getitem__((m,n), (k,l))

省略号

1 2	>>> ... Ellipsis

1	a[i, ...] => a[i, :, :, :]

切片实质上是对于原来序列中一部分元素的引用，修改切片会修改原序列。

序列的+和*

初始化一个由列表组成的列表？

a = [[]] * 3
>>> a[1].append(3) 
>>> a
[[3], [3], [3]]

[[]] * n 实质上创建了 n 个指向同一个列表的引用。

该如何修改？

a = [[] for i in range(3)]
>>> a[1].append(3) 
>>> a
[[], [3], []]

每次迭代都产生了新的列表实例。

序列的增量赋值

1 2	a += b a *= b

实质上是 __iadd__ 和 __imul__ 方法在起作用，如果第一个操作对象不具有这两个方法，那么就会调用 __add__ 和 __mul__。

Attention_1

__iadd__ 和 __imul__ 不改变变量的地址，而调用 __add__ 和 __mul__ 实质上执行了：

1 2	a = a + b a = a * b

有一个赋值语句，将新的值赋给了新的对象，改变了 a 的地址。

Attention_2

1 2	>>> a = (1, 2, [3, 4]) >>> a[2] += [3, 4]

会发生什么？

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> a
(1, 2, [3, 4, 5, 6])

结果是既抛出了错误，又改变了不可变的元组！

查看字节码如下：

>>> dis.dis("a[2] += [5, 6]")
  1           0 LOAD_NAME                0 (a)
              2 LOAD_CONST               0 (2)
              4 DUP_TOP_TWO
              6 BINARY_SUBSCR
              8 LOAD_CONST               1 (5)
             10 LOAD_CONST               2 (6)
             12 BUILD_LIST               2
             14 INPLACE_ADD
             16 ROT_THREE
             18 STORE_SUBSCR
             20 LOAD_CONST               3 (None)
             22 RETURN_VALUE

STORE_SUBSCR: a[2] = TOS 赋值操作抛出错误。

`list.sort` 与 `sroted`

区别：list.sort 为原址排序，不产生新的列表对象，返回 None；而 sorted 返回新的排好序的列表。

连贯接口 fluent interface

参数：

reverse：默认为 False，若为 True 则降序输出
key：只有一个参数的函数，用于对序列中的每一个元素产生一个对比关键字。使用 str.lower 实现忽略大小写的排序，使用 len 实现根据字符串长度进行的排序……

算法使用的是 Timsort，会根据原始数据的顺序特点交替使用插入排序和归并排序。作者为 Tim Peters (Timbot)，也是 Python之禅的作者（import this）

`bisect` 操作已排好序的序列

bisect：二分，对半。

bisect、insort：利用二分查找算法在有序序列中查找或插入元素。

1
2
3

# 在 haystack（干草垛）种搜索 needle（针）的位置
# 参数 lo、hi 控制查找范围
bisect(haystack, needle)

结果满足：把 needle 插入该位置后，haystack 还能够保持升序，

import bisect
import sys

HAYSTACK = [1, 4, 5, 6, 8, 12, 15, 20, 21, 23, 23, 26, 29, 30]
NEEDLES = [0, 1, 2, 5, 8, 10, 22, 23, 29, 30, 31]

ROW_FMT = "{0:2d} @ {1:2d}    {2}{0:<2d}"

def demo(bisect_fn):
    for needle in reversed(NEEDLES):
        position = bisect_fn(HAYSTACK, needle)
        offset = position * "  |"
        print(ROW_FMT.format(needle, position, offset))

if __name__ == "__main__":
    if sys.argv[-1] == "left":
        bisect_fn = bisect.bisect_left
    else:
        bisect_fn = bisect.bisect
    
    print("DEMO:", bisect_fn.__name__)
    print("haystack ->", ' '.join("{:2d}".format(n) for n in HAYSTACK))
    demo(bisect_fn)

输出：

PS > python37 .\bisect_test.py   
DEMO: bisect_right
haystack ->  1  4  5  6  8 12 15 20 21 23 23 26 29 30
31 @ 14      |  |  |  |  |  |  |  |  |  |  |  |  |  |31
30 @ 14      |  |  |  |  |  |  |  |  |  |  |  |  |  |30
29 @ 13      |  |  |  |  |  |  |  |  |  |  |  |  |29
23 @ 11      |  |  |  |  |  |  |  |  |  |  |23
22 @  9      |  |  |  |  |  |  |  |  |22
10 @  5      |  |  |  |  |10
 8 @  5      |  |  |  |  |8
 5 @  3      |  |  |5
 2 @  1      |2
 1 @  1      |1
 0 @  0    0

PS n> python37 .\bisect_test.py left
DEMO: bisect_left
haystack ->  1  4  5  6  8 12 15 20 21 23 23 26 29 30
31 @ 14      |  |  |  |  |  |  |  |  |  |  |  |  |  |31
30 @ 13      |  |  |  |  |  |  |  |  |  |  |  |  |30
29 @ 12      |  |  |  |  |  |  |  |  |  |  |  |29
23 @  9      |  |  |  |  |  |  |  |  |23
22 @  9      |  |  |  |  |  |  |  |  |22
10 @  5      |  |  |  |  |10
 8 @  4      |  |  |  |8
 5 @  2      |  |5
 2 @  1      |2
 1 @  0    1
 0 @  0    0

还可以通过两个元素互相对应的有序列表，将一个列表中的值排序到对应的区间内 bisect_left，再获取另一个列表中的对应值。

1
2
3

def trans_grade(score, breakpoints=[60,70,80,90], grades="FDCBA"):
    i = bisect.bisect(breakpoints, score)
    return grades[i]

bisect 将返回分数对应的第 i 个分数段，通过分数段序号取对应等级。

bisect = bisect_right：所有的 haystack[:i] 都小于等于 needle

bisect_left：所有的 haystack[:i] 都小于 needle，也就是遇上了相等元素，新元素放在前面

Attention！

str.format，参数作为一个元组传入，format string 中的 {m:nX} 表示：取参数元组中的第 m 个，字段宽度为 n，按照数据类型 X 右对齐输出。

.join() 接受一个序列类型，或者一个序列生成器。

sys.argv 获取命令行参数。

列表不是首选时

列表背后存储的是 int、float 等对象，而数组 array 存储数字的字节表述。

如果需要频繁对序列进行先进先出操作，双端队列 deque 速度更快。

`array` 模块

1 2	# 根据类型码和初始值创建存储为字节码的数组 floats = array('d', (i for i in range(100)))

需要注意的是，array.tofile 和 array.fromfile 用起来简单且快速，比从文本读入快多了。因为后者会调用 float 方法将每一行文字转换为浮点数。并且写入二进制文件 *.bin 时，占用的空间更少。不过， python3.4 之后，数组不支持就地排序，需要用 sorted。

`memoryview`

内存视图。在不复制内容的情况下操作同一个数组的不同切片。处理大型数据集合时很重要。

# 创建 短整型有符号整数 数组 'h'
numbers = array.array('h', [-2, -1, 0, 1, 2])
# 获取 内存视图 memv
memv = memoryview(numbers)
# 将内存视图转换为 无符号字符 'B'
memv_oct = memv.cast('B')
# 以列表的形式查看 memv_oct
>>> memv_oct.tolist()
[254, 255, 255, 255, 0, 0, 1, 0, 2, 0]
# 修改第三个数字的低位字节码
memv_oct[5] = 4
# 改变了原数组
>>> numbers
array('h', [-2, -1, 1024, 1, 2])

‘h’ 占 2 个字节，’B’ 占 1 个字节，因此使用 memvoryview.cast('B') 时，每个短整型有符号数字被划分为高位 + 低位。例如：-2 的字节码划分为高位和低位就是 254、255。

`NumPy` 和 `SciPy`

另有笔记进行学习。

双端队列

普通列表通过 append 和 pop 模拟栈。

collections.deque 支持更快速、线程安全的队列类型。maxlen 参数指明队列容纳的元素个数。

rotate(n)：将队列的右侧（n>0）n个元素移动到左侧，反之移动到右侧。

>>> dq = collections.deque(range(10), maxlen = 10)
>>> dq
deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
>>> dq.rotate(3)
deque([7, 8, 9, 0, 1, 2, 3, 4, 5, 6], maxlen=10)
>>> dq.rotate(-4)
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 0], maxlen=10)

appendleft：左侧添加元素，若队列已满则删除最右侧元素。

1 2	>>> dq.appendleft(-1) deque([-1, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)

extend：将序列中的元素依次添加到右侧，挤出左侧元素。

1 2	>>> dq.extend([11,22,33]) deque([3, 4, 5, 6, 7, 8, 9, 11, 22, 33], maxlen=10)

extendleft：将序列中的元素依次添加到左侧，挤出右侧元素。

1 2	>>> dq.extendleft([44,55,66,77]) deque([77, 66, 55, 44, 3, 4, 5, 6, 7, 8], maxlen=10)

append 和 popleft 都是原子操作，也就说是 deque 可以在多线程程序中安全地当作先进先出的栈使用，而使用者不需要担心资源锁的问题。

其他队列

queue：同步类Queue、LifoQueue 和 PriorityQueue

multiproessing：进程通信用、JoinableQueue 用于任务管理

asyncio：包括前两者提供的 Queue，用于异步编程

heapq：堆队列、优先队列