第 2 章 序列构成的数组

第 2 章 序列构成的数组

你可能注意到了,之前提到的几个操作可以无差别地应用于文本、列表和表格上。我们把文本、列表和表格叫作数据火车……FOR 命令通常能作用于数据火车上。1

——Geurts、Meertens 和 Pemberton
ABC Programmer's Handbook

1Leo Geurts, Lambert Meertens, and Steven Pemberton, ABC Programmer's Handbook, p. 8.

在创造 Python 以前,Guido 曾为 ABC 语言贡献过代码。ABC 语言是一个致力于为初学者设计编程环境的长达 10 年的研究项目,其中很多点子在现在看来都很有 Python 风格:序列的泛型操作、内置的元组和映射类型、用缩进来架构的源码、无需变量声明的强类型,等等。Python 对开发者如此友好,根源就在这里。

Python 也从 ABC 那里继承了用统一的风格去处理序列数据这一特点。不管是哪种数据结构,字符串、列表、字节序列、数组、XML 元素,抑或是数据库查询结果,它们都共用一套丰富的操作:迭代、切片、排序,还有拼接。

深入理解 Python 中的不同序列类型,不但能让我们避免重新发明轮子,它们的 API 还能帮助我们把自己定义的 API 设计得跟原生的序列一样,或者是跟未来可能出现的序列类型保持兼容。

本章讨论的内容几乎可以应用到所有的序列类型上,从我们熟悉的 list,到 Python 3 中特有的 strbytes。我还会特别提到跟列表、元组、数组以及队列有关的话题。但是 Unicode 字符串和字节序列这方面的内容被放在了第 4 章。另外这里讨论的数据结构都是 Python 中现成可用的,如果你想知道怎样创建自己的序列类型,那得等到第 10 章。

2.1 内置序列类型概览

Python 标准库用 C 实现了丰富的序列类型,列举如下。

容器序列

  listtuplecollections.deque 这些序列能存放不同类型的数据。

扁平序列

  strbytesbytearraymemoryviewarray.array,这类序列只能容纳一种类型。

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

序列类型还能按照能否被修改来分类。

可变序列

  listbytearrayarray.arraycollections.dequememoryview

不可变序列

  tuplestrbytes

图 2-1 显示了可变序列(MutableSequence)和不可变序列(Sequence)的差异,同时也能看出前者从后者那里继承了一些方法。虽然内置的序列类型并不是直接从 SequenceMutableSequence 这两个抽象基类(Abstract Base Class,ABC)继承而来的,但是了解这些基类可以帮助我们总结出那些完整的序列类型包含了哪些功能。

{%}

图 2-1:这个 UML 类图列举了 collections.abc 中的几个类(超类在左边,箭头从子类指向超类,斜体名称代表抽象类和抽象方法)

通过记住这些类的共有特性,把可变与不可变序列或是容器与扁平序列的概念融会贯通,在探索并学习新的序列类型时,你会更加得心应手。

最重要也最基础的序列类型应该就是列表(list)了。list 是一个可变序列,并且能同时存放不同类型的元素。作为这本书的读者,我想你应该对它很了解了,因此让我们直接开始讨论列表推导(list comprehension)吧。列表推导是一种构建列表的方法,它异常强大,然而由于相关的句法比较晦涩,人们往往不愿意去用它。掌握列表推导还可以为我们打开生成器表达式(generator expression)的大门,后者具有生成各种类型的元素并用它们来填充序列的功能。下一节就来看看这两个概念。

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

列表推导是构建列表(list)的快捷方式,而生成器表达式则可以用来创建其他任何类型的序列。如果你的代码里并不经常使用它们,那么很可能你错过了许多写出可读性更好且更高效的代码的机会。

如果你对我说的“更具可读性”持怀疑态度的话,别急着下结论,我马上就能说服你。

 很多 Python 程序员都把列表推导(list comprehension)简称为 listcomps,生成器表达式(generator expression)则称为 genexps。我有时也会这么用。

2.2.1 列表推导和可读性

先来个小测试,你觉得示例 2-1 和示例 2-2 中的代码,哪个更容易读懂?

示例 2-1 把一个字符串变成 Unicode 码位的列表

>>> symbols = '$¢£¥€¤'
>>> codes = []
>>> for symbol in symbols:
...     codes.append(ord(symbol))
...
>>> codes
[36, 162, 163, 165, 8364, 164]

示例 2-2 把字符串变成 Unicode 码位的另外一种写法

>>> symbols = '$¢£¥€¤'
>>> codes = [ord(symbol) for symbol in symbols]
>>> codes
[36, 162, 163, 165, 8364, 164]

虽说任何学过一点 Python 的人应该都能看懂示例 2-1,但是我觉得如果学会了列表推导的话,示例 2-2 读起来更方便,因为这段代码的功能从字面上就能轻松地看出来。

for 循环可以胜任很多任务:遍历一个序列以求得总数或挑出某个特定的元素、用来计算总和或是平均数,还有其他任何你想做的事情。在示例 2-1 的代码里,它被用来新建一个列表。

另一方面,列表推导也可能被滥用。以前看到过有的 Python 代码用列表推导来重复获取一个函数的副作用。通常的原则是,只用列表推导来创建新的列表,并且尽量保持简短。如果列表推导的代码超过了两行,你可能就要考虑是不是得用 for 循环重写了。就跟写文章一样,并没有什么硬性的规则,这个度得你自己把握。

 句法提示

Python 会忽略代码里 []{}() 中的换行,因此如果你的代码里有多行的列表、列表推导、生成器表达式、字典这一类的,可以省略不太好看的续行符 \

 

列表推导不会再有变量泄漏的问题

Python 2.x 中,在列表推导中 for 关键词之后的赋值操作可能会影响列表推导上下文中的同名变量。像下面这个 Python 2.7 控制台对话:

