第 5 章 Python中常见的数据结构

第 5 章 Python中常见的数据结构

有没有什么是每个Python开发者都应该进一步练习和学习的呢?

那就是数据结构。数据结构是构建程序的基础。各个数据结构在组织方式上有自己的特点,以便在不同情况下高效访问数据。

我相信无论程序员的技术水平或经验如何,掌握一些基本功总是有好处的。

我并不主张只专注于掌握更多的数据结构知识,这是一种“失效模式”(failure mode),只会让人陷入假想理论上的幻境,而不会带来任何实际的结果。

不过花一些时间来补习数据结构(和算法)的知识总会有好处。

无论是花几天时间“突击”,还是利用零碎的时间持续学习,在数据结构上下点功夫都是值得的。

那么Python中有哪些数据结构呢?列表、字典、集合,还有……栈?Python有栈吗?

看到没?Python在其标准库中提供了大量的数据结构,但问题在于各自的命名有点词不达意。

举例来说,很多人甚至不清楚Python是否具体实现了像栈这样著名的“抽象数据类型”。相比之下,Java等其他语言则更“计算机科学化”,其中的命名很明确。比如,Java中的列表还细分成了LinkedListArrayList

这种细分的命名便于我们识别各个数据类型的预期行为和计算复杂度。Python也倾向于使用简单且“人性化”的命名方案。我喜欢Python的方案,因为人性化也是Python编程更有趣的原因之一。

这种方案的缺点在于,即使是经验丰富的Python开发人员,也不清楚内置的列表类型是以链表还是动态数组实现的。如果需要用到这些知识却没有掌握,则会让人感到沮丧,也可能导致面试被拒。

本章将介绍Python及其标准库内置的基本数据结构和抽象数据类型的实现。

我的目标是阐释常见的抽象数据类型在Python中对应的名称及实现,并逐个进行简单的介绍。这些内容也会帮助你在Python面试中大放异彩。

如果你正在寻找一本能够用来温习通用数据结构知识的好书,我强烈推荐Steven S. Skiena的《算法设计手册》。

这本书介绍了各种数据结构及其各自在不同算法中的实际应用,并在这两个方面之间取得了很好的平衡。它对我编写本章提供了很大的帮助。

5.1 字典、映射和散列表

在Python中,字典是核心数据结构。字典可以存储任意数量的对象,每个对象都由唯一的字典标识。

字典通常也被称为映射散列表查找表关联数组。字典能够高效查找、插入和删除任何与给定键关联的对象。

这在现实中意味着什么呢?字典对象相当于现实世界中的电话簿。

电话簿有助于快速检索与给定键(人名)相关联的信息(电话号码)。因此不必为了查找某人的号码而浏览整本电话簿,根据人名基本上就能直接跳到需要查找的相关信息。

若想研究以何种方式组织信息才有利于快速检索,上述类比就不那么贴切了。但基本性能特征相同,即字典能够用来快速查找与给定键相关的信息。

总之,字典是计算机科学中最常用且最重要的数据结构之一。

那么Python如何处理字典呢?

我们来看看Python及其标准库中可用的字典实现。

5.1.1 dict——首选字典实现

由于字典非常重要,因此Python直接在语言核心中实现了一个稳健的字典1dict数据类型2

1为了与其他资料统一,这里将不区分中文语境下的dict(字典)和“字典类型的数据结构”,统称为“字典”。——译者注

2详见Python文档:“Mapping Types — dict”。

Python还提供了一些有用的“语法糖”来处理程序中的字典。例如,用花括号字典表达式语法和字典解析式能够方便地创建新的字典对象:

phonebook = {
    'bob': 7387,
    'alice': 3719,
    'jack': 7052,
}

squares = {x: x * x for x in range(6)}

>>> phonebook['alice']
3719

>>> squares
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

关于哪些对象可以作为字典键,有一些限制。

Python的字典由可散列类型3的键来索引。可散列对象具有在其生命周期中永远不会改变的散列值(参见__hash__),并且可以与其他对象进行比较(参见__eq__)。另外,相等的可散列对象,其散列值必然相同。

3详见Python文档词汇表:“Hashable”。

像字符串和数这样的不可变类型是可散列的,它们可以很好地用作字典键。元组对象也可以用作字典键,但这些元组本身必须只包含可散列类型。

Python的内置字典实现可以应对大多数情况。字典是高度优化的,并且是Python语言的基石,例如栈帧中的类属性和变量都存储在字典中。

Python字典基于经过充分测试和精心调整过的散列表实现,提供了符合期望的性能特征。一般情况下,用于查找、插入、更新和删除操作的时间复杂度都为O(1)

大部分情况下,应该使用Python自带的标准字典实现。但是也存在专门的第三方字典实现,例如跳跃表4或基于B树的字典。

4一种数据结构,详见。——译者注

除了通用的dict对象外,Python的标准库还包含许多特殊的字典实现。它们都基于内置的字典类,基本性能特征相同,但添加了其他一些便利特性。

下面来逐个了解一下。

5.1.2 collections.OrderedDict——能记住键的插入顺序

collections.OrderedDict5是特殊的dict子类,该类型会记录添加到其中的键的插入顺序。

5详见Python文档:“collections.OrderedDict”。

尽管在CPython 3.6及更高版本中,标准的字典实现也能保留键的插入顺序,但这只是CPython实现的一个副作用,直到Python 3.7才将这种特性固定下来了。6因此,如果在自己的工作中很需要用到键顺序,最好明确使用OrderedDict类。

6详见CPython邮件列表。

顺便说一句,OrderedDict不是内置的核心语言部分,因此必须从标准库中的collections模块导入。

>>> import collections
>>> d = collections.OrderedDict(one=1, two=2, three=3)

>>> d
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> d['four'] = 4
>>> d
OrderedDict([('one', 1), ('two', 2),
             ('three', 3), ('four', 4)])

>>> d.keys()
odict_keys(['one', 'two', 'three', 'four'])

5.1.3 collections.defaultdict——为缺失的键返回默认值

defaultdict是另一个dict子类,其构造函数接受一个可调用对象,查找时如果找不到给定的键,就返回这个可调用对象。7

7详见Python文档:“collections.defaultdict”。

与使用get()方法或在普通字典中捕获KeyError异常相比,这种方式的代码较少,并能清晰地表达出程序员的意图。

