第2章数据结构

ABC语言是Python的爸爸~

很多点子在现在看来都很有 Python 风格：序列的泛型操作、内置的元组和映射类型、用缩进来架构的源码、无需变量声明的强类型

不管是哪种数据结构，字符串、列表、字节序列、数组、XML 元素，抑或是数据库查询结果，它们都共用一套丰富的操作：迭代、切片、排序，还有拼接

2.1 内置序列类型概览

容器序列 container sequence
list、tuple 和 collections.deque 这些序列能存放不同类型的数据。
扁平序列 flat sequence
str、bytes、bytearray、memoryview 和 array.array，这类序列只能容纳一种类型；

在本书第二版拿掉了 bytearray、memoryview ，不过貌似都不咋用

除了collections、array你要import，其他都是builtins

容器序列存放的是它们所包含的任意类型的对象的引用，而扁平序列里存放的是值而不是引用。换句话说，扁平序列其实是一段连续的内存空间。由此可见扁平序列其实更加紧凑，但是它里面只能存放诸如字符、字节和数值这种基础类型

序列类型还能按照能否被修改来分类。
可变序列 mutable
list、bytearray、array.array、collections.deque 和 memoryview。
不可变序列 immutable
tuple、str 和 bytes。

MutableSequence继承Sequence继承Collection|Reversible

from collections import abc

print(issubclass(tuple, abc.Sequence)) # T

print(issubclass(list, abc.MutableSequence)) # T

内置的序列类型并不是直接从 Sequence 和MutableSequence 这两个抽象基类（Abstract Base Class，ABC）继承而来的

But they are virtual subclasses registered with those ABCs

列表（list）列表推导（list comprehension）生成器表达式（generator expression）

2.2 列表推导和生成器表达式

表推导（list comprehension）简写 listcomps

生成器表达式（generator expression）简写 genexps

2.2.1 列表推导和可读性

for循环写法

>>> symbols ='!@#$%'
>>> codes = []
>>> for symbol in symbols:
...     codes.append(ord(symbol))
...
>>> codes
[33, 64, 35, 36, 37]

列表推导式的写法

>>> symbols ='!@#$%'
>>> codes1 = [ord(symbol) for symbol in symbols]
>>> codes1
[33, 64, 35, 36, 37]

怎么选择呢?

通常的原则是，只用列表推导来创建新的列表，并且尽量保持简短

如果列表推导的代码超过了两行，你可能就要考虑是不是得用 for 循环重写了。

Python 会忽略代码里 []、{} 和 () 中的换行

如果你的代码里有多行的列表、列表推导、生成器表达式、字典这一类的，可以省略不太好看的续行符

比如这样完全是合法的

symbols = '!@#$%^'
codes = [ ord(symbol) for symbol in symbols
                       if symbol!='!']

列表推导可以帮助我们把一个序列或是其他可迭代类型中的元素过滤或是加工

Python 内置的 filter 和 map 函数组合起来也能达到这一效果，但是可读性上打了不小的折扣

2.2.2 列表推导同filter和map的比较

filter 和 map 合起来能做的事情，列表推导也可以做

比如上面的代码你可以用filter和map来完成

# 效果是类似的，先map再过滤，还是先过滤再map
codes1 = list(filter(lambda s:s!=ord('!'),map(ord,symbols)))
codes2 = list(map(ord,filter(lambda s:s!='!',symbols)))
print(codes1)
print(codes2)

2.2.3 笛卡尔积

用列表推导可以生成两个或以上的可迭代类型的笛卡儿积

示例代码

>>> colors = ['black', 'white']
>>> sizes = ['S', 'M', 'L']
>>> tshirts = [(color, size) for color in colors for size in sizes] ➊
>>> tshirts
[('black', 'S'), ('black', 'M'), ('black', 'L'), ('white', 'S'),
('white', 'M'), ('white', 'L')]

# 等价于 for 循环 
>>> for color in colors: ➋
... for size in sizes:
... print((color, size))
...
('black', 'S')
('black', 'M')
('black', 'L')
('white', 'S')
('white', 'M')
('white', 'L')

# 改变了size 和color的先后顺序 ， 注意看结果
>>> tshirts = [(color, size) for size in sizes ➌
... for color in colors]
>>> tshirts
[('black', 'S'), ('white', 'S'), ('black', 'M'), ('white', 'M'),
('black', 'L'), ('white', 'L')]

这种双重for不算难，应该都可以理解

说到底作者其实是在解释下面的这一行代码

self._cards = [Card(rank, suit) for suit in self.suits for rank in self.ranks]