Python 2.7.6 (default, Mar 22 2014, 22:59:38)
[GCC 4.8.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> x = 'my precious'
>>> dummy = [x for x in 'ABC']
>>> x
'C'

如你所见,x 原本的值被取代了,但是这种情况在 Python 3 中是不会出现的。

列表推导、生成器表达式,以及同它们很相似的集合(set)推导和字典(dict)推导,在 Python 3 中都有了自己的局部作用域,就像函数似的。表达式内部的变量和赋值只在局部起作用,表达式的上下文里的同名变量还可以被正常引用,局部变量并不会影响到它们。

这是Python 3 代码:

>>> x = 'ABC'
>>> dummy = [ord(x) for x in x]
>>> x ➊
'ABC'
>>> dummy ➋
[65, 66, 67]
>>>

x 的值被保留了。

➋ 列表推导也创建了正确的列表。

列表推导可以帮助我们把一个序列或是其他可迭代类型中的元素过滤或是加工,然后再新建一个列表。Python 内置的 filtermap 函数组合起来也能达到这一效果,但是可读性上打了不小的折扣。

2.2.2 列表推导同filtermap的比较

filtermap 合起来能做的事情,列表推导也可以做,而且还不需要借助难以理解和阅读的 lambda 表达式。详见示例 2-3。

示例 2-3 用列表推导和 map/filter 组合来创建同样的表单

>>> symbols = '$¢£¥€¤'
>>> beyond_ascii = [ord(s) for s in symbols if ord(s) > 127]
>>> beyond_ascii
[162, 163, 165, 8364, 164]
>>> beyond_ascii = list(filter(lambda c: c > 127, map(ord, symbols)))
>>> beyond_ascii
[162, 163, 165, 8364, 164]

我原以为 map/filter 组合起来用要比列表推导快一些,Alex Martelli 却说不一定——至少在上面这个例子中不一定。在本书的代码仓库中有名为 02-array-seq/listcomp_speed.py的脚本,代码中有这两个方法的效率的比较。

第 5 章会更详细地讨论 mapfilter。下面就来看看如何用列表推导来计算笛卡儿积:两个或以上的列表中的元素对构成元组,这些元组构成的列表就是笛卡儿积。

2.2.3 笛卡儿积

如前所述,用列表推导可以生成两个或以上的可迭代类型的笛卡儿积。笛卡儿积是一个列表,列表里的元素是由输入的可迭代类型的元素对构成的元组,因此笛卡儿积列表的长度等于输入变量的长度的乘积,如图 2-2 所示。

{%}

图 2-2:含有 4 种花色和 3 种牌面的列表的笛卡儿积,结果是一个包含 12 个元素的列表

如果你需要一个列表,列表里是 3 种不同尺寸的 T 恤衫,每个尺寸都有 2 个颜色,示例 2-4 用列表推导算出了这个列表,列表里有 6 种组合。

示例 2-4 使用列表推导计算笛卡儿积

>>> 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 color in colors: ➋
...     for size in sizes:
...         print((color, size))
...
('black', 'S')
('black', 'M')
('black', 'L')
('white', 'S')
('white', 'M')
('white', 'L')
>>> 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 从句的先后顺序一样。

➌ 如果想依照先尺码后颜色的顺序来排列,只需要调整从句的顺序。我在这里插入了一个换行符,这样顺序安排就更明显了。

在第 1 章的示例 1-1 中,有下面这样一段程序,它的作用是生成一个按花色分组的 52 张牌的列表,其中每个花色各有 13 张不同点数的牌。

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

列表推导的作用只有一个:生成列表。如果想生成其他类型的序列,生成器表达式就派上了用场。下一节就是对生成器表达式的一个简单介绍,其中可以看到如何用它生成列表以外的序列类型。

2.2.4 生成器表达式

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

生成器表达式的语法跟列表推导差不多,只不过把方括号换成圆括号而已。

示例 2-5 展示了如何用生成器表达式建立元组和数组。

示例 2-5 用生成器表达式初始化元组和数组

>>> symbols = '$¢£¥€¤'
>>> tuple(ord(symbol) for symbol in symbols) ➊
(36, 162, 163, 165, 8364, 164)
>>> import array
>>> array.array('I', (ord(symbol) for symbol in symbols)) ➋
array('I', [36, 162, 163, 165, 8364, 164])

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

array 的构造方法需要两个参数,因此括号是必需的。array 构造方法的第一个参数指定了数组中数字的存储方式。2.9.1 节中有更多关于数组的详细讨论。

示例 2-6 则是利用生成器表达式实现了一个笛卡儿积,用以打印出上文中我们提到过的 T 恤衫的 2 种颜色和 3 种尺码的所有组合。与示例 2-4 不同的是,用到生成器表达式之后,内存里不会留下一个有 6 个组合的列表,因为生成器表达式会在每次 for 循环运行时才生成一个组合。如果要计算两个各有 1000 个元素的列表的笛卡儿积,生成器表达式就可以帮忙省掉运行 for 循环的开销,即一个含有 100 万个元素的列表。

示例 2-6 使用生成器表达式计算笛卡儿积

>>> colors = ['black', 'white']
>>> sizes = ['S', 'M', 'L']
>>> for tshirt in ('%s %s' % (c, s) for c in colors for s in sizes): ➊
...     print(tshirt)
...
black S
black M
black L
white S
white M
white L

➊ 生成器表达式逐个产出元素,从来不会一次性产出一个含有 6 个 T 恤样式的列表。

第 14 章会专门讲到生成器的工作原理。这里只是简单看看如何用生成器来初始化除列表之外的序列,以及如何用它来避免额外的内存占用。

接下来看看 Python 中的另外一个很重要的序列类型:元组(tuple)。

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

有些 Python 入门教程把元组称为“不可变列表”,然而这并没有完全概括元组的特点。除了用作不可变的列表,它还可以用于没有字段名的记录。鉴于后者常常被忽略,我们先来看看元组作为记录的功用。

2.3.1 元组和记录

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

如果只把元组理解为不可变的列表,那其他信息——它所含有的元素的总数和它们的位置——似乎就变得可有可无。但是如果把元组当作一些字段的集合,那么数量和位置信息就变得非常重要了。

示例 2-7 中的元组就被当作记录加以利用。如果在任何的表达式里我们在元组内对元素排序,这些元素所携带的信息就会丢失,因为这些信息是跟它们的位置有关的。

示例 2-7 把元组用作记录

>>> 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 sorted(traveler_ids):  ➍
...     print('%s/%s' % passport) ➎
...
BRA/CE342567
ESP/XDA205856
USA/31195855
>>> for country, _ in traveler_ids:  ➏
...     print(country)
...
USA
BRA
ESP

❶ 洛杉矶国际机场的经纬度。

❷ 东京市的一些信息:市名、年份、人口(单位:百万)、人口变化(单位:百分比)和面积(单位:平方千米)。

❸ 一个元组列表,元组的形式为 (country_code, passport_number)

❹ 在迭代的过程中,passport 变量被绑定到每个元组上。

% 格式运算符能被匹配到对应的元组元素上。

for 循环可以分别提取元组里的元素,也叫作拆包(unpacking)。因为元组中第二个元素对我们没有什么用,所以它赋值给“_”占位符。

拆包让元组可以完美地被当作记录来使用,这也是下一节的话题。

2.3.2 元组拆包

示例 2-7 中,我们把元组 ('Tokyo', 2003, 32450, 0.66, 8014) 里的元素分别赋值给变量 cityyearpopchgarea,而这所有的赋值我们只用一行声明就写完了。同样,在后面一行中,一个 % 运算符就把 passport 元组里的元素对应到了 print 函数的格式字符串空档中。这两个都是对元组拆包的应用。

 元组拆包可以应用到任何可迭代对象上,唯一的硬性要求是,被可迭代对象中的元素数量必须要跟接受这些元素的元组的空档数一致。除非我们用 * 来表示忽略多余的元素,在“用 * 来处理多余的元素”一节里,我会讲到它的具体用法。Python 爱好者们很喜欢用元组拆包这个说法,但是可迭代元素拆包这个表达也慢慢流行了起来,比如“PEP 3132—Extended Iterable Unpacking”的标题就是这么用的。

最好辨认的元组拆包形式就是平行赋值,也就是说把一个可迭代对象里的元素,一并赋值到由对应的变量组成的元组中。就像下面这段代码:

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

另外一个很优雅的写法当属不使用中间变量交换两个变量的值:

>>> b, a = a, b

还可以用 * 运算符把一个可迭代对象拆开作为函数的参数:

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

下面是另一个例子,这里元组拆包的用法则是让一个函数可以用元组的形式返回多个值,然后调用函数的代码就能轻松地接受这些返回值。比如 os.path.split() 函数就会返回以路径和最后一个文件名组成的元组 (path, last_part):

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

在进行拆包的时候,我们不总是对元组里所有的数据都感兴趣,_ 占位符能帮助处理这种情况,上面这段代码也展示了它的用法。

 如果做的是国际化软件,那么 _ 可能就不是一个理想的占位符,因为它也是 gettext.gettext 函数的常用别名,gettext 模块的文档里提到了这一点。在其他情况下,_ 会是一个很好的占位符。

除此之外,在元组拆包中使用 * 也可以帮助我们把注意力集中在元组的部分元素上。

*来处理剩下的元素

在 Python 中,函数用 *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 嵌套元组拆包

接受表达式的元组可以是嵌套式的,例如 (a, b, (c, d))。只要这个接受元组的嵌套结构符合表达式本身的嵌套结构,Python 就可以作出正确的对应。示例 2-8 就是对嵌套元组拆包的应用。

示例 2-8 用嵌套元组来获取经度

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))

❶ 每个元组内有 4 个元素,其中最后一个元素是一对坐标。

❷ 我们把输入元组的最后一个元素拆包到由变量构成的元组里,这样就获取了坐标。

if longitude <= 0: 这个条件判断把输出限制在西半球的城市。

示例 2-8 的输出是这样的:

                |   lat.    |   long.
Mexico City     |   19.4333 |  -99.1333
New York-Newark |   40.8086 |  -74.0204
Sao Paul        |  -23.5478 |  -46.6358

 在 Python 3 之前,元组可以作为形参放在函数声明中,例如 def fn(a, (b, c), d):。然而 Python 3 不再支持这种格式,具体原因见于“PEP 3113—Removal of Tuple Parameter Unpacking”。需要弄清楚的是,这个改变对函数调用者并没有影响,它改变的是某些函数的声明方式。

元组已经设计得很好用了,但作为记录来用的话,还是少了一个功能:我们时常会需要给记录中的字段命名。namedtuple 函数的出现帮我们解决了这个问题。

2.3.4 具名元组

collections.namedtuple 是一个工厂函数,它可以用来构建一个带字段名的元组和一个有名字的类——这个带名字的类对调试程序有很大帮助。

 用 namedtuple 构建的类的实例所消耗的内存跟元组是一样的,因为字段名都被存在对应的类里面。这个实例跟普通的对象实例比起来也要小一些,因为 Python 不会用 __dict__ 来存放这些实例的属性。

在第 1 章的示例 1-1 中是这样新建 Card 类的:

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

示例 2-9 展示了如何用具名元组来记录一个城市的信息。

示例 2-9 定义和使用具名元组

>>> 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'

❶ 创建一个具名元组需要两个参数,一个是类名,另一个是类的各个字段的名字。后者可以是由数个字符串组成的可迭代对象,或者是由空格分隔开的字段名组成的字符串。

❷ 存放在对应字段里的数据要以一串参数的形式传入到构造函数中(注意,元组的构造函数却只接受单一的可迭代对象)。

❸ 你可以通过字段名或者位置来获取一个字段的信息。

除了从普通元组那里继承来的属性之外,具名元组还有一些自己专有的属性。示例 2-10 中就展示了几个最有用的:_fields 类属性、类方法 _make(iterable) 和实例方法 _asdict()

示例 2-10 具名元组的属性和方法(接续前一个示例)

>>> City._fields  ➊
('name', 'country', 'population', 'coordinates')
>>> LatLong = namedtuple('LatLong', 'lat long')
>>> delhi_data = ('Delhi NCR', 'IN', 21.935, LatLong(28.613889, 77.208889))
>>> delhi = City._make(delhi_data)  ➋
>>> delhi._asdict()  ➌
OrderedDict([('name', 'Delhi NCR'), ('country', 'IN'), ('population',
21.935), ('coordinates', LatLong(lat=28.613889, long=77.208889))])
>>> for key, value in delhi._asdict().items():
        print(key + ':', value)

name: Delhi NCR
country: IN
population: 21.935
coordinates: LatLong(lat=28.613889, long=77.208889)
>>>

_fields 属性是一个包含这个类所有字段名称的元组。

❷ 用 _make() 通过接受一个可迭代对象来生成这个类的一个实例,它的作用跟 City(*delhi_data) 是一样的。

_asdict() 把具名元组以 collections.OrderedDict 的形式返回,我们可以利用它来把元组里的信息友好地呈现出来。

现在我们知道了,元组是一种很强大的可以当作记录来用的数据类型。它的第二个角色则是充当一个不可变的列表。下面就来看看它的第二重功能。

2.3.5 作为不可变列表的元组

如果要把元组当作列表来用的话,最好先了解一下它们的相似度如何。在表 2-1 中可以清楚地看到,除了跟增减元素相关的方法之外,元组支持列表的其他所有方法。还有一个例外,元组没有 __reversed__ 方法,但是这个方法只是个优化而已,reversed(my_tuple) 这个用法在没有 __reversed__ 的情况下也是合法的。