>>> from collections import defaultdict
>>> dd = defaultdict(list)

# 访问缺失的键就会用默认工厂方法创建它并将其初始化
# 在本例中工厂方法为list():
>>> dd['dogs'].append('Rufus')
>>> dd['dogs'].append('Kathrin')
>>> dd['dogs'].append('Mr Sniffles')

>>> dd['dogs']
['Rufus', 'Kathrin', 'Mr Sniffles']

5.1.4 collections.ChainMap——搜索多个字典

collections.ChainMap数据结构将多个字典分组到一个映射中8,在查找时逐个搜索底层映射,直到找到一个符合条件的键。对ChainMap进行插入、更新和删除操作,只会作用于其中的第一个字典。

8详见Python文档:“collections.ChainMap”。

>>> from collections import ChainMap
>>> dict1 = {'one': 1, 'two': 2}
>>> dict2 = {'three': 3, 'four': 4}
>>> chain = ChainMap(dict1, dict2)

>>> chain
ChainMap({'one': 1, 'two': 2}, {'three': 3, 'four': 4})

# ChainMap在内部从左到右逐个搜索,
# 直到找到对应的键或全部搜索完毕:
>>> chain['three']
3
>>> chain['one']
1
>>> chain['missing']
KeyError: 'missing'

5.1.5 types.MappingProxyType——用于创建只读字典

MappingProxyType封装了标准的字典,为封装的字典数据提供只读视图。9该类添加自Python 3.3,用来创建字典不可变的代理版本。

9详见Python文档:“types.MappingProxyType”。

举例来说,如果希望返回一个字典来表示类或模块的内部状态,同时禁止向该对象写入内容,此时MappingProxyType就能派上用场。使用MappingProxyType无须创建完整的字典副本。

>>> from types import MappingProxyType
>>> writable = {'one': 1, 'two': 2}
>>> read_only = MappingProxyType(writable)

# 代理是只读的:
>>> read_only['one']
1
>>> read_only['one'] = 23
TypeError:
"'mappingproxy' object does not support item assignment"

# 更新原字典也会影响到代理:
>>> writable['one'] = 42
>>> read_only
mappingproxy({'one': 42, 'two': 2})

5.1.6 Python中的字典:总结

本节列出的所有Python字典实现都是内置于Python标准库中的有效实现。

一般情况下,建议在自己的程序中使用内置的dict数据类型。这是优化过的散列表实现,功能多且已被直接内置到了核心语言中。

如果你有内置dict无法满足的特殊需求,那么建议使用本节列出的其他数据类型。

虽然前面列出的其他字典实现均可用,但大多数情况下都应该使用Python内置的标准dict,这样其他开发者在维护你的代码时就会轻松一点。

5.1.7 关键要点

  • 字典是Python中的核心数据结构。
  • 大部分情况下,内置的dict类型就足够了。
  • Python标准库提供了用于满足特殊需求的实现,比如只读字典或有序字典。

5.2 数组数据结构

大多数编程语言中都有数组这种基本数据结构,它在许多算法中都有广泛的运用。

本节将介绍Python中的一些数组实现,这些数组只用到了语言的核心特性或Python标准库包含的功能。

本章还会介绍每种实现的优缺点,这样就能根据实际情况选择合适的实现。不过在介绍之前,先来了解一些基础知识。

首先要知道数组的原理及用途。

数组由大小固定的数据记录组成,根据索引能快速找到其中的每个元素。

因为数组将信息存储在依次连接的内存块中,所以它是连续的数据结构(与链式列表等链式数据结构不同)。

现实世界中能用来类比数组数据结构的是停车场。

停车场可被视为一个整体,即单个对象,但停车场内的每个停车位都有唯一的编号索引。停车位是车辆的容器,每个停车位既可以为空,也可以停有汽车、摩托车或其他车辆。

各个停车场之间也会有区别。

有些停车场可能只能停一种类型的车辆。例如,汽车停车场不允许停放自行车。这种“有限制”的停车场相当于“类型数组”数据结构,只允许存储相同数据类型的元素。

在性能方面,根据元素的索引能快速查找数组中对应的元素。合理的数组实现能够确保索引访问的耗时为常量时间O(1)

Python标准库包含几个与数组相似的数据结构,每个数据结构的特征略有不同。下面来逐一介绍。

5.2.1 列表——可变动态数组

列表是Python语言核心的一部分。10虽然名字叫列表,但它实际上是以动态数组实现的。这意味着列表能够添加或删除元素,还能分配或释放内存来自动调整存储空间。

10详见Python文档:“list”。

Python列表可以包含任意元素,因为Python中一切皆为对象,连函数也是对象。因此,不同的数据类型可以混合存储在一个列表中。

这个功能很强大,但缺点是同时支持多种数据类型会导致数据存储得不是很紧凑。因此整个结构占据了更多的空间。11

11本质上是因为列表中存储的是PyObject指针,指向不同的对象。然而数组是直接存放数据本身。后面类似内容不再提醒,还请读者注意。——译者注

>>> arr = ['one', 'two', 'three']
>>> arr[0]
'one'

# 列表拥有不错的__repr__方法:
>>> arr
['one', 'two', 'three']

# 列表是可变的:
>>> arr[1] = 'hello'
>>> arr
['one', 'hello', 'three']

>>> del arr[1]
>>> arr
['one', 'three']

# 列表可以含有任意类型的数据:
>>> arr.append(23)
>>> arr
['one', 'three', 23]

5.2.2 元组——不可变容器

与列表一样,元组也是Python语言核心的一部分。12与s列表不同的是,Python的元组对象是不可变的。这意味着不能动态添加或删除元素,元组中的所有元素都必须在创建时定义。

12详见Python文档:“tuple”。

就像列表一样,元组可以包含任意数据类型的元素。这具有很强的灵活性,但也意味着数据的打包密度要比固定类型的数组小。

>>> arr = 'one', 'two', 'three'
>>> arr[0]
'one'

# 元组拥有不错的__repr__方法:
>>> arr
('one', 'two', 'three')

# 元组是可变的
>>> arr[1] = 'hello'
TypeError:
"'tuple' object does not support item assignment"

>>> del arr[1]
TypeError:
"'tuple' object doesn't support item deletion"