列表推导的作用只有一个：生成列表。如果想生成其他类型的序列，生成器表达式就派上了用场。

2.2.4 生成器表达式

虽然也可以用列表推导来初始化元组、数组或其他序列类型，但是生成器表达式是更好的选择。这是因为生成器表达式背后遵守了迭代器协议，可以逐个地产出元素，而不是先建立一个完整的列表，然后再把这个列表传递到某个构造函数里。前面那种方式显然能够节省内存。

生成器表达式跟列表推导式直观的区别是从[]变成了()

示例代码

symbols = '!@#$%'
tuple(ord(symbol) for symbol in symbols)

实际上你应该这样看: temp = (ord(symbol) for symbol in symbols) 这才是中间产物，它是generator

>>> symbols = '!@#$%'
>>> tuple(ord(symbol) for symbol in symbols)
(33, 64, 35, 36, 37)

>>> temp = (ord(symbol) for symbol in symbols)
>>> type(temp)
<class 'generator'>
>>> tuple(temp)
(33, 64, 35, 36, 37)

如果生成器表达式是一个函数调用过程中的唯一参数，那么不需要额外再用括号把它围起来

作者给的例子，tuple(生成器表达式)和array.array(生成器表达式)其实都是Class的实例化过程，而非函数。

注意看下面的例子，你可能会感觉到生成器的好处

colors = ['black', 'white']
sizes = ['S', 'M', 'L']
# 下面是我加的
generator1 = ((c, s) for c in colors for s in sizes) # 这是个generator ， 常规我们可能会这么写
for i in generator1:
    print(i) # ('black', 'S')
generator = ('%s %s' % (c, s) for c in colors for s in sizes) # 再次格式化的做法可以借鉴
for i in generator:
    print(i) # 这样就格式化成了 black S
# 到这里是我加的
for tshirt in ('%s %s' % (c, s) for c in colors for s in sizes):
    print(tshirt)

这样做的好处是，过程中不需要生成一个列表来存储，generator的一个特点是每次 for 循环运行时才生成一个组合，内存里不会留下一个有 6 个组合的列表

>>> tshirts = [(color, size) for size in sizes ➌
... for color in colors]

2.3 元组不仅仅是不可变的列表

除了用作不可变的列表，它还可以用于没有字段名的记录

多数刚入门的用到元素，多是用的第一个特性

2.3.1 元组和记录

元组其实是对数据的记录：元组中的每个元素都存放了记录中一个字段的数据，外加这个字段的位置。正是这个位置信息给数据赋予了意义

改变位置(索引)，即打乱顺序会让元组失去意义

元组作为记录的例子

>>> lax_coordinates = (33.9425, -118.408056) ➊
>>> city, year, pop, chg, area = ('Tokyo', 2003, 32450, 0.66, 8014) ➋

继续

traveler_ids = [('USA', '31195855'), ('BRA', 'CE342567'), ('ESP', 'XDA205856')]
for passport in traveler_ids:
    print(passport)  #  ('USA', '31195855') # 原始数据
    print('%s/%s' %passport) # USA/31195855 # 可以进行格式化

for country,_ in traveler_ids:  # 丢弃部分
    print(country) # USA

for 循环可以分别提取元组里的元素，也叫作拆包（unpacking）

拆包让元组可以完美地被当作记录来使用

2.3.2 元组拆包 unpacking

city, year, pop, chg, area = ('Tokyo', 2003, 32450, 0.66, 8014) 这是拆包

for passport in traveler_ids:
    print('%s/%s' %passport)

上面也是拆包的应用

元组拆包可以应用到任何可迭代对象上

可迭代元素拆包 PEP 3132—Extended Iterable Unpacking”（https://www.python.org/dev/peps/pep-3132

元组拆包的一些例子

>>> lax_coordinates = (33.9425, -118.408056)
>>> latitude, longitude = lax_coordinates # 元组拆包

>>> b, a = a, b

>>> import os
>>> _, filename = os.path.split('/home/luciano/.ssh/idrsa.pub') # _ 是 '/home/luciano/.ssh'
>>> filename
'idrsa.pub'

_是用来做占位符的

用*来拆包一个可迭代对象作为函数参数的例子

>>> divmod(20, 8)
(2, 4)
>>> t = (20, 8)
>>> divmod(*t)
(2, 4)
>>> quotient, remainder = divmod(*t)
>>> quotient, remainder
(2, 4)

函数用 *args 来获取不确定数量的参数算是一种经典写法

于是 Python 3 里，这个概念被扩展到了平行赋值中