表2-1:列表或元组的方法和属性(那些由object类支持的方法没有列出来)

 

列表

元组

 

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)

es 中出现的次数

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 * nns 的重复拼接

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

* 反向运算符在第 13 章中介绍。

每个 Python 程序员都知道序列可以用 s[a:b] 的形式切片,但是关于切片,我还想说说它的一些不太为人所知的方面。

2.4 切片

在 Python 里,像列表(list)、元组(tuple)和字符串(str)这类序列类型都支持切片操作,但是实际上切片操作比人们所想象的要强大很多。

这一节主要讨论的是这些高级切片形式的用法,它们的实现方法则会在第 10 章的一个自定义类里提到。这么做主要是为了符合这本书的哲学:先讲用法,第四部分中再来讲如何创建新类。

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

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

  • 当只有最后一个位置信息时,我们也可以快速看出切片和区间里有几个元素:range(3)my_list[:3] 都返回 3 个元素。

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

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

    >>> l = [10, 20, 30, 40, 50, 60]
    >>> l[:2] # 在下标2的地方分割
    [10, 20]
    >>> l[2:]
    [30, 40, 50, 60]
    >>> l[:3] # 在下标3的地方分割
    [10, 20, 30]
     >>> l[3:]
    [40, 50, 60]
    

计算机科学家 Edsger W. Dijkstra 对这一风格的解释应该是最好的,详见“延伸阅读”中给出的最后一个参考资料。

接下来进一步看看 Python 解释器是如何理解切片操作的。

2.4.2 对对象进行切片

一个众所周知的秘密是,我们还可以用 s[a:b:c] 的形式对 sab 之间以 c 为间隔取值。c 的值还可以为负,负值意味着反向取值。下面的 3 个例子更直观些:

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

另一个例子是在第 1 章中用 deck[12::13] 的形式在未洗过的牌里把每种花色的 A 拿出来:

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

a:b:c 这种用法只能作为索引或者下标用在 [] 中来返回一个切片对象:slice(a, b, c)。在 10.4.1 节中会讲到,对 seq[start:stop:step] 进行求值的时候,Python 会调用 seq.__getitem__(slice(start, stop, step))。就算你还不会自定义序列类型,了解一下切片对象也是有好处的。例如你可以给切片命名,就像电子表格软件里给单元格区域取名字一样。

比如,要解析示例 2-11 中所示的纯文本文件,这时使用有名字的切片比用硬编码的数字区间要方便得多,注意示例里的 for 循环的可读性有多强。

示例 2-11 纯文本文件形式的收据以一行字符串的形式被解析

>>> 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])
...
    $17.50   Pimoroni PiBrella
     $4.95   6mm Tactile Switch x20
    $28.00   Panavise Jr. - PV-201
    $34.95   PiTFT Mini Kit 320x240

在 10.4 节还有更多机会来了解切片(slice)对象。如果从 Python 用户的角度出发,切片还有个两个额外的功能:多维切片和省略表示法(...)。

2.4.3 多维切片和省略

[] 运算符里还可以使用以逗号分开的多个索引或者是切片,外部库 NumPy 里就用到了这个特性,二维的 numpy.ndarray 就可以用 a[i, j] 这种形式来获取,抑或是用 a[m:n, k:l] 的方式来得到二维切片。稍后的示例 2-22 会展示这个用法。要正确处理这种 [] 运算符的话,对象的特殊方法 __getitem____setitem__ 需要以元组的形式来接收 a[i, j] 中的索引。也就是说,如果要得到 a[i, j] 的值,Python 会调用 a.__getitem__((i, j))

Python 内置的序列类型都是一维的,因此它们只支持单一的索引,成对出现的索引是没有用的。

省略(ellipsis)的正确书写方法是三个英语句号(...),而不是 Unicdoe 码位 U+2026 表示的半个省略号(...)。省略在 Python 解析器眼里是一个符号,而实际上它是 Ellipsis 对象的别名,而 Ellipsis 对象又是 ellipsis 类的单一实例。2 它可以当作切片规范的一部分,也可以用在函数的参数清单中,比如 f(a, ..., z),或 a[i:...]。在 NumPy 中,... 用作多维数组切片的快捷方式。如果 x 是四维数组,那么 x[i, ...] 就是 x[i, :, :, :] 的缩写。如果想了解更多,请参见“Tentative NumPy Tutorial”。

2是的,你没看错,ellipsis 是类名,全小写,而它的内置实例写作 Ellipsis。这其实跟 bool 是小写,但是它的两个实例写作 TrueFalse 异曲同工。

在写这本书的时候,我还没有发现在 Python 的标准库里有任何 Ellipsis 或者是多维索引的用法。如果你知道,请告诉我。这些句法上的特性主要是为了支持用户自定义类或者扩展,比如 NumPy 就是个例子。

除了用来提取序列里的内容,切片还可以用来就地修改可变序列,也就是说修改的时候不需要重新组建序列。

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  ➊
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]

➊ 如果赋值的对象是一个切片,那么赋值语句的右侧必须是个可迭代对象。即便只有单独一个值,也要把它转换成可迭代的序列。

序列的拼接操作可谓是众所周知,任何一本 Python 入门教材都会介绍 +* 的用法,但是在这些用法的背后还有一些可能被忽视的细节。下面就来看看这两种操作。

2.5 对序列使用+*

Python 程序员会默认序列是支持 +* 操作的。通常 + 号两侧的序列由相同类型的数据所构成,在拼接的过程中,两个被操作的序列都不会被修改,Python 会新建一个包含同样类型数据的序列来作为拼接的结果。

如果想要把一个序列复制几份然后再拼接起来,更快捷的做法是把这个序列乘以一个整数。同样,这个操作会产生一个新序列:

>>> l = [1, 2, 3]
>>> l * 5
[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]
>>> 5 * 'abcd'
'abcdabcdabcdabcdabcd'

+* 都遵循这个规律,不修改原有的操作对象,而是构建一个全新的序列。

 如果在 a * n 这个语句中,序列 a 里的元素是对其他可变对象的引用的话,你就需要格外注意了,因为这个式子的结果可能会出乎意料。比如,你想用 my_list = [[]] * 3 来初始化一个由列表组成的列表,但是你得到的列表里包含的 3 个元素其实是 3 个引用,而且这 3 个引用指向的都是同一个列表。这可能不是你想要的效果。

下面来看看如何用 * 来初始化一个由列表组成的列表。

建立由列表组成的列表

有时我们会需要初始化一个嵌套着几个列表的列表,譬如一个列表可能需要用来存放不同的学生名单,或者是一个井字游戏板 3 上的一行方块。想要达成这些目的,最好的选择是使用列表推导,见示例 2-12。

3又称过三关,是一种在 3×3 的方块矩阵上进行的游戏。——译者注

示例 2-12 一个包含 3 个列表的列表,嵌套的 3 个列表各自有 3 个元素来代表井字游戏的一行方块

>>> board = [['_'] * 3 for i in range(3)]  ➊
>>> board
[['_', '_', '_'], ['_', '_', '_'], ['_', '_', '_']]
>>> board[1][2] = 'X' ➋
>>> board
[['_', '_', '_'], ['_', '_', 'X'], ['_', '_', '_']]

➊ 建立一个包含 3 个列表的列表,被包含的 3 个列表各自有 3 个元素。打印出这个嵌套列表。

➋ 把第 1 行第 2 列的元素标记为 X,再打印出这个列表。

示例 2-13 展示了另一个方法,这个方法看上去是个诱人的捷径,但实际上它是错的。

示例 2-13 含有 3 个指向同一对象的引用的列表是毫无用处的

>>> weird_board = [['_'] * 3] * 3 ➊
>>> weird_board
[['_', '_', '_'], ['_', '_', '_'], ['_', '_', '_']]
>>> weird_board[1][2] = 'O' ➋
>>> weird_board
[['_', '_', 'O'], ['_', '_', 'O'], ['_', '_', 'O']]

➊ 外面的列表其实包含 3 个指向同一个列表的引用。当我们不做修改的时候,看起来都还好。

➋ 一旦我们试图标记第 1 行第 2 列的元素,就立马暴露了列表内的 3 个引用指向同一个对象的事实。

示例 2-13 犯的错误本质上跟下面的代码犯的错误一样:

row=['_'] * 3
board = []
for i in range(3):
    board.append(row)  ➊

➊ 追加同一个行对象(row)3 次到游戏板(board)。

相反,示例 2-12 中的方法等同于这样做:

>>> board = []
>>> for i in range(3):
...     row=['_'] * 3 # ➊
...     board.append(row)
...
>>> board
[['_', '_', '_'], ['_', '_', '_'], ['_', '_', '_']]
>>> board[2][0] = 'X'
>>> board  # ➋
[['_', '_', '_'], ['_', '_', '_'], ['X', '_', '_']]

➊ 每次迭代中都新建了一个列表,作为新的一行(row)追加到游戏板(board)。

➋ 正如我们所期待的,只有第 2 行的元素被修改。

 如果你觉得这一节里所说的问题及其对应的解决方法都有点云里雾里,没关系。第 8 章里我们会详细说明引用和可变对象背后的原理和陷阱。

我们一直在说 +*,但是别忘了我们还有 +=*=。随着目标序列的可变性的变化,这个两个运算符的结果也大相径庭。下一节就来详细讨论。

2.6 序列的增量赋值

增量赋值运算符 +=*= 的表现取决于它们的第一个操作对象。简单起见,我们把讨论集中在增量加法(+=)上,但是这些概念对 *= 和其他增量运算符来说都是一样的。

+= 背后的特殊方法是 __iadd__ (用于“就地加法”)。但是如果一个类没有实现这个方法的话,Python 会退一步调用 __add__ 。考虑下面这个简单的表达式:

>>> a += b

如果 a 实现了 __iadd__ 方法,就会调用这个方法。同时对可变序列(例如 listbytearrayarray.array)来说,a 会就地改动,就像调用了 a.extend(b) 一样。但是如果 a 没有实现 __iadd__ 的话,a += b 这个表达式的效果就变得跟 a = a + b 一样了:首先计算 a + b,得到一个新的对象,然后赋值给 a。也就是说,在这个表达式中,变量名会不会被关联到新的对象,完全取决于这个类型有没有实现 __iadd__ 这个方法。

总体来讲,可变序列一般都实现了 __iadd__ 方法,因此 += 是就地加法。而不可变序列根本就不支持这个操作,对这个方法的实现也就无从谈起。

上面所说的这些关于 += 的概念也适用于 *=,不同的是,后者相对应的是 __imul__。关于 __iadd____imul__,第 13 章中会再次提到。

接下来有个小例子,展示的是 *= 在可变和不可变序列上的作用:

>>> l = [1, 2, 3]
>>> id(l)
4311953800  ➊
>>> l *= 2
>>> l
[1, 2, 3, 1, 2, 3]
>>> id(l)
4311953800  ➋
>>> t = (1, 2, 3)
>>> id(t)
4312681568  ➌
>>> t *= 2
>>> id(t)
4301348296  ➍

❶ 刚开始时列表的 ID。

❷ 运用增量乘法后,列表的 ID 没变,新元素追加到列表上。

❸ 元组最开始的 ID。

❹ 运用增量乘法后,新的元组被创建。

对不可变序列进行重复拼接操作的话,效率会很低,因为每次都有一个新对象,而解释器需要把原来对象中的元素先复制到新的对象里,然后再追加新的元素。4

4str 是一个例外,因为对字符串做 += 实在是太普遍了,所以 CPython 对它做了优化。为 str 初始化内存的时候,程序会为它留出额外的可扩展空间,因此进行增量操作的时候,并不会涉及复制原有字符串到新位置这类操作。

我们已经认识了 += 的一般用法,下面来看一个有意思的边界情况。这个例子可以说是突出展示了“不可变性”对于元组来说到底意味着什么。

一个关于+=的谜题

读完下面的代码,然后回答这个问题:示例 2-14 中的两个表达式到底会产生什么结果? 5回答之前不要用控制台去运行这两个式子。

5感谢 Leonardo Rochael 在 2013 年的 Python 巴西会议上提到这个谜题。

示例 2-14 一个谜题

>>> t = (1, 2, [30, 40])
>>> t[2] += [50, 60]

到底会发生下面 4 种情况中的哪一种?

a. t 变成 (1, 2, [30, 40, 50, 60])

b. 因为 tuple 不支持对它的元素赋值,所以会抛出 TypeError 异常。

c. 以上两个都不是。

d. ab 都是对的。

我刚看到这个问题的时候,异常确定地选择了 b,但其实答案是 d,也就是说 ab 都是对的!示例 2-15 是运行这段代码得到的结果,用的 Python 版本是 3.4,但是在 2.7 中结果也一样。6

6有读者提出,如果写成 t[2].extend([50, 60]) 就能避免这个异常。确实是这样,但这个例子是为了展示这种奇怪的现象而专门写的。

示例 2-15 没人料到的结果:t[2] 被改动了,但是也有异常抛出

>>> t = (1, 2, [30, 40])
>>> t[2] += [50, 60]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> t
(1, 2, [30, 40, 50, 60])

Python Tutor是一个对 Python 运行原理进行可视化分析的工具。图 2-3 里是两张截图,分别代表示例 2-15 中 t 的初始和最终状态。

{%}

图 2-3:元组赋值之谜的初始和最终状态(图表由 Python Tutor 网站生成)

下面来看看示例 2-16 中 Python 为表达式 s[a] += b 生成的字节码,可能这个现象背后的原因会变得清晰起来。

示例 2-16 s[a] += b 背后的字节码

>>> dis.dis('s[a] += b')
  1           0 LOAD_NAME                  0(s)
              3 LOAD_NAME                  1(a)
              6 DUP_TOP_TWO
              7 BINARY_SUBSCR                      ➊
              8 LOAD_NAME                  2(b)
             11 INPLACE_ADD                        ➋
             12 ROT_THREE
             13 STORE_SUBSCR                       ➌
             14 LOAD_CONST                 0(None)
             17 RETURN_VALUE

➊ 将 s[a] 的值存入 TOS(Top Of Stack,栈的顶端)。

➋ 计算 TOS += b。这一步能够完成,是因为 TOS 指向的是一个可变对象(也就是示例 2-15 里的列表)。

s[a] = TOS 赋值。这一步失败,是因为 s 是不可变的元组(示例 2-15 中的元组 t)。

这其实是个非常罕见的边界情况,在 15 年的 Python 生涯中,我还没见过谁在这个地方吃过亏。

至此我得到了 3 个教训。

  • 不要把可变对象放在元组里面。

  • 增量赋值不是一个原子操作。我们刚才也看到了,它虽然抛出了异常,但还是完成了操作。

  • 查看 Python 的字节码并不难,而且它对我们了解代码背后的运行机制很有帮助。

在见证了 +* 的微妙之处后,我们把话题转移到序列类型的另一个重要部分上:排序。

2.7 list.sort方法和内置函数sorted

list.sort 方法会就地排序列表,也就是说不会把原列表复制一份。这也是这个方法的返回值是 None 的原因,提醒你本方法不会新建一个列表。在这种情况下返回 None 其实是 Python 的一个惯例:如果一个函数或者方法对对象进行的是就地改动,那它就应该返回 None,好让调用者知道传入的参数发生了变动,而且并未产生新的对象。例如,random.shuffle 函数也遵守了这个惯例。

 用返回 None 来表示就地改动这个惯例有个弊端,那就是调用者无法将其串联起来。而返回一个新对象的方法(比如说 str 里的所有方法)则正好相反,它们可以串联起来调用,从而形成连贯接口(fluent interface)。详情参见维基百科中有关连贯接口的讨论

list.sort 相反的是内置函数 sorted,它会新建一个列表作为返回值。这个方法可以接受任何形式的可迭代对象作为参数,甚至包括不可变序列或生成器(见第 14 章)。而不管 sorted 接受的是怎样的参数,它最后都会返回一个列表。

不管是 list.sort 方法还是 sorted 函数,都有两个可选的关键字参数。

reverse

  如果被设定为 True,被排序的序列里的元素会以降序输出(也就是说把最大值当作最小值来排序)。这个参数的默认值是 False

key

  一个只有一个参数的函数,这个函数会被用在序列里的每一个元素上,所产生的结果将是排序算法依赖的对比关键字。比如说,在对一些字符串排序时,可以用 key=str.lower 来实现忽略大小写的排序,或者是用 key=len 进行基于字符串长度的排序。这个参数的默认值是恒等函数(identity function),也就是默认用元素自己的值来排序。

 可选参数 key 还可以在内置函数 min()max() 中起作用。另外,还有些标准库里的函数也接受这个参数,像 itertools.groupby()heapq.nlargest() 等。

下面通过几个小例子来看看这两个函数和它们的关键字参数:7

7这几个例子还说明了 Python 的排序算法——Timsort——是稳定的,意思是就算两个元素比不出大小,在每次排序的结果里它们的相对位置是固定的。Timsort 在本章结尾的“杂谈”里会有进一步的讨论。

>>> fruits = ['grape', 'raspberry', 'apple', 'banana']
>>> sorted(fruits)
['apple', 'banana', 'grape', 'raspberry']  ➊
>>> fruits
['grape', 'raspberry', 'apple', 'banana']  ➋
>>> sorted(fruits, reverse=True)
['raspberry', 'grape', 'banana', 'apple']  ➌
>>> sorted(fruits, key=len)
['grape', 'apple', 'banana', 'raspberry']  ➍
>>> sorted(fruits, key=len, reverse=True)
['raspberry', 'banana', 'grape', 'apple']  ➎
>>> fruits
['grape', 'raspberry', 'apple', 'banana']  ➏
>>> fruits.sort()                          ➐
>>> fruits
['apple', 'banana', 'grape', 'raspberry']  ➑

❶ 新建了一个按照字母排序的字符串列表。

❷ 原列表并没有变化。

❸ 按照字母降序排序。

❹ 新建一个按照长度排序的字符串列表。因为这个排序算法是稳定的,grape 和 apple 的长度都是 5,它们的相对位置跟在原来的列表里是一样的。

❺ 按照长度降序排序的结果。结果并不是上面那个结果的完全翻转,因为用到的排序算法是稳定的,也就是说在长度一样时,grape 和 apple 的相对位置不会改变。

❻ 直到这一步,原列表 fruits 都没有任何变化。

❼ 对原列表就地排序,返回值 None 会被控制台忽略。

❽ 此时 fruits 本身被排序。

已排序的序列可以用来进行快速搜索,而标准库的 bisect 模块给我们提供了二分查找算法。下一节会详细讲这个函数,顺便还会看看 bisect.insort 如何让已排序的序列保持有序。

2.8 用bisect来管理已排序的序列

bisect 模块包含两个主要函数,bisectinsort,两个函数都利用二分查找算法来在有序序列中查找或插入元素。

2.8.1 用bisect来搜索

bisect(haystack, needle)haystack(干草垛)里搜索 needle(针)的位置,该位置满足的条件是,把 needle 插入这个位置之后,haystack 还能保持升序。也就是在说这个函数返回的位置前面的值,都小于或等于 needle 的值。其中 haystack 必须是一个有序的序列。你可以先用 bisect(haystack, needle) 查找位置 index,再用 haystack.insert(index, needle) 来插入新值。但你也可用 insort 来一步到位,并且后者的速度更快一些。

 Python 的高产贡献者 Raymond Hettinger 写了一个排序集合模块,模块里集成了 bisect 功能,但是比独立的 bisect 更易用。