# 元组可以持有任意类型的数据:
#(添加元素会创建新元组)
>>> arr + (23,)
('one', 'two', 'three', 23)

5.2.3 array.array——基本类型数组

Python的array模块占用的空间较少,用于存储C语言风格的基本数据类型(如字节、32位整数,以及浮点数等)。

使用array.array类创建的数组是可变的,行为与列表类似。但有一个重要的区别:这种数组是单一数据类型的“类型数组”。13

13详见Python文档:“array.array”。

由于这个限制,含有多个元素的array.array对象比列表和元组节省空间。存储在其中的元素紧密排列,因此适合存储许多相同类型的元素。

此外,数组中有许多普通列表中也含有的方法,使用方式也相同,无须对应用程序代码进行其他更改。

>>> import array
>>> arr = array.array('f', (1.0, 1.5, 2.0, 2.5))
>>> arr[1]
1.5

# 数组拥有不错的__repr__方法:
>>> arr
array('f', [1.0, 1.5, 2.0, 2.5])

# 数组是可变的:
>>> arr[1] = 23.0
>>> arr
array('f', [1.0, 23.0, 2.0, 2.5])

>>> del arr[1]
>>> arr
array('f', [1.0, 2.0, 2.5])

>>> arr.append(42.0)
>>> arr
array('f', [1.0, 2.0, 2.5, 42.0])

# 数组中元素类型是固定的:
>>> arr[1] = 'hello'
TypeError: "must be real number, not str"

5.2.4 str——含有Unicode字符的不可变数组

{\rm Python}~3.x使用str对象将文本数据存储为不可变的Unicode字符序列。14实际上,这意味着str是不可变的字符数组。说来也怪,str也是一种递归的数据结构,字符串中的每个字符都是长度为1的str对象。

14详见Python文档:“str”。

由于字符串对象专注于单一数据类型,元组排列紧密,因此很节省空间,适合用来存储Unicode文本。因为字符串在Python中是不可变的,所以修改字符串需要创建一个改动副本。最接近“可变字符串”概念的是存储单个字符的列表。

>>> arr = 'abcd'
>>> arr[1]
'b'

>>> arr
'abcd'

# 字符串是可变的:
>>> arr[1] = 'e'
TypeError: 
"'str' object does not support item assignment"

>>> del arr[1]
TypeError:
"'str' object doesn't support item deletion"

# 字符串可以解包到列表中,从而得到可变版本:
>>> list('abcd')
['a', 'b', 'c', 'd']
>>> ''.join(list('abcd'))
'abcd'

# 字符串是递归型数据类型:
>>> type('abc')
"<class 'str'>"
>>> type('abc'[0])
"<class 'str'>"

5.2.5 bytes——含有单字节的不可变数组

bytes对象是单字节的不可变序列,单字节为0~255(含)范围内的整数。15从概念上讲,bytesstr对象类似,可认为是不可变的字节数组。

15详见Python文档:“bytes”。

与字符串一样,也有专门用于创建bytes对象的字面语法,bytes也很节省空间。bytes对象是不可变的,但与字符串不同,还有一个名为bytearray的专用“可变字节数组”数据类型,bytes可以解包到bytearray中。下一节将介绍更多关于bytearray的内容。

>>> arr = bytes((0, 1, 2, 3))
>>> arr[1]
1

# bytes 有自己的语法:
>>> arr
b'\x00\x01\x02\x03'
>>> arr = b'\x00\x01\x02\x03'

# bytes 必须位于0~255:
>>> bytes((0, 300))
ValueError: "bytes must be in range(0, 256)"

# bytes 是不可变的:
>>> arr[1] = 23
TypeError:
"'bytes' object does not support item assignment"

>>> del arr[1]
TypeError:
"'bytes' object doesn't support item deletion"

5.2.6 bytearray——含有单字节的可变数组

bytearray类型是可变整数序列16,包含的整数范围在0~255(含)。bytearraybytes对象关系密切,主要区别在于bytearray可以自由修改,如覆盖、删除现有元素和添加新元素,此时bytearray对象将相应地增长和缩小。

16详见Python文档:“bytearray”。

bytearray数可以转换回不可变的bytes对象,但是这需要复制所存储的数据,是耗时为O(n)的慢操作。

>>> arr = bytearray((0, 1, 2, 3))
>>> arr[1]
1

# bytearray 的repr:
>>> arr
bytearray(b'\x00\x01\x02\x03')

# bytearray 是可变的:
>>> arr[1] = 23
>>> arr
bytearray(b'\x00\x17\x02\x03')

>>> arr[1]
23

# bytearray 可以增长或缩小:
>>> del arr[1]
>>> arr
bytearray(b'\x00\x02\x03')

>>> arr.append(42)
>>> arr
bytearray(b'\x00\x02\x03*')

# bytearray 只能持有byte,即位于0~255 范围内的整数
>>> arr[1] = 'hello'
TypeError: "an integer is required"

>>> arr[1] = 300
ValueError: "byte must be in range(0, 256)"

# bytearray 可以转换回byte 对象,此过程会复制数据:
>>> bytes(arr)
b'\x00\x02\x03*'

5.2.7 关键要点

Python中有多种内置数据结构可用来实现数组,本节只专注位于标准库中和核心语言特性中的数据结构。

如果不想局限于Python标准库,那么从NumPy这样的第三方软件包中可找到为科学计算和数据科学提供的许多快速数组实现。

对于Python中包含的数组数据结构,选择顺序可归结如下。

如果需要存储任意对象,且其中可能含有混合数据类型,那么可以选择使用列表或元组,前者可变后者不可变。

如果存储数值(整数或浮点数)数据并要求排列紧密且注重性能,那么先尝试array.array,看能否满足要求。另外可尝试准库之外的软件包,如NumPy或Pandas。

如果有需要用Unicode字符表示的文本数据,那么可以使用Python内置的str。如果需要用到“可变字符串”,则请使用字符列表。

如果想存储一个连续的字节块,不可变的请使用bytes,可变的请使用bytearray

总之,在大多数情况下首先应尝试列表。如果在性能或存储空间上有问题,再选择其他专门的数据类型。一般像列表这样通用的数组型数据结构已经能同时兼顾开发速度和编程便利性的要求了。