# 多
>>> a, b, *rest = range(5)
>>> a, b, rest
(0, 1, [2, 3, 4])
# 正好，但注意，也是[]
>>> a, b, *rest = range(3)
>>> a, b, rest
(0, 1, [2])
# 少 也没关系
>>> a, b, *rest = range(2)
>>> a, b, rest
(0, 1, [])

在平行赋值中，* 前缀只能用在一个变量名前面，但是这个变量可以出现在赋值表达式的任意位置：

>>> a, *body, c, d = range(5)
>>> a, body, c, d
(0, [1, 2], 3, 4)
>>> *head, b, c, d = range(5)
>>> head, b, c, d
([0, 1], 2, 3, 4)

2.3.3 嵌套元组拆包

没啥特别的，就是匹配结构，核心代码是for name, cc, pop, (latitude, longitude) in metro_areas

这个结构契合('Tokyo','JP',36.933,(35.689722,139.691667))

metro_areas = [
('Tokyo','JP',36.933,(35.689722,139.691667)), # ➊
('Delhi NCR', 'IN', 21.935, (28.613889, 77.208889)),
('Mexico City', 'MX', 20.142, (19.433333, -99.133333)),
('New York-Newark', 'US', 20.104, (40.808611, -74.020386)),
('Sao Paulo', 'BR', 19.649, (-23.547778, -46.635833)),
]
print('{:15} | {:^9} | {:^9}'.format('', 'lat.', 'long.'))
fmt = '{:15} | {:9.4f} | {:9.4f}'
for name, cc, pop, (latitude, longitude) in metro_areas: # ➋
    if longitude <= 0: # ➌
    	print(fmt.format(name, latitude, longitude))

元组已经设计得很好用了，但作为记录来用的话，还是少了一个功能：我们时常会需要给记录中的字段命名

2.3.4 具名元组

collections.namedtuple 是一个工厂函数，它可以用来构建一个带字段名的元组和一个有名字的类

用 namedtuple 构建的类的实例所消耗的内存跟元组是一样的

示例代码

>>> from collections import namedtuple
>>> City = namedtuple('City', 'name country population coordinates') ➊
>>> tokyo = City('Tokyo', 'JP', 36.933, (35.689722, 139.691667)) ➋
>>> tokyo
City(name='Tokyo', country='JP', population=36.933, coordinates=(35.689722,
139.691667))
>>> tokyo.population ➌
36.933
>>> tokyo.coordinates
(35.689722, 139.691667)
>>> tokyo[1]
'JP'

注意

City = namedtuple('City', 'name country population coordinates')构建的类名是=号左侧的变量名决定的，一般我们都与namedtuple的第一个参数保持一致，其实可以不一致
作为namedtuple，你可以像元组一样去使用，如下标法tokyo[1]；也可以用.field的方式来使用，如tokyo.coordinates

具名元组还要一些特性

from collections import namedtuple

City = namedtuple('City', 'name country population')
print(City._fields)
nanjing_info = 'nanjing','china','2100'
nanjing = City._make(nanjing_info) # 等价于 nanjing = City('nanjing','china','2100')
print(nanjing._asdict())

➊ _fields 属性是一个包含这个类所有字段名称的元组。
➋ 用 _make() 通过接受一个可迭代对象来生成这个类的一个实例，它的作用跟City(*nanjing_info) 是一样的。
➌ _asdict() 把具名元组以 collections.OrderedDict 的形式返回，我们可以利用它来把元组里的信息友好地呈现出来

2.3.5 作为不可变列表的元组

除了跟增减元素相关的方法之外，元组支持列表的其他所有方法。还有一个例外，元组没有 reversed 方法

示例	列表	元组	说明
`s.__add__(s2)`	√	√	s + s2，拼接
`s.__iadd__(s2)`	√		s += s2，就地拼接
s.append(e)	√		在尾部添加一个新元素
s.clear()	√		删除所有元素
`s.__contains__(e)`	√	√	s 是否包含 e
s.copy()	√		列表的浅复制
s.count(e)	√		e 在 s 中出现的次数
`s.__delitem__(p)`	√		把位于 p 的元素删除
s.extend(it)	√		把可迭代对象 it 追加给 s
`s.__getitem__(p)`	√	√	s[p]，获取位置 p 的元素
`s.__getnewargs__()`		√	在 pickle 中支持更加优化的序列化
s.index(e)	√	√	在 s 中找到元素 e 第一次出现的位置
s.insert(p, e)	√		在位置 p 之前插入元素 e
`s.__iter__()`	√	√	获取 s 的迭代器
`s.__len__()`	√	√	len(s)，元素的数量
`s.__mul__(n)`	√	√	s * n，n 个 s 的重复拼接
`s.__imul__(n)`	√		s *= n，就地重复拼接
`s.__rmul__(n)`	√	√	n * s，反向拼接 *
s.pop([p])	√		删除最后或者是（可选的）位于 p 的元素，并返回它的值
s.remove(e)	√		删除 s 中的第一次出现的 e
s.reverse()	√		就地把 s 的元素倒序排列
`s.__reversed__()`	√		返回 s 的倒序迭代器
`s.__setitem__(p, e)`	√		s[p] = e，把元素 e 放在位置 p，替代已经在那个位置的元素
s.sort([key], [reverse])	√		就地对 s 中的元素进行排序，可选的参数有键（key）和是否倒序（reverse）