示例 2-17 利用几个精心挑选的 needle,向我们展示了 bisect 返回的不同位置值。这段代码的输出结果显示在图 2-4 中。

示例 2-17 在有序序列中用 bisect 查找某个元素的插入位置

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' % n for n in HAYSTACK))
    demo(bisect_fn)

❶ 用特定的 bisect 函数来计算元素应该出现的位置。

❷利用该位置来算出需要几个分隔符号。

❸ 把元素和其应该出现的位置打印出来。

❹ 根据命令上最后一个参数来选用 bisect 函数。

❺ 把选定的函数在抬头打印出来。

{%}

图 2-4:用 bisect 函数时示例 2-17 的输出。每一行以 needle @ position(元素及其应该插入的位置)开始,然后展示了该元素在原序列中的物理位置

bisect 的表现可以从两个方面来调教。

首先可以用它的两个可选参数——lohi——来缩小搜寻的范围。lo 的默认值是 0hi 的默认值是序列的长度,即 len() 作用于该序列的返回值。

其次,bisect 函数其实是 bisect_right 函数的别名,后者还有个姊妹函数叫 bisect_left。它们的区别在于,bisect_left 返回的插入位置是原序列中跟被插入元素相等的元素的位置,也就是新元素会被放置于它相等的元素的前面,而 bisect_right 返回的则是跟它相等的元素之后的位置。这个细微的差别可能对于整数序列来讲没什么用,但是对于那些值相等但是形式不同的数据类型来讲,结果就不一样了。比如说虽然 1 == 1.0 的返回值是 True11.0 其实是两个不同的元素。图 2-5 显示的是用 bisect_left 来运行上述示例的结果。

{%}

图 2-5:用 bisect_left 运行示例 2-17 得到的结果(跟图 2-4 对比可以发现,值 18232930 的插入位置变成了原序列中这些值的前面)

bisect 可以用来建立一个用数字作为索引的查询表格,比如说把分数和成绩 8 对应起来,见示例 2-18。

8成绩指的是在美国大学中普遍使用的 A~F 字母成绩,A 表示优秀,F 表示不及格。——译者注

示例 2-18 根据一个分数,找到它所对应的成绩

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect.bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

示例 2-18 里的代码来自 bisect 模块的文档。文档里列举了一些利用 bisect 的函数,它们可以在很长的有序序列中作为 index 的替代,用来更快地查找一个元素的位置。

这些函数不但可以用于查找,还可以用来向序列中插入新元素,下面就来看看它们的用法。

2.8.2 用bisect.insort插入新元素

排序很耗时,因此在得到一个有序序列之后,我们最好能够保持它的有序。bisect.insort 就是为了这个而存在的。

insort(seq, item) 把变量 item 插入到序列 seq 中,并能保持 seq 的升序顺序。详见示例 2-19 和它在图 2-6 里的输出。

示例 2-19 insort 可以保持有序序列的顺序

import bisect
import random

SIZE=7

random.seed(1729)

my_list = []
for i in range(SIZE):
    new_item = random.randrange(SIZE*2)
    bisect.insort(my_list, new_item)
    print('%2d ->' % new_item, my_list)

{%}

图 2-6:示例 2-19 的输出

insortbisect 一样,有 lohi 两个可选参数用来控制查找的范围。它也有个变体叫 insort_left,这个变体在背后用的是 bisect_left

目前所提到的内容都不仅仅是对列表或者元组有效,还可以应用于几乎所有的序列类型上。有时候因为列表实在是太方便了,所以 Python 程序员可能会过度使用它,反正我知道我犯过这个毛病。而如果你只需要处理数字列表的话,数组可能是个更好的选择。下面就来讨论一些可以替换列表的数据结构。

2.9 当列表不是首选时

虽然列表既灵活又简单,但面对各类需求时,我们可能会有更好的选择。比如,要存放 1000 万个浮点数的话,数组(array)的效率要高得多,因为数组在背后存的并不是 float 对象,而是数字的机器翻译,也就是字节表述。这一点就跟 C 语言中的数组一样。再比如说,如果需要频繁对序列做先进先出的操作,deque(双端队列)的速度应该会更快。

 如果在你的代码里,包含操作(比如检查一个元素是否出现在一个集合中)的频率很高,用 set(集合)会更合适。set 专为检查元素是否存在做过优化。但是它并不是序列,因为 set 是无序的。第 3 章会详细讨论它。

本章余下的内容都是关于在某些情况下可以替换列表的数据类型的,让我们从数组开始。

2.9.1 数组

如果我们需要一个只包含数字的列表,那么 array.arraylist 更高效。数组支持所有跟可变序列有关的操作,包括 .pop.insert.extend。另外,数组还提供从文件读取和存入文件的更快的方法,如 .frombytes.tofile

Python 数组跟 C 语言数组一样精简。创建数组需要一个类型码,这个类型码用来表示在底层的 C 语言应该存放怎样的数据类型。比如 b 类型码代表的是有符号的字符(signed char),因此 array('b') 创建出的数组就只能存放一个字节大小的整数,范围从 -128 到 127,这样在序列很大的时候,我们能节省很多空间。而且 Python 不会允许你在数组里存放除指定类型之外的数据。

示例 2-20 展示了从创建一个有 1000 万个随机浮点数的数组开始,到如何把这个数组存放到文件里,再到如何从文件读取这个数组。

示例 2-20 一个浮点型数组的创建、存入文件和从文件读取的过程

>>> from array import array  ➊
>>> from random import random
>>> floats = array('d', (random() for i in range(10**7)))  ➋
>>> floats[-1]  ➌
0.07802343889111107
>>> fp = open('floats.bin', 'wb')
>>> floats.tofile(fp)  ➍
>>> fp.close()
>>> floats2 = array('d')  ➎
>>> fp = open('floats.bin', 'rb')
>>> floats2.fromfile(fp, 10**7)  ➏
>>> fp.close()
>>> floats2[-1]  ➐
0.07802343889111107
>>> floats2 == floats  ➑
True

❶ 引入 array 类型。

❷ 利用一个可迭代对象来建立一个双精度浮点数组(类型码是 'd'),这里我们用的可迭代对象是一个生成器表达式。

❸ 查看数组的最后一个元素。

❹ 把数组存入一个二进制文件里。

❺ 新建一个双精度浮点空数组。

❻ 把 1000 万个浮点数从二进制文件里读取出来。

❼ 查看新数组的最后一个元素。

❽ 检查两个数组的内容是不是完全一样。

从上面的代码我们能得出结论,array.tofilearray.fromfile 用起来很简单。把这段代码跑一跑,你还会发现它的速度也很快。一个小试验告诉我,用 array.fromfile 从一个二进制文件里读出 1000 万个双精度浮点数只需要 0.1 秒,这比从文本文件里读取的速度要快 60 倍,因为后者会使用内置的 float 方法把每一行文字转换成浮点数。另外,使用 array.tofile 写入到二进制文件,比以每行一个浮点数的方式把所有数字写入到文本文件要快 7 倍。另外,1000 万个这样的数在二进制文件里只占用 80 000 000 个字节(每个浮点数占用 8 个字节,不需要任何额外空间),如果是文本文件的话,我们需要 181 515 739 个字节。

 另外一个快速序列化数字类型的方法是使用 pickle模块pickle.dump 处理浮点数组的速度几乎跟 array.tofile 一样快。不过前者可以处理几乎所有的内置数字类型,包含复数、嵌套集合,甚至用户自定义的类。前提是这些类没有什么特别复杂的实现。

还有一些特殊的数字数组,用来表示二进制数据,比如光栅图像。里面涉及的 bytesbytearry 类型会在第 4 章提及。

表 2-2 对数组和列表的功能做了一些总结。

表2-2:列表和数组的属性和方法(不包含过期的数组方法以及那些由对象实现的方法)

 

列表

数组

 

s.__add__(s2)__

s + s2,拼接

s.__iadd__(s2)__

s += s2,就地拼接

s.append(e)

在尾部添加一个元素

s.byteswap

 

翻转数组内每个元素的字节序列,转换字节序

s.clear()

 

删除所有元素

s.__contains__(e)

s 是否含有 e

s.copy()

 

对列表浅复制

s.__copy__()

 

copy.copy 的支持

s.count(e)

se 出现的次数

s.__deepcopy__()

 

copy.deepcopy 的支持

s.__delitem__(p)

删除位置 p 的元素

s.extend(it)

将可迭代对象 it 里的元素添加到尾部

s.frombytes(b)

 

将压缩成机器值的字节序列读出来添加到尾部

s.fromfile(f, n)

 

将二进制文件 f 内含有机器值读出来添加到尾部,最多添加 n

s.fromlist(l)

 

将列表里的元素添加到尾部,如果其中任何一个元素导致了 TypeError 异常,那么所有的添加都会取消

s.__getitem__(p)

s[p],读取位置 p 的元素

s.index(e)

找到 e 在序列中第一次出现的位置

s.insert(p, e)

在位于 p 的元素之前插入元素 e

s.itemsize

 

数组中每个元素的长度是几个字节

s.__iter__()

返回迭代器

s.__len__()

len(s),序列的长度

s.__mul__(n)

s * n,重复拼接

s.__imul__(n)

s *= n,就地重复拼接

s.__rmul__(n)

n * s,反向重复拼接*

s.pop([p])

删除位于 p 的值并返回这个值,p 的默认值是最后一个元素的位置

s.remove(e)

删除序列里第一次出现的 e 元素

s.reverse()