强烈建议在初期使用通用数据格式,不要试图在一开始就榨干所有性能。

5.3 记录、结构体和纯数据对象

与数组相比,记录数据结构中的字段数目固定,每个都有一个名称,类型也可以不同。

本节将介绍Python中的记录、结构体,以及“纯数据对象”17,但只介绍标准库中含有的内置数据类型和类。

17指只含有数据本身,不含有业务逻辑的数据类型,参见。

顺便说一句,这里的“记录”定义很宽泛。例如,这里也会介绍像Python的内置元组这样的类型。由于元组中的字段没有名称,因此一般不认为它是严格意义上的记录。

Python提供了几种可用于实现记录、结构体和数据传输对象的数据类型。本节将快速介绍每个实现及各自特性,最后进行总结并给出一个决策指南,用来帮你做出自己的选择。

好吧,让我们开始吧!

5.3.1 字典——简单数据对象

Python字典能存储任意数量的对象,每个对象都由唯一的键来标识。18字典也常常称为映射关联数组,能高效地根据给定的键查找、插入和删除所关联的对象。

18详见Python文档“Dictionaries, Maps, and Hashtables”一章。

Python的字典还可以作为记录数据类型(record data type)或数据对象来使用。在Python中创建字典很容易,因为语言内置了创建字典的语法糖,简洁又方便。

字典创建的数据对象是可变的,同时由于可以随意添加和删除字段,因此对字段名称几乎没有保护措施。这些特性综合起来可能会引入令人惊讶的bug,毕竟要在便利性和避免错误之间做出取舍。

car1 = {
    'color': 'red',
    'mileage': 3812.4,
    'automatic': True,
}
car2 = {
    'color': 'blue',
    'mileage': 40231,
    'automatic': False,
}

# 字典有不错的__repr__方法:
>>> car2
{'color': 'blue', 'automatic': False, 'mileage': 40231}

# 获取mileage:
>>> car2['mileage']
40231

# 字典是可变的:
>>> car2['mileage'] = 12
>>> car2['windshield'] = 'broken'
>>> car2
{'windshield': 'broken', 'color': 'blue',
 'automatic': False, 'mileage': 12}

# 对于提供错误、缺失和额外的字段名称并没有保护措施:
car3 = {
    'colr': 'green',
    'automatic': False,
    'windshield': 'broken',
}

5.3.2 元组——不可变对象集合

Python元组是简单的数据结构,用于对任意对象进行分组。19元组是不可变的,创建后无法修改。

19详见Python文档:“tuple”。

在性能方面,元组占用的内存略少于CPython中的列表20,构建速度也更快。

20详见CPython源码:tupleobject.clistobject.c

从如下反汇编的字节码中可以看到,构造元组常量只需要一个LOAD_CONST操作码,而构造具有相同内容的列表对象则需要多个操作:

>>> import dis
>>> dis.dis(compile("(23, 'a', 'b', 'c')", '', 'eval'))
      0 LOAD_CONST            4 ((23, 'a', 'b', 'c'))
      3 RETURN_VALUE

>>> dis.dis(compile("[23, 'a', 'b', 'c']", '', 'eval'))
      0 LOAD_CONST            0 (23)
      3 LOAD_CONST            1 ('a')
      6 LOAD_CONST            2 ('b')
      9 LOAD_CONST            3 ('c')
     12 BUILD_LIST            4
     15 RETURN_VALUE

不过你无须过分关注这些差异。在实践中这些性能差异通常可以忽略不计,试图通过用元组替换列表来获得额外的性能提升一般都是入了歧途。

单纯的元组有一个潜在缺点,即存储在其中的数据只能通过整数索引来访问,无法为元组中存储的单个属性制定一个名称,从而影响了代码的可读性。

此外,元组总是一个单例模式的结构,很难确保两个元组存储了相同数量的字段和相同的属性。

这样很容易因疏忽而犯错,比如弄错字段顺序。因此,建议尽可能减少元组中存储的字段数量。

# 字段:color、mileage、automatic
>>> car1 = ('red', 3812.4, True)
>>> car2 = ('blue', 40231.0, False)

# 元组的实例有不错的__repr__方法:
>>> car1
('red', 3812.4, True)
>>> car2
('blue', 40231.0, False)

# 获取mileage:
>>> car2[1]
40231.0

# 元组是可变的:
>>> car2[1] = 12
TypeError:
"'tuple' object does not support item assignment"

# 对于错误或额外的字段,以及提供错误的字段顺序,并没有报错措施:
>>> car3 = (3431.5, 'green', True, 'silver')

5.3.3 编写自定义类——手动精细控制

类可用来为数据对象定义可重用的“蓝图”(blueprint),以确保每个对象都提供相同的字段。

普通的Python类可作为记录数据类型,但需要手动完成一些其他实现中已有的便利功能。例如,向__init__构造函数添加新字段就很烦琐且耗时。

此外,对于从自定义类实例化得到的对象,其默认的字符串表示形式没什么用。解决这个问题需要添加自己的__repr__方法。21这个方法通常很冗长,每次添加新字段时都必须更新。

21详见4.2节。

存储在类上的字段是可变的,并且可以随意添加新字段。使用@property装饰器22能创建只读字段,并获得更多的访问控制,但是这又需要编写更多的胶水代码。

22详见Python文档:“property”。

编写自定义类适合将业务逻辑和行为添加到记录对象中,但这意味着这些对象在技术上不再是普通的纯数据对象。

class Car:
    def __init__(self, color, mileage, automatic):
        self.color = color
        self.mileage = mileage
        self.automatic = automatic

>>> car1 = Car('red', 3812.4, True)
>>> car2 = Car('blue', 40231.0, False)

# 获取mileage:
>>> car2.mileage
40231.0

# 类是可变的:
>>> car2.mileage = 12
>>> car2.windshield = 'broken'

# 类的默认字符串形式没多大用处,必须手动编写一个__repr__方法:
>>> car1
<Car object at 0x1081e69e8>

5.3.4 collections.namedtuple——方便的数据对象

自Python 2.6以来添加的namedtuple类扩展了内置元组数据类型。23与自定义类相似,namedtuple可以为记录定义可重用的“蓝图”,以确保每次都使用正确的字段名称。

23详见4.6节。

