Python 提供了许多内置的数据集合类型，如果选择明智的话，可以高效解决许多问题。
你可能已经学过下面这些集合类型，它们都有专门的字面值，如下所示。
• 列表（list）。
• 元组（tuple）。
• 字典（dictionary）。
• 集合（set）
Python 的集合类型当然不止这 4 种，它的标准库扩展了其可选列表。在许多情况下，
问题的答案可能正如选择正确的数据结构一样简单。本书的这一部分将深入介绍各种集合
类型，以帮你做出更好的选择。
列表与元组
Python 最基本的两个集合类型就是列表与元组，它们都表示对象序列。只要是花几小
时学过 Python 的人，应该都很容易发现二者之间的根本区别：列表是动态的，其大小可以
改变；而元组是不可变的，一旦创建就不能修改。
虽然快速分配/释放小型对象的优化方法有很多，但对于元素位置本身也是信息的数据
结构来说，推荐使用元组这一数据类型。举个例子，想要保存(x, y)坐标对，元组可能是一
个很好的选择。反正关于元组的细节相当无趣。本章关于元组唯一重要的内容就是，tuple
是不可变的（immutable），因此也是可哈希的（hashable）。其具体含义将会在后面“字典”
一节介绍。比元组更有趣的是另一种动态的数据结构 list，以及它的工作原理和高效处
理理方式。
实现细节
许多程序员容易将 Python 的 list 类型与其他语言（如 C、C++或 Java）标准库中常
见的链表的概念相混淆。事实上，CPython 的列表根本不是列表。在 CPython 中，列表被
实现为长度可变的数组。对于其他 Python 实现（如 Jython 和 IronPython）而言，这种说法
应该也是正确的，虽然这些项目的文档中没有记录其实现细节。造成这种混淆的原因很清
楚。这种数据类型被命名为列表，还和链表实现有相似的接口。
为什么这一点很重要，这又意味着什么呢？列表是最常见的数据结构之一，其使用方
式会对所有应用的性能带来极大影响。此外，CPython 又是最常见也最常用的 Python 实现，
所以了解其内部实现细节至关重要。
从细节上来看，Python 中的列表是由对其他对象的引用组成的的连续数组。指向这个
数组的指针及其长度被保存在一个列表头结构中。这意味着，每次添加或删除一个元素时，
由引用组成的数组需要改变大小（重新分配）。幸运的是，Python 在创建这些数组时采用了
指数过分配（exponential over-allocation），所以并不是每次操作都需要改变数组大小。这也
是添加或取出元素的平摊复杂度较低的原因。不幸的是，在普通链表中“代价很小”的其
他一些操作在 Python 中的计算复杂度却相对较高：
• 利用 list.insert 方法在任意位置插入一个元素 — 复杂度为 O(n)。
• 利用 list.delete 或 del 删除一个元素 — 复杂度为 O(n)。
这里 n 是列表的长度。至少利用索引来查找或修改元素的时间开销与列表大小无关。
表 2-1 是一张完整的表格，列出了大多数列表操作的平均时间复杂度。
表 2-1
操作 复杂度
复制 O(n)
添加元素 O(1)
插入元素 O(n)
获取元素 O(1)
修改元素 O(1)
删除元素 O(n)
遍历 O(n)
获取长度为 k 的切片 O(k)
删除切片 O(n)
操作 复杂度
修改长度为 k 的切片 O(k+n)
列表扩展（Extend） O(k)
乘以 k O(nk)
测试元素是否在列表中（element in list） O(n)
min()/max() O(n)
获取列表长度 O(1)
对于需要真正的链表（或者简单来说，双端 append 和 pop 操作的复杂度都是 O(1)
的数据结构）的场景，Python 在内置的 collections 模块中提供了 deque（双端队列）。
它是栈和队列的一般化，在需要用到双向链表的地方都可以使用这种数据结构。
列表推导
你可能知道，编写这样的代码是很痛苦的：
evens = []
for i in range(10):
… if i % 2 == 0:
… evens.append(i)
…
evens
[0, 2, 4, 6, 8]
这种写法可能适用于 C 语言，但在 Python 中的实际运行速度很慢，原因如下。
• 解释器在每次循环中都需要判断序列中的哪一部分需要修改。
• 需要用一个计数器来跟踪需要处理的元素。
• 由于 append()是一个列表方法，所以每次遍历时还需要额外执行一个查询函数。
列表推导正是解决这个问题的正确方法。它使用编排好的功能对上述语法的一部分做
了自动化处理：
[i for i in range(10) if i % 2 == 0]
[0, 2, 4, 6, 8]
这种写法除了更加高效之外，也更加简短，涉及的语法元素也更少。在大型程序中，
这意味着更少的错误，代码也更容易阅读和理解。
其他习语
Python 习语的另一个典型例子是使用 enumerate（枚举）。在循环中使用序列时，这
个内置函数可以很方便地获取其索引。以下面这段代码为例：
i = 0
for element in [‘one’, ‘two’, ‘three’]:
… print(i, element)
… i += 1
…
0 one
1 two
2 three
它可以替换为下面这段更短的代码：
for i, element in enumerate([‘one’, ‘two’, ‘three’]):
… print(i, element)
…
0 one
1 two
2 three
如果需要一个一个合并多个列表（或任意可迭代对象）中的元素，那么可以使用内置
的 zip()函数。对两个大小相等的可迭代对象进行均匀遍历时，这是一种非常常用的模式：
for item in zip([1, 2, 3], [4, 5, 6]):
… print(item)
…
(1, 4)
(2, 5)
(3, 6)
注意，对 zip()函数返回的结果再次调用 zip()，可以将其恢复原状：
for item in zip(*zip([1, 2, 3], [4, 5, 6])):
… print(item)
…
(1, 2, 3)
(4, 5, 6)
另一个常用的语法元素是序列解包（sequence unpacking）。这种方法并不限于列表
和元组，而是适用于任意序列类型（甚至包括字符串和字节序列）。只要赋值运算符左
边的变量数目与序列中的元素数目相等，你都可以用这种方法将元素序列解包到另一组
变量中：
first, second, third = “foo”, “bar”, 100
first
‘foo’
second
‘bar’
third
100
解包还可以利用带星号的表达式获取单个变量中的多个元素，只要它的解释没有歧义
即可。还可以对嵌套序列进行解包。特别是在遍历由序列构成的复杂数据结构时，这种方
法非常实用。下面是一些更复杂的解包示例：带星号的表达式可以获取序列的剩余部分
first, second, *rest = 0, 1, 2, 3
first
0
second
1
rest
[2, 3]带星号的表达式可以获取序列的中间部分
first, *inner, last = 0, 1, 2, 3
first
0
inner
[1, 2]
last
3嵌套解包
(a, b), (c, d) = (1, 2), (3, 4)
a, b, c, d
(1, 2, 3, 4)