就地调转序列中元素的位置

s.__reversed__()

 

返回一个从尾部开始扫描元素的迭代器

s.__setitem__(p, e)

s[p] = e,把位于 p 位置的元素替换成 e

s.sort([key], [revers])

 

就地排序序列,可选参数有 keyreverse

s.tobytes()

 

把所有元素的机器值用 bytes 对象的形式返回

s.tofile(f)

 

把所有元素以机器值的形式写入一个文件

s.tolist()

 

把数组转换成列表,列表里的元素类型是数字对象

s.typecode

 

返回只有一个字符的字符串,代表数组元素在 C 语言中的类型

* 第 13 章会讲反向运算符。

从 Python 3.4 开始,数组类型不再支持诸如 list.sort() 这种就地排序方法。要给数组排序的话,得用 sorted 函数新建一个数组:

a = array.array(a.typecode, sorted(a))

想要在不打乱次序的情况下为数组添加新的元素,bisect.insort 还是能派上用场(就像 2.8.2 节中所展示的)。

如果你总是跟数组打交道,却没有听过 memoryview,那就太遗憾了。下面就来谈谈 memoryview

2.9.2 内存视图

memoryview 是一个内置类,它能让用户在不复制内容的情况下操作同一个数组的不同切片。memoryview 的概念受到了 NumPy 的启发(参见 2.9.3 节)。Travis Oliphant 是 NumPy 的主要作者,他在回答 “When should a memoryview be used?”这个问题时是这样说的:

内存视图其实是泛化和去数学化的 NumPy 数组。它让你在不需要复制内容的前提下,在数据结构之间共享内存。其中数据结构可以是任何形式,比如 PIL 图片、SQLite 数据库和 NumPy 的数组,等等。这个功能在处理大型数据集合的时候非常重要。

memoryview.cast 的概念跟数组模块类似,能用不同的方式读写同一块内存数据,而且内容字节不会随意移动。这听上去又跟 C 语言中类型转换的概念差不多。memoryview.cast 会把同一块内存里的内容打包成一个全新的 memoryview 对象给你。

在示例 2-21 里,我们利用 memoryview 精准地修改了一个数组的某个字节,这个数组的元素是 16 位二进制整数。

示例 2-21 通过改变数组中的一个字节来更新数组里某个元素的值

>>> numbers = array.array('h', [-2, -1, 0, 1, 2])
>>> memv = memoryview(numbers)  ➊
>>> len(memv)
5
>>> memv[0]  ➋
-2
>>> memv_oct = memv.cast('B')  ➌
>>> 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])  ➏

❶ 利用含有 5 个短整型有符号整数的数组(类型码是 'h')创建一个 memoryview

memv 里的 5 个元素跟数组里的没有区别。

❸ 创建一个 memv_oct,这一次是把 memv 里的内容转换成 'B' 类型,也就是无符号字符。

❹ 以列表的形式查看 memv_oct 的内容。

❺ 把位于位置 5 的字节赋值成 4

❻ 因为我们把占 2 个字节的整数的高位字节改成了 4,所以这个有符号整数的值就变成了 1024

在第 4 章的示例 4-4 中,我们还可以看到如何利用 memoryviewstruct 来操作二进制序列。

另外,如果利用数组来做高级的数字处理是你的日常工作,那么 NumPy 和 SciPy 应该是你的常用武器。下面就是对这两个库的简单介绍。

2.9.3 NumPy和SciPy

整本书我都在强调如何最大限度地利用 Python 标准库。但是 NumPy 和 SciPy 的优秀让我觉得偶尔跑个题来谈谈它们也是很值得的。

凭借着 NumPy 和 SciPy 提供的高阶数组和矩阵操作,Python 成为科学计算应用的主流语言。NumPy 实现了多维同质数组(homogeneous array)和矩阵,这些数据结构不但能处理数字,还能存放其他由用户定义的记录。通过 NumPy,用户能对这些数据结构里的元素进行高效的操作。

SciPy 是基于 NumPy 的另一个库,它提供了很多跟科学计算有关的算法,专为线性代数、数值积分和统计学而设计。SciPy 的高效和可靠性归功于其背后的 C 和 Fortran 代码,而这些跟计算有关的部分都源自于 Netlib 库。换句话说,SciPy 把基于 C 和 Fortran 的工业级数学计算功能用交互式且高度抽象的 Python 包装起来,让科学家如鱼得水。

示例 2-22 是一个很简短的演示,从中可以窥见一些 NumPy 二维数组的基本操作。

示例 2-22 对 numpy.ndarray 的行和列进行基本操作

>>> import numpy  ➊
>>> a = numpy.arange(12)  ➋
>>> a
array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  10,  11])
>>> type(a)
<class 'numpy.ndarray'>
>>> a.shape  ➌
(12,)
>>> a.shape = 3, 4  ➍
>>> a
array([[  0,  1,  2,  3],
       [  4,  5,  6,  7],
       [  8,  9, 10, 11]])
>>> a[2]  ➎
array([  8,  9,  10,  11])
>>> a[2, 1]  ➏
9
>>> a[:, 1]  ➐
array([1, 5, 9])
>>> a.transpose() ➑
array([[  0,  4,  8],
       [  1,  5,  9],
       [  2,  6, 10],
       [  3,  7, 11]])

❶ 安装 NumPy 之后,导入它(NumPy 并不是 Python 标准库的一部分)。

❷ 新建一个 0~11 的整数的 numpy.ndarray,然后把它打印出来。

❸ 看看数组的维度,它是一个一维的、有 12 个元素的数组。

❹ 把数组变成二维的,然后把它打印出来看看。

❺ 打印出第 2 行。

❻ 打印第 2 行第 1 列的元素。

❼ 把第 1 列打印出来。

❽ 把行和列交换,就得到了一个新数组。

NumPy 也可以对 numpy.ndarray 中的元素进行抽象的读取、保存和其他操作:

>>> import numpy
>>> floats = numpy.loadtxt('floats-10M-lines.txt')  ➊
>>> floats[-3:]  ➋
array([ 3016362.69195522, 535281.10514262, 4566560.44373946])
>>> floats *= .5  ➌
>>> floats[-3:]
array([ 1508181.34597761, 267640.55257131, 2283280.22186973])
>>> from time import perf_counter as pc  ➍
>>> t0 = pc(); floats /= 3; pc() - t0  ➎
0.03690556302899495
>>> numpy.save('floats-10M', floats)  ➏
>>> floats2 = numpy.load('floats-10M.npy', 'r+')  ➐
>>> floats2 *= 6
>>> floats2[-3:]  ➑
memmap([3016362.69195522, 535281.10514262, 4566560.44373946])

❶ 从文本文件里读取 1000 万个浮点数。

❷ 利用序列切片来读取其中的最后 3 个数。

❸ 把数组里的每个数都乘以 0.5,然后再看看最后 3 个数。

❹ 导入精度和性能都比较高的计时器(Python 3.3 及更新的版本中都有这个库)。

❺ 把每个元素都除以 3,可以看到处理 1000 万个浮点数所需的时间还不足 40 毫秒。

❻ 把数组存入后缀为 .npy 的二进制文件。

❼ 将上面的数据导入到另外一个数组里,这次 load 方法利用了一种叫作内存映射的机制,它让我们在内存不足的情况下仍然可以对数组做切片。

❽ 把数组里每个数乘以 6 之后,再检视一下数组的最后 3 个数。

NumPy 和 SciPy 的安装可能会比较费劲。在“Installing the SciPy Stack”页面,SciPy.org 建议找一个科学计算 Python 的分发渠道帮忙,比如 Anacoda、Enthought Canopy、WinPython,等等。常见的 GNU/Linux 版本的用户应该可以在他们自己的包管理系统中找到 NumPy 和 SciPy。例如,在 Debian 或者 Ubuntu 上面,用户可以通过下面的命令一键安装:

$ sudo apt-get install python-numpy python-scipy

以上的内容仅仅是九牛一毛。NumPy 和 SciPy 都是异常强大的库,也是其他一些很有用的工具的基石。PandasBlaze 数据分析库就以它们为基础,提供了高效的且能存储非数值类数据的数组类型,和读写常见数据文件格式(例如 csv、xls、SQL 转储和 HDF5)的功能。因此,要详细介绍 NumPy 和 SciPy 的话,不写成几本书是不可能的。虽然本书不在此列,但是如果要对 Python 的序列类型做一个概览,恐怕没有人能忽略 NumPy。

在介绍完扁平序列(包括标准数组和 NumPy 数组)之后,让我们把目光投向 Python 中可以取代列表的另外一种数据结构:队列。

2.9.4 双向队列和其他形式的队列

利用 .append.pop 方法,我们可以把列表当作栈或者队列来用(比如,把 .append.pop(0) 合起来用,就能模拟队列的“先进先出”的特点)。但是删除列表的第一个元素(抑或是在第一个元素之前添加一个元素)之类的操作是很耗时的,因为这些操作会牵扯到移动列表里的所有元素。

collections.deque 类(双向队列)是一个线程安全、可以快速从两端添加或者删除元素的数据类型。而且如果想要有一种数据类型来存放“最近用到的几个元素”,deque 也是一个很好的选择。这是因为在新建一个双向队列的时候,你可以指定这个队列的大小,如果这个队列满员了,还可以从反向端删除过期的元素,然后在尾端添加新的元素。示例 2-23 中有几个双向队列的典型操作。

示例 2-23 使用双向队列