与普通的元组一样,namedtuple是不可变的。这意味着在创建namedtuple实例之后就不能再添加新字段或修改现有字段。

除此之外,namedtuple就相当于具有名称的元组。存储在其中的每个对象都可以通过唯一标识符访问。因此无须整数索引,也无须使用变通方法,比如将整数常量定义为索引的助记符。

namedtuple对象在内部是作为普通的Python类实现的,其内存占用优于普通的类,和普通元组一样高效:

>>> from collections import namedtuple
>>> from sys import getsizeof

>>> p1 = namedtuple('Point', 'x y z')(1, 2, 3)
>>> p2 = (1, 2, 3)

>>> getsizeof(p1)
72
>>> getsizeof(p2)
72

由于使用namedtuple就必须更好地组织数据,因此无意中清理了代码并让其更加易读。

我发现从专用的数据类型(例如固定格式的字典)切换到namedtuple有助于更清楚地表达代码的意图。通常,每当我在用namedtuple重构应用时,都神奇地为代码中的问题想出了更好的解决办法。

用namedtuple替换普通(非结构化的)元组和字典还可以减轻同事的负担,因为用namedtuple传递的数据在某种程度上能做到“自说明”。

>>> from collections import namedtuple
>>> Car = namedtuple('Car' , 'color mileage automatic')
>>> car1 = Car('red', 3812.4, True)

# 实例有不错的__repr__方法:
>>> car1
Car(color='red', mileage=3812.4, automatic=True)

# 访问字段:
>>> car1.mileage
3812.4

# 字段是不可变的:
>>> car1.mileage = 12
AttributeError: "can't set attribute"
>>> car1.windshield = 'broken'
AttributeError:
"'Car' object has no attribute 'windshield'"

5.3.5 typing.NamedTuple——改进版namedtuple

这个类添加自Python 3.6,是collections模块中namedtuple类的姊妹。24它与namedtuple非常相似,主要区别在于用新语法来定义记录类型并支持类型注解(type hint)。

24详见Python文档:“typing.NamedTuple”。

注意,只有像mypy这样独立的类型检查工具才会在意类型注解。不过即使没有工具支持,类型注解也可帮助其他程序员更好地理解代码(如果类型注解没有随代码及时更新则会带来混乱)。

>>> from typing import NamedTuple

class Car(NamedTuple):
    color: str
    mileage: float
    automatic: bool

>>> car1 = Car('red', 3812.4, True)

# 实例有不错的__repr__方法:
>>> car1
Car(color='red', mileage=3812.4, automatic=True)

# 访问字段:
>>> car1.mileage
3812.4

# 字段是不可变的:
>>> car1.mileage = 12
AttributeError: "can't set attribute"
>>> car1.windshield = 'broken'
AttributeError:
"'Car' object has no attribute 'windshield'"

# 只有像mypy 这样的类型检查工具才会落实类型注解:
>>> Car('red', 'NOT_A_FLOAT', 99)
Car(color='red', mileage='NOT_A_FLOAT', automatic=99)

5.3.6 struct.Struct——序列化C结构体

struct.Struct25用于在Python值和C结构体之间转换,并将其序列化为Python字节对象。例如可以用来处理存储在文件中或来自网络连接的二进制数据。

25详见Python文档:“struct.Struct”。

结构体使用与格式化字符串类似的语法来定义,能够定义并组织各种C数据类型(如charintlong,以及对应的无符号的变体)。

序列化结构体一般不用来表示只在Python代码中处理的数据对象,而是主要用作数据交换格式。

在某些情况下,与其他数据类型相比,将原始数据类型打包到结构体中占用的内存较少。但大多数情况下这都属于高级(且可能不必要的)优化。

>>> from struct import Struct
>>> MyStruct = Struct('i?f')
>>> data = MyStruct.pack(23, False, 42.0)

# 得到的是一团内存中的数据:
>>> data
b'\x17\x00\x00\x00\x00\x00\x00\x00\x00\x00(B'

# 数据可以再次解包:
>>> MyStruct.unpack(data)
(23, False, 42.0)

5.3.7 types.SimpleNamespace——花哨的属性访问

这里再介绍一种高深的方法来在Python中创建数据对象:types.SimpleNamespace26。该类添加自Python 3.3,可以用属性访问的方式访问其名称空间。

26详见Python文档:“types.SimpleNamespace”。

也就是说,SimpleNamespace实例将其中的所有键都公开为类属性。因此访问属性时可以使用obj.key这样的点式语法,不需要用普通字典的obj['key']方括号索引语法。所有实例默认都包含一个不错的__repr__

正如其名,SimpleNamespace很简单,基本上就是扩展版的字典,能够很好地访问属性并以字符串打印出来,还能自由地添加、修改和删除属性。

>>> from types import SimpleNamespace
>>> car1 = SimpleNamespace(color='red',
...                        mileage=3812.4,
...                        automatic=True)

# 默认的__repr__效果:
>>> car1
namespace(automatic=True, color='red', mileage=3812.4)

# 实例支持属性访问并且是可变的:
>>> car1.mileage = 12
>>> car1.windshield = 'broken'
>>> del car1.automatic
>>> car1
namespace(color='red', mileage=12, windshield='broken')

5.3.8 关键要点

那么在Python中应该使用哪种类型的数据对象呢?从上面可以看到,Python中有许多不同的方法实现记录或数据对象,使用哪种方式通常取决于具体的情况。

如果只有两三个字段,字段顺序易于记忆或无须使用字段名称,则使用简单元组对象。例如三维空间中的(x, y, z)点。

如果需要实现含有不可变字段的数据对象,则使用collections.namedtupletyping.NamedTuple这样的简单元组。

如果想锁定字段名称来避免输入错误,同样建议使用collections.namedtupletyping.NamedTuple

如果希望保持简单,建议使用简单的字典对象,其语法方便,和JSON也类似。

如果需要对数据结构完全掌控,可以用@property加上设置方法和获取方法来编写自定义的类。

如果需要向对象添加行为(方法),则应该从头开始编写自定义类,或者通过扩展collections.namedtupletyping.NamedTuple来编写自定义类。

如果想严格打包数据以将其序列化到磁盘上或通过网络发送,建议使用struct.Struct

一般情况下,如果想在Python中实现一个普通的记录、结构体或数据对象,我的建议是在{\rm Python}~2.x中使用collections.namedtuple,在Python 3中使用其姊妹typing.NamedTuple