2.4 切片

2.4.1 为什么切片和区间会忽略最后一个元素

在切片和区间操作里不包含区间范围的最后一个元素是 Python 的风格，这个习惯符合Python、C 和其他语言里以 0 作为起始下标的传统

zero-based index和 one-based index

这样设计的好处是

当只有最后一个位置信息时，我们也可以快速看出切片和区间里有几个元素：range(3)序列构成的数组和 my_list[:3] 都返回 3 个元素。

当起止位置信息都可见时，我们可以快速计算出切片和区间的长度，用后一个数减去第一个下标（stop - start）即可。

这样做也让我们可以利用任意一个下标来把序列分割成不重叠的两部分，只要写成 my_list[:x] 和 my_list[x:] 就可以了

https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html

计算机科学家 Edsger W. Dijkstra 对这一风格的解释应该是最好的

2.4.2 对对象进行切片

用 s[a:B:c] 的形式对 s 在 a 和 B之间以 c 为间隔取值。c 的值还可以为负，负值意味着反向取值

>>> s = 'bicycle'
>>> s[::3]
'bye'
>>> s[::-1]
'elcycib'
>>> s[::-2]
'eccb'

不错的例子是

>>> deck[12::13]
[Card(rank='A', suit='spades'), Card(rank='A', suit='diamonds'),
Card(rank='A', suit='clubs'), Card(rank='A', suit='hearts')]

对 seq[start:stop:step] 进行求值的时候，Python 会调用 seq.__getitem__(slice(start, stop, step))

nums = [1,3,5,7,9,11]
print((nums[2:5:2])) # [5, 9]
print(nums.__getitem__(slice(2,5,2))) # [5, 9]

再看个例子

invoice = """
0.....6................................40..........52...55........
1909  Pimoroni      PiBrella             $17.50     3    $52.50
1489  6mm Tactile Switch x20             $4.95      2    $9.90
1510  Panavise Jr. - PV-201              $28.00     1    $28.00
1601  PiTFT Mini Kit 320x240             $34.95     1    $34.95
"""
SKU = slice(0, 6)
DESCRIPTION = slice(6, 40)
UNIT_PRICE = slice(40, 52)
QUANTITY = slice(52, 55)
ITEM_TOTAL = slice(55, None)
line_items = invoice.split('\n')[2:]
for item in line_items:
    print(item[UNIT_PRICE], item[DESCRIPTION])

好家伙，这个invoice是一段格式化后的文本，可以理解为一份单据

格式化是比较严格的，要跟下文的slice严格对应

个人感觉这么做的意义不是很大吧，完全有更好的做法，可以理解为slice的一个应用吧。

2.4.3 多维切片和省略号

省略（ellipsis）的正确书写方法是三个英语句号（...），而不是 Unicdoe 码位 U+2026 表示的半个省略号（...）。省略在 Python 解析器眼里是一个符号，而实际上它是 Ellipsis 对象的别名，而 Ellipsis 对象又是 ellipsis 类的单一实例

解释下，下面的代码输出的id是一样的

a = Ellipsis
b = Ellipsis
c = ...
print(id(a))
print(id(b))
print(id(c))

2.4.4 给切片赋值

如果把切片放在赋值语句的左边，或把它作为 del 操作的对象，我们就可以对序列进行嫁接、切除或就地修改操作

看书中的例子

>>> l = list(range(10))
>>> l
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> l[2:5] = [20, 30] # 就地修改
>>> l
[0, 1, 20, 30, 5, 6, 7, 8, 9]
>>> del l[5:7] # 就地删除
>>> l
[0, 1, 20, 30, 5, 8, 9]
>>> l[3::2] = [11, 22] # 还是修改，竟然可以跳跃
>>> l
[0, 1, 20, 11, 5, 22, 9]
>>> l[2:5] = 100 ➊ # 即便你用的是l[2:3] 也不能用100
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: can only assign an iterable
>>> l[2:5] = [100]
>>> l
[0, 1, 100, 22, 9]