>>> from collections import deque
>>> dq = deque(range(10), maxlen=10)  ➊
>>> dq
deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
>>> dq.rotate(3)  ➋
>>> dq
deque([7, 8, 9, 0, 1, 2, 3, 4, 5, 6], maxlen=10)
>>> dq.rotate(-4)
>>> dq
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 0], maxlen=10)
>>> dq.appendleft(-1)  ➌
>>> dq
deque([-1, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
>>> dq.extend([11, 22, 33])  ➍
>>> dq
deque([3, 4, 5, 6, 7, 8, 9, 11, 22, 33], maxlen=10)
>>> dq.extendleft([10, 20, 30, 40])  ➎
>>> dq
deque([40, 30, 20, 10, 3, 4, 5, 6, 7, 8], maxlen=10)

maxlen 是一个可选参数,代表这个队列可以容纳的元素的数量,而且一旦设定,这个属性就不能修改了。

❷ 队列的旋转操作接受一个参数 n,当 n > 0 时,队列的最右边的 n 个元素会被移动到队列的左边。当 n < 0 时,最左边的 n 个元素会被移动到右边。

❸ 当试图对一个已满(len(d) == d.maxlen)的队列做头部添加操作的时候,它尾部的元素会被删除掉。注意在下一行里,元素 0 被删除了。

❹ 在尾部添加 3 个元素的操作会挤掉 -112

extendleft(iter) 方法会把迭代器里的元素逐个添加到双向队列的左边,因此迭代器里的元素会逆序出现在队列里。

表 2-3 总结了列表和双向队列这两个类型的方法(object 类包含的方法除外)。

双向队列实现了大部分列表所拥有的方法,也有一些额外的符合自身设计的方法,比如说 popleftrotate。但是为了实现这些方法,双向队列也付出了一些代价,从队列中间删除元素的操作会慢一些,因为它只对在头尾的操作进行了优化。

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

表2-3:列表和双向队列的方法(不包括由对象实现的方法)

 

列表

双向队列

 

s.__add__(s2)

 

s + s2,拼接

s.__iadd__(s2)

s += s2,就地拼接

s.append(e)

添加一个元素到最右侧(到最后一个元素之后)

s.appendleft(e)

 

添加一个元素到最左侧(到第一个元素之前)

s.clear()

删除所有元素

s.__contains__(e)

 

s 是否含有 e

s.copy()

 

对列表浅复制

s.__copy__()

 

copy.copy(浅复制)的支持

s.count(e)

se 出现的次数

s.__delitem__(p)

把位置 p 的元素移除

s.extend(i)

将可迭代对象 i 中的元素添加到尾部

s.extendleft(i)

 

将可迭代对象 i 中的元素添加到头部

s.__getitem__(p)

s[p],读取位置 p 的元素

s.index(e)

 

找到 e 在序列中第一次出现的位置

s.insert(p, e)

 

在位于 p 的元素之前插入元素 e

s.__iter__()

返回迭代器

s.__len__()

len(s),序列的长度

s.__mul__(n)

 

s * n,重复拼接

s.__imul__(n)

 

s *= n,就地重复拼接

s.__rmul__(n)

 

n * s,反向重复拼接*

s.pop()

移除最后一个元素并返回它的值#

s.popleft()

 

移除第一个元素并返回它的值

s.remove(e)

移除序列里第一次出现的 e 元素

s.reverse()

调转序列中元素的位置

s.__reversed__()

返回一个从尾部开始扫描元素的迭代器

s.rotate(n)

 

n 个元素从队列的一端移到另一端

s.__setitem__(p, e)

s[p] = e,把位于 p 位置的元素替换成 e

s.sort([key], [reverse])

 

就地排序序列,可选参数有 keyreverse

* 第 13 章会讲反向运算符。

# a_list.pop(p) 这个操作只能用于列表,双向队列的这个方法不接收参数。

除了 deque 之外,还有些其他的 Python 标准库也有对队列的实现。

queue

  提供了同步(线程安全)类 QueueLifoQueuePriorityQueue,不同的线程可以利用这些数据类型来交换信息。这三个类的构造方法都有一个可选参数 maxsize,它接收正整数作为输入值,用来限定队列的大小。但是在满员的时候,这些类不会扔掉旧的元素来腾出位置。相反,如果队列满了,它就会被锁住,直到另外的线程移除了某个元素而腾出了位置。这一特性让这些类很适合用来控制活跃线程的数量。

multiprocessing

  这个包实现了自己的 Queue,它跟 queue.Queue 类似,是设计给进程间通信用的。同时还有一个专门的 multiprocessing.JoinableQueue 类型,可以让任务管理变得更方便。

asyncio

  Python 3.4 新提供的包,里面有 QueueLifoQueuePriorityQueueJoinableQueue,这些类受到 queuemultiprocessing 模块的影响,但是为异步编程里的任务管理提供了专门的便利。

heapq

  跟上面三个模块不同的是,heapq 没有队列类,而是提供了 heappushheappop 方法,让用户可以把可变序列当作堆队列或者优先队列来使用。

到了这里,我们对列表之外的类的介绍也就告一段落了,是时候阶段性地总结一下对序列类型的探索了。注意我们还没有提到 str(字符串)和二进制序列,它们将在第 4 章中专门介绍。

2.10 本章小结

要想写出准确、高效和地道的 Python 代码,对标准库里的序列类型的掌握是不可或缺的。

Python 序列类型最常见的分类就是可变和不可变序列。但另外一种分类方式也很有用,那就是把它们分为扁平序列和容器序列。前者的体积更小、速度更快而且用起来更简单,但是它只能保存一些原子性的数据,比如数字、字符和字节。容器序列则比较灵活,但是当容器序列遇到可变对象时,用户就需要格外小心了,因为这种组合时常会搞出一些“意外”,特别是带嵌套的数据结构出现时,用户要多费一些心思来保证代码的正确。

列表推导和生成器表达式则提供了灵活构建和初始化序列的方式,这两个工具都异常强大。如果你还不能熟练地使用它们,可以专门花时间练习一下。它们其实不难,而且用起来让人上瘾。

元组在 Python 里扮演了两个角色,它既可以用作无名称的字段的记录,又可以看作不可变的列表。当元组被当作记录来用的时候,拆包是最安全可靠地从元组里提取不同字段信息的方式。新引入的 * 句法让元组拆包的便利性更上一层楼,让用户可以选择性忽略不需要的字段。具名元组也已经不是一个新概念了,但它似乎没有受到应有的重视。就像普通元组一样,具名元组的实例也很节省空间,但它同时提供了方便地通过名字来获取元组各个字段信息的方式,另外还有个实用的 ._asdict() 方法来把记录变成 OrderedDict 类型。

Python 里最受欢迎的一个语言特性就是序列切片,而且很多人其实还没完全了解它的强大之处。比如,用户自定义的序列类型也可以选择支持 NumPy 中的多维切片和省略(...)。另外,对切片赋值是一个修改可变序列的捷径。

重复拼接 seq * n 在正确使用的前提下,能让我们方便地初始化含有不可变元素的多维列表。增量赋值 +=*= 会区别对待可变和不可变序列。在遇到不可变序列时,这两个操作会在背后生成新的序列。但如果被赋值的对象是可变的,那么这个序列会就地修改——然而这也取决于序列本身对特殊方法的实现。

序列的 sort 方法和内置的 sorted 函数虽然很灵活,但是用起来都不难。这两个方法都比较灵活,是因为它们都接受一个函数作为可选参数来指定排序算法如何比较大小,这个参数就是 key 参数。key 还可以被用在 minmax 函数里。如果在插入新元素的同时还想保持有序序列的顺序,那么需要用到 bisect.insortbisect.bisect 的作用则是快速查找。

除了列表和元组,Python 标准库里还有 array.array。另外,虽然 NumPy 和 SciPy 都不是 Python 标准库的一部分,但稍微学习一下它们,会让你在处理大规模数值型数据时如有神助。

本章末尾介绍了 collections.deque 这个类型,它具有灵活多用和线程安全的特性。表 2-3 将它和列表的 API 做了比较。本章最后也提及了一些标准库中的其他队列类型的实现。

2.11 延伸阅读

David Beazley 和 Brian K. Jones 的《Python Cookbook(第 3 版)中文版》一书的第 1 章“数据结构”里有很多专门针对序列的小窍门。尤其是“1.11 对切片命名”这一部分,从中我学会把切片赋值给变量以改善可读性,本书的示例 2-11 对此做了说明。

《Python Cookbook(第 2 版)中文版》用的是 Python 2.4,但其中大部分的代码都可以运行在 Python 3 中。该书第 5 章和第 6 章的大部分内容都是跟序列有关的。该书的编者有 Alex Martelli、Anna Martelli Ravenscroft 和 David Ascher,另外还有十几位 Python 程序员为内容做出了贡献。第 3 版则是从零开始完全重写的,书的重点也放在了 Python 的语义上,特别是 Python 3 带来的那些变化,而不是像第 2 版那样把重点放在如何解决实际问题上。虽然第 2 版中有些内容已经不是最优解了,但是我仍然推荐把这两个版本都读一读。

Python 官方网站中的“Sorting HOW TO”一文通过几个例子讲解了 sortedlist.sort 的高级用法。

PEP 3132 — Extended Iterable Unpacking”算得上是使用 *extra 句法进行平行赋值的权威指南。如果你想窥探一下 Python 本身的开发过程,“Missing *-unpacking generalizations”是一个 bug 追踪器,里面有很多关于如何更广泛地使用可迭代对象拆包的讨论和提议。“PEP 448—Additional Unpacking Generalizations”就是这些讨论的直接结果。就在我写这本书的时候,这些改动也许会被集成在 Python 3.5 中。

Eli Bendersky 的博客文章“Less Copies in Python with the Buffer Protocol and memoryviews”里有一些关于 memoryview 的小教程。

市面上关于 NumPy 的书多到数不清,其中有些书的名字里都不带“NumPy”这几个字,例如 Wes McKinney 的《利用 Python 进行数据分析》一书。

科学家尤其钟爱 NumPy 和 SciPy 的强大以及与 Python 的交互式控制台的结合,于是他们专门开发了 IPython。IPython 是 Python 自带控制台的强大替代品,而且它还附带了图形界面、内嵌的图表渲染、文学编程支持(代码和文本互动)和 PDF 渲染。而这些互动多媒体对话还能以 IPython 记事本的形式在网络上分享——详见“IPython 记事本”中的截屏和视频。IPython 在 2012 年非常流行,背后的开发者收到了一笔 1 150 000 美元的捐赠。这笔来自 Sloan 基金的捐赠是专门用来支持加州大学伯克利分校的开发者的,好让他们能在 2013—2014 年期间按计划实现 IPython 的扩展。

Python 标准库里的“8.3. collections — Container datatypes”里有一些关于双向队列和其他集合类型的使用技巧。

Python 里的范围(range)和切片都不会返回第二个下标所指的元素,Edsger W. Dijkstra 在一个很短的备忘录里为这一惯例做了最好的辩护。这篇名为“Why Numbering Should Start at Zero”的备忘录其实是关于数学符号的,但是它跟 Python 的关系在于,Dijkstra 教授严肃又活泼地解释了为什么 2,3,…,12 这个序列应该表达为 2 ≤ i < 13。备忘录对其他所有的表达习惯都作出了反驳,同时还说明了为什么不能让用户自行决定表达习惯。虽然文章的标题是关于基于 0 的下标,但是整篇文章其实都在说为什么 'ABCDE'[1:3] 的结果应该是 'BC' 而不是 'BCD',以及为什么 2,3,…,12 应该写作 range(2, 13)。(顺便说一下,这份备忘录是手写的,但是字写得干净漂亮。如果有人就此创作 Dijkstra 字体,我应该会买一份。)

杂谈

元组的本质

2012 年,我在 PyCon US 上贴了一张关于 ABC 语言的墙报。Guido 在开创 Python 语言之前曾做过 ABC 解释器方面的工作,因此他也去看了我的墙报。我们聊了不少,而且都提到了 ABC 里的 compounds 类型。compounds 算得上是 Python 元组的鼻祖,它既支持平行赋值,又可以用在字典(dict)里作为合成键(ABC 里对应字典的类型是表格,即 table)。但 compounds 不属于序列,它不是迭代类型,也不能通过下标来提取某个值,更不用说切片了。要么把 compounds 对象当作整体来用,要么用平行赋值把里面所有的字段都提取出来,仅此而已。

我跟 Guido 说,上面这些限制让 compounds 的作用变得很明确,它只能用作没有字段名的记录。Guido 回应说,Python 里的元组能当作序列来使用,其实是一个取巧的实现。

这其实体现了 Python 的实用主义,而实用主义是 Python 较之 ABC 更好用也更成功的原因。从一个语言开发人员的角度来看,让元组具有序列的特性可能需要下点功夫,结果则是设计出了一个概念上并不如 compounds 纯粹,却更灵活的元组——它甚至能当成不可变的列表来使用。

说真的,不可变列表这种数据类型在编程语言里真的非常好用(其实 frozenlist 这个名字更酷),而 Python 里这种类型其实就是一个行为很像序列的元组。

“优雅是简约之父”

很久以前,*extra 这种语法就在函数里用来把多个元素赋值给一个参数了。(我有本出版于 1996 年的讲 Python 1.4 的书,里面就提到了这个用法。)Python 1.6 或更新的版本里,这个语法在函数调用中用来把一个可迭代对象拆包成不同的参数,这算是跟上面说的那种用法互补。这一设计直观而优雅,并且取代了 Python 里的 apply 函数。如今到了 Python 3,*extra 这个写法又可以用在赋值表达式的左侧,从而在平行赋值里接收多余的元素。这一点让这个本来就很实用的语法锦上添花。

像这样的改进一个接着一个,让 Python 变得越来越灵活,越来越统一,也越来越简单。“优雅是简约之父”(“Elegance begets simplicity”)是 2009 年在芝加哥的 PyCon 的口号,印在 PyCon 的 T 恤上,同样印在 T 恤上的还有 Bruce Eckel 画的《易经》第二十二卦,即贲卦的卦象。贲代表着典雅高贵。这也是我最喜欢的一件 PyCon 的 T 恤。

扁平序列和容器序列

为了解释不同序列类型里不同的内存模型,我用了容器序列扁平序列这两个说法。其中“容器”一词来自“Data Model”文档:

有些对象里包含对其他对象的引用;这些对象称为容器。

因此,我特别使用了“容器序列”这个词,因为 Python 里有是容器但并非序列的类型,比如 dictset。容器序列可以嵌套着使用,因为容器里的引用可以针对包括自身类型在内的任何类型。

与此相反,扁平序列因为只能包含原子数据类型,比如整数、浮点数或字符,所以不能嵌套使用。

称其为“扁平序列”是因为我希望有个名词能够跟“容器序列”形成对比。这个词是我自己发明的,专门用来指代 Python 中“不是容器序列”的序列,在其他地方你可能找不到这样的用法。如果这个词出现在维基百科上面的话,我们需要给它加上“原创研究”标签。我更倾向于把这类词称作“自创名词”,希望它能对你有所帮助并为你所用。

混合类型列表

Python 入门教材往往会强调列表是可以同时容纳不同类型的元素的,但是实际上这样做并没有什么特别的好处。我们之所以用列表来存放东西,是期待在稍后使用它的时候,其中的元素有一些通用的特性(比如,列表里存的是一类可以“呱呱”叫的动物,那么所有的元素都应该会发出这种叫声,即便其中一部分元素类型并不是鸭子)。在 Python 3 中,如果列表里的东西不能比较大小,那么我们就不能对列表进行排序:

>>> l = [28, 14, '28', 5, '9', '1', 0, 6, '23', 19]
>>> sorted(l)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unorderable types: str() < int()

元组则恰恰相反,它经常用来存放不同类型的的元素。这也符合它的本质,元组就是用作存放彼此之间没有关系的数据的记录。

key 参数很妙

list.sortsortedmaxmin 函数的 key 参数是一个很棒的设计。其他语言里的排序函数需要用户提供一个接收两个参数的比较函数作为参数,像是 Python 2 里的 cmp(a, b)。用 key 参数能把事情变得简单且高效。说它更简单,是因为只需要提供一个单参数函数来提取或者计算一个值作为比较大小的标准即可,而 Python 2 的这种设计则需要用户写一个返回值是—1、0 或者 1 的双参数函数。说它更高效,是因为在每个元素上,key 函数只会被调用一次。而双参数比较函数则在每一次两两比较的时候都会被调用。诚然,在排序的时候,Python 总会比较两个键(key),但是那一阶段的计算会发生在 C 语言那一层,这样会比调用用户自定义的 Python 比较函数更快。

另外,key 参数也能让你对一个混有数字字符和数值的列表进行排序。你只需要决定到底是把字符看作数值,还是把数值看作字符:

>>> l = [28, 14, '28', 5, '9', '1', 0, 6, '23', 19]
>>> sorted(l, key=int)
[0, '1', 5, 6, '9', 14, 19, '23', 28, '28']
>>> sorted(l, key=str)
[0, '1', 14, 19, '23', 28, '28', 5, 6, '9']

Oracle、Google 和 Timbot 之间的八卦

sortedlist.sort 背后的排序算法是 Timsort,它是一种自适应算法,会根据原始数据的顺序特点交替使用插入排序和归并排序,以达到最佳效率。这样的算法被证明是很有效的,因为来自真实世界的数据通常是有一定的顺序特点的。维基百科上有一个条目是关于这个算法的。

Timsort 在 2002 年的时候首次用在 CPython 中;自 2009 年起,Java 和 Android 也开始使用这个算法。后面这个时间点如此广为人知,是因为在 Google 对 Sun 的侵权案中, Oracle 把 Timsort 中的一些相关代码当作了呈堂证供。详见 “Oracle v. Google—Day 14 Filings”一文。

Timsort 的创始人是 Tim Peters,他同时也是一位高产的 Python 核心开发者。由于他贡献了太多代码,以至于很多人都说他其实是人工智能,他也就有了“Timbot”这一绰号。在“Python Humor”里可以读到相关的故事。Tim 也是“Python 之禅”(import this)的作者。

目录

  • 版权声明
  • O'Reilly Media, Inc. 介绍
  • 献词
  • 前言
  • 第一部分 序幕
  • 第 1 章 Python 数据模型
  • 第二部分 数据结构
  • 第 2 章 序列构成的数组
  • 第 3 章 字典和集合
  • 第 4 章 文本和字节序列
  • 第三部分 把函数视作对象
  • 第 5 章 一等函数
  • 第 6 章 使用一等函数实现设计模式
  • 第 7 章 函数装饰器和闭包
  • 第四部分 面向对象惯用法
  • 第 8 章 对象引用、可变性和垃圾回收
  • 第 9 章 符合 Python 风格的对象
  • 第 10 章 序列的修改、散列和切片
  • 第 11 章 接口:从协议到抽象基类
  • 第 12 章 继承的优缺点
  • 第 13 章 正确重载运算符
  • 第五部分 控制流程
  • 第 14 章 可迭代的对象、迭代器和生成器
  • 第 15 章 上下文管理器和 else 块
  • 第 16 章 协程
  • 第 17 章 使用future处理并发
  • 第 18 章 使用 asyncio 包处理并发
  • 第六部分 元编程
  • 第 19 章 动态属性和特性
  • 第 20 章 属性描述符
  • 第 21 章 类元编程
  • 结语
  • 附录 A 辅助脚本
  • Python 术语表
  • 作者简介
  • 关于封面