5.4 集合和多重集合

本节将用标准库中的内置数据类型和类在Python中实现可变集合、不可变集合和多重集合(背包)数据结构。首先来快速回顾一下集合数据结构。

集合含有一组不含重复元素的无序对象。集合可用来快速检查元素的包含性,插入或删除值,计算两个集合的并集或交集。

在“合理”的集合实现中,成员检查预计耗时为O(1)。并集、交集、差集和子集操作应平均耗时为O(n)。Python标准库中的集合实现都具有这些性能指标。27

27详见wiki.python.org/moin/TimeComplexity。

与字典一样,集合在Python中也得到了特殊对待,有语法糖能够方便地创建集合。例如,花括号集合表达式语法和集合解析式能够方便地定义新的集合实例:

vowels = {'a', 'e', 'i', 'o', 'u'}
squares = {x * x for x in range(10)}

但要小心,创建空集时需要调用set()构造函数。空花括号{}有歧义,会创建一个空字典。

Python及其标准库提供了几个集合实现,让我们看看。

5.4.1 set——首选集合实现

set是Python中的内置集合实现。28set类型是可变的,能够动态插入和删除元素。

28详见Python文档:“set”。

Python的集合由dict数据类型支持,具有相同的性能特征。所有可散列29的对象都可以存储在集合中。

29详见Python文档:“hashable”。

>>> vowels = {'a', 'e', 'i', 'o', 'u'}
>>> 'e' in vowels
True

>>> letters = set('alice')
>>> letters.intersection(vowels)
{'a', 'e', 'i'}

>>> vowels.add('x')
>>> vowels
{'i', 'a', 'u', 'o', 'x', 'e'}

>>> len(vowels)
6

5.4.2 frozenset——不可变集合

frozenset类实现了不可变版的集合,即在构造后无法更改。30不可变集合是静态的,只能查询其中的元素(无法插入或删除)。因为不可变集合是静态的且可散列的,所以可以用作字典的键,也可以放置在另一个集合中,普通可变的set对象做不到这一点。

30详见Python文档:“frozenset”。

>>> vowels = frozenset({'a', 'e', 'i', 'o', 'u'})
>>> vowels.add('p')
AttributeError:
"'frozenset' object has no attribute 'add'"

# 不可变集合是可散列的,可用作字典的键
>>> d = { frozenset({1, 2, 3}): 'hello' }
>>> d[frozenset({1, 2, 3})]
'hello'

5.4.3 collections.Counter——多重集合

Python标准库中的collections.Counter类实现了多重集合(也称背包,bag)类型,该类型允许在集合中多次出现同一个元素。31

31详见Python文档:“collections.Counter”。

如果既要检查元素是否为集合的一部分,又要记录元素在集合中出现的次数,那么就需要用到这个类型。

>>> from collections import Counter
>>> inventory = Counter()

>>> loot = {'sword': 1, 'bread': 3}
>>> inventory.update(loot)
>>> inventory
Counter({'bread': 3, 'sword': 1})

>>> more_loot = {'sword': 1, 'apple': 1}
>>> inventory.update(more_loot)
>>> inventory
Counter({'bread': 3, 'sword': 2, 'apple': 1})

Counter类有一点要注意,在计算Counter对象中元素的数量时需要小心。调用len()返回的是多重集合中唯一元素的数量,而想获取元素的总数需要使用sum函数:

>>> len(inventory)
3 # 唯一元素的个数

>>> sum(inventory.values())
6 # 元素总数

5.4.4 关键要点

  • 集合是Python及其标准库中含有的另一种有用且常用的数据结构。
  • 查找可变集合时可使用内置的set类型。
  • frozenset对象可散列且可用作字典和集合的键。
  • collections.Counter实现了多重集合或“背包”类型的数据。

5.5 栈(后进先出)

栈是含有一组对象的容器,支持快速后进先出(LIFO)的插入和删除操作。与列表或数组不同,栈通常不允许随机访问所包含的对象。插入和删除操作通常称为入栈(push)和出栈(pop)。

现实世界中与栈数据结构相似的是一叠盘子。

新盘子会添加到栈的顶部。由于这些盘子非常宝贵且很重,所以只能移动最上面的盘子(后进先出)。要到达栈中位置较低的盘子,必须逐一移除最顶端的盘子。

栈和队列相似,都是线性的元素集合,但元素的访问顺序不同。

队列删除元素时,移除的是最先添加的项(先进先出,FIFO);而是移除最近添加的项(后进先出,LIFO)。

在性能方面,合理的栈实现在插入和删除操作的预期耗时是O(1)

栈在算法中有广泛的应用,比如用于语言解析和运行时的内存管理(“调用栈”)。树或图数据结构上的深度优先搜索(DFS)是简短而美丽的算法,其中就用到了栈。

Python中有几种栈实现,每个实现的特性略有不同。下面来分别介绍并比较各自的特性。

5.5.1 列表——简单的内置栈

Python的内置列表类型能在正常的O(1)时间内完成入栈和出栈操作,因此适合作为栈数据结构。32

32详见Python文档:“Using lists as stacks”。

Python的列表在内部以动态数组实现,这意味着在添加或删除时,列表偶尔需要调整元素的存储空间大小。列表会预先分配一些后备存储空间,因此并非每个入栈或出栈操作都需要调整大小,所以这些操作的均摊时间复杂度为O(1)

这么做的缺点是列表的性能不如基于链表的实现(如collections.deque,下面会介绍),后者能为插入和删除操作提供稳定的O(1)时间复杂度。另一方面,列表能在O(1)时间快速随机访问堆栈上的元素,这能带来额外的好处。

使用列表作为堆栈应注意下面几个重要的性能问题。

为了获得O(1)的插入和删除性能,必须使用append()方法将新项添加到列表的末尾,删除时也要使用pop()从末尾删除。为了获得最佳性能,基于Python列表的栈应该向高索引增长并向低索引缩小。

从列表前部添加和删除元素很慢,耗时为O(n),因为这种情况下必须移动现有元素来为新元素腾出空间。这是一个性能反模式,应尽可能避免。

>>> s = []
>>> s.append('eat')
>>> s.append('sleep')
>>> s.append('code')

>>> s
['eat', 'sleep', 'code']

>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'

>>> s.pop()
IndexError: "pop from empty list"

5.5.2 collections.deque——快速且稳健的栈

deque类实现了一个双端队列,支持在O(1)时间(非均摊)从两端添加和移除元素。因为双端队列支持从两端添加和删除元素,所以既可以作为队列也可以作为栈。33

33详见Python文档:“collections.deque”。

Python的deque对象以双向链表实现,这为插入和删除元素提供了出色且一致的性能,但是随机访问位于栈中间元素的性能很差,耗时为O(n)34

34详见CPython源码:_collectionsmodule.c

总之,如果想在Python的标准库中寻找一个具有链表性能特征的栈数据结构实现,那么collections.deque是不错的选择。

>>> from collections import deque
>>> s = deque()
>>> s.append('eat')
>>> s.append('sleep')
>>> s.append('code')

>>> s
deque(['eat', 'sleep', 'code'])

>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'

>>> s.pop()
IndexError: "pop from an empty deque"

5.5.3 queue.LifoQueue——为并行计算提供锁语义

queue.LifoQueue这个位于Python标准库中的栈实现是同步的,提供了锁语义来支持多个并发的生产者和消费者。35

35详见Python文档:“queue.LifoQueue”。

除了LifoQueue之外,queue模块还包含其他几个类,都实现了用于并行计算的多生产者/多用户队列。

在不同情况下,锁语义即可能会带来帮助,也可能会导致不必要的开销。在后面这种情况下,最好使用listdeque作为通用栈。

>>> from queue import LifoQueue
>>> s = LifoQueue()
>>> s.put('eat')
>>> s.put('sleep')
>>> s.put('code')

>>> s
<queue.LifoQueue object at 0x108298dd8>

>>> s.get()
'code'
>>> s.get()
'sleep'
>>> s.get()
'eat'

>>> s.get_nowait()
queue.Empty

>>> s.get()
# 阻塞,永远停在这里……

5.5.4 比较Python中各个栈的实现

从上面可以看出,Python中有多种栈数据结构的实现,各自的特性稍有区别,在性能和用途上也各有优劣。

如果不寻求并行处理支持(或者不想手动处理上锁和解锁),可选择内置列表类型或collections.deque。两者背后使用的数据结构和总体易用性有所不同。

  • 列表底层是动态数组,因此适用于快速随机访问,但在添加或删除元素时偶尔需要调整大小。列表会预先分配一些备用存储空间,因此不是每个入栈或出栈操作都需要调整大小,这些操作的均摊时间复杂度为O(1)。但需要小心,只能用append()pop()从“右侧”插入和删除元素,否则性能会下降为O(n)
  • collections.deque底层是双向链表,为从两端的添加和删除操作进行了优化,为这些操作提供了一致的O(1)性能。collections.deque不仅性能稳定,而且便于使用,不必担心在“错误的一端”添加或删除项。

总之,我认为collections.deque是在Python中实现栈(LIFO队列)的绝佳选择。

5.5.5 关键要点

  • Python中有几个栈实现,每种实现的性能和使用特性略有不同。
  • collections.deque提供安全且快速的通用栈实现。
  • 内置列表类型可以作为栈使用,但要小心只能使用append()pop()来添加和删除项,以避免性能下降。

5.6 队列(先进先出)

本节将介绍仅使用Python标准库中的内置数据类型和类来实现FIFO队列数据结构,首先来回顾一下什么是队列。

队列是含有一组对象的容器,支持快速插入和删除的先进先出语义。插入和删除操作有时称为入队(enqueue)和出队(dequeue)。与列表或数组不同,队列通常不允许随机访问所包含的对象。

来看一个先进先出队列在现实中的类比。

想象在PyCon注册的第一天,一些Python高手等着领取会议徽章。新到的人依次进入会场并排队领取徽章,队列后面会有其他人继续排队。移除动作发生在队列前端,因为开发者领取徽章和会议礼品袋后就离开了。

另一种记住队列数据结构特征的方法是将其视为管道

新元素(水分子、乒乓球等)从管道一端移向另一端并在那里被移除。当元素在队列中(想象成位于一根坚固的金属管中)时是无法接触的。唯一能够与队列中元素交互的方法是在管道后端添加新元素(入队)或在管道前端删除元素(出队)。

队列与栈类似,但删除元素的方式不同。

队列删除的是最先添加的项(先进先出),而栈删除的是最近添加的项(后进先出)。

在性能方面,实现合理的队列在插入和删除方面的操作预计耗时为O(1)。插入和删除是队列上的两个主要操作,在正确的实现中应该很快。

队列在算法中有广泛的应用,经常用于解决调度和并行编程问题。在树或图数据结构上进行宽度优先搜索(BFS)是一种简短而美丽的算法,其中就用到了队列。

调度算法通常在内部使用优先级队列。这些是特化的队列,其中元素的顺序不是基于插入时间,而是基于优先级。队列根据元素的键计算到每个元素的优先级。下一节详细介绍优先级队列以及它们在Python中的实现方式。

不过普通队列无法重新排列所包含的元素。就像在管道示例中一样,元素输入和输出的顺序完全一致。

Python中实现了几个队列,每种实现的特征略有不同,下面就来看看。

5.6.1 列表——非常慢的队列

普通列表可以作为队列,但从性能角度来看并不理想。36由于在起始位置插入或删除元素需要将所有其他元素都移动一个位置,因此需要的时间为O(n)

36详见Python文档:“Using lists as queues”。

因此不推荐在Python中凑合用列表作为队列使用(除非只处理少量元素):

>>> q = []
>>> q.append('eat')
>>> q.append('sleep')
>>> q.append('code')

>>> q
['eat', 'sleep', 'code']

# 小心,这种操作很慢!
>>> q.pop(0)
'eat'

5.6.2 collections.deque——快速和稳健的队列

deque类实现了一个双端队列,支持在O(1)时间(非均摊)中从任一端添加和删除元素。由于deque支持从两端添加和移除元素,因此既可用作队列也可用作栈。37

37详见Python文档:“collections.deque”。

Python的deque对象以双向链表实现。38这为插入和删除元素提供了出色且一致的性能,但是随机访问位于栈中间元素的性能很差,耗时为O(n)

38CPython源码:_collectionsmodule.c

因此,默认情况下collections.deque是Python标准库中不错的队列型数据结构:

>>> from collections import deque
>>> q = deque()
>>> q.append('eat')
>>> q.append('sleep')
>>> q.append('code')

>>> q
deque(['eat', 'sleep', 'code'])

>>> q.popleft()
'eat'
>>> q.popleft()
'sleep'
>>> q.popleft()
'code'

>>> q.popleft()
IndexError: "pop from an empty deque"

5.6.3 queue.Queue——为并行计算提供的锁语义

queue.Queue在Python标准库中以同步的方式实现,提供了锁语义来支持多个并发的生产者和消费者。39

39详见Python文档:“queue.Queue”。

queue模块包含其他多个实现多生产者/多用户队列的类,这些队列对并行计算很有用。

在不同情况下,锁语义可能会带来帮助,也可能会导致不必要的开销。在后面这种情况下,最好使用collections.deque作为通用队列:

>>> from queue import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')

>>> q
<queue.Queue object at 0x1070f5b38>

>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'

>>> q.get_nowait()
queue.Empty

>>> q.get()
# 阻塞,永远停在这里……

5.6.4 multiprocessing.Queue——共享作业队列

multiprocessing.Queue作为共享作业队列来实现,允许多个并发worker并行处理队列中的元素。40由于CPython中存在全局解释器锁(GIL),因此无法在单个解释器进程上执行某些并行化过程,使得大家都转向基于进程的并行化。

40详见Python文档:“multiprocessing.Queue”。

作为专门用于在进程间共享数据的队列实现,使用multiprocessing.Queue能够方便地在多个进程中分派工作,以此来绕过GIL的限制。这种类型的队列可以跨进程存储和传输任何可pickle的对象:

>>> from multiprocessing import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')

>>> q
<multiprocessing.queues.Queue object at 0x1081c12b0>

>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'

>>> q.get()
# 阻塞,永远停在这里……

5.6.5 关键要点

  • Python核心语言及其标准库中含有几种队列实现。
  • 列表对象可以用作队列,但由于性能较差,通常不建议这么做。
  • 如果不需要支持并行处理,那么collections.deque是Python中实现FIFO队列数据结构的最佳选择。collections.deque是非常优秀的队列实现,具备期望的性能特征,并且可以用作栈(LIFO队列)。

5.7 优先队列

优先队列是一个容器数据结构,使用具有全序关系41的键(例如用数值表示的权重)来管理元素,以便快速访问容器中键值最小最大的元素。

41详见维基百科“全序关系”。

优先队列可被视为队列的改进版,其中元素的顺序不是基于插入时间,而是基于优先级的。对键进行处理能得到每个元素的优先级。

优先级队列通常用于处理调度问题,例如优先考虑更加紧急的任务。

来看看操作系统任务调度器的工作。

理想情况下,系统上的高优先级任务(如玩实时游戏)级别应高于低优先级的任务(如在后台下载更新)。优先级队列将待执行的任务根据紧急程度排列,任务调度程序能够快速选取并优先执行优先级最高的任务。

本节将介绍如何使用Python语言内置或位于标准库中的数据结构来实现优先队列。每种实现都有各自的优缺点,但其中有一种实现能应对大多数常见情况,下面一起来看看。

5.7.1 列表——手动维护有序队列

使用有序列表能够快速识别并删除最小或最大的元素,缺点是向列表插入元素表是很慢的O(n)操作。

虽然用标准库中的bisect.insort42能在O(\log n)时间内找到插入位置,但缓慢的插入操作才是瓶颈。

42详见Python文档:“bisect.insort”。

向列表添加并重新排序来维持顺序也至少需要O(n\log n)的时间。另一个缺点是在插入新元素时,必须手动重新排列列表。缺少这一步就很容易引入bug,因此担子总是压在开发人员身上。

因此,有序列表只适合在插入次数很少的情况下充当优先队列。

q = []

q.append((2, 'code'))
q.append((1, 'eat'))
q.append((3, 'sleep'))

# 注意:每当添加新元素或调用bisect.insort()时,都要重新排序。
q.sort(reverse=True)

while q:
    next_item = q.pop()
    print(next_item)

# 结果:
#   (1, 'eat')
#   (2, 'code')
#   (3, 'sleep')

5.7.2 heapq——基于列表的二叉堆

heapq是二叉堆,通常用普通列表实现,能在O(\log n)时间内插入和获取最小的元素。43

43详见Python文档:“heapq”。

heapq模块是在Python中不错的优先级队列实现。由于heapq在技术上只提供最小堆实现,因此必须添加额外步骤来确保排序稳定性,以此来获得“实际”的优先级队列中所含有的预期特性。44

44详见Python文档:“heapq - Priority queue implementation notes”。

import heapq

q = []

heapq.heappush(q, (2, 'code'))
heapq.heappush(q, (1, 'eat'))
heapq.heappush(q, (3, 'sleep'))

while q:
    next_item = heapq.heappop(q)
    print(next_item)

# 结果:
#   (1, 'eat')
#   (2, 'code')
#   (3, 'sleep')

5.7.3 queue.PriorityQueue——美丽的优先级队列

queue.PriorityQueue这个优先级队列的实现在内部使用了heapq,时间和空间复杂度与heapq相同。45

45详见Python文档:“queue.PriorityQueue”。

区别在于PriorityQueue是同步的,提供了锁语义来支持多个并发的生产者和消费者。

在不同情况下,锁语义可能会带来帮助,也可能会导致不必要的开销。不管哪种情况,你都可能更喜欢PriorityQueue提供的基于类的接口,而不是使用heapq提供的基于函数的接口。

from queue import PriorityQueue

q = PriorityQueue()

q.put((2, 'code'))
q.put((1, 'eat'))
q.put((3, 'sleep'))

while not q.empty():
    next_item = q.get()
    print(next_item)

# 结果:
#   (1, 'eat')
#   (2, 'code')
#   (3, 'sleep')

5.7.4 关键要点

  • Python提供了几种优先队列实现可以使用。
  • queue.PriorityQueue是其中的首选,具有良好的面向对象的接口,从名称就能明白其用途。
  • 如果想避免queue.PriorityQueue的锁开销,那么建议直接使用heapq模块。

目录