4.8　实例方法、类方法和静态方法揭秘

本节将深入探寻Python中的类方法 、静态方法 和普通实例方法 。
在对这些方法之间的差异有直观的理解后，就能以面向对象的形式编写Python代码了，从而更清楚地传达代码的意图，而且从长远来看代码更易维护。
首先来编写一个类，其中包含这三种方法的简单示例（Python 3版）：

class MyClass:
    def method(self):
        return 'instance method called', self
    @classmethod
    def classmethod(cls):
        return 'class method called', cls
    @staticmethod
    def staticmethod():
        return 'static method called'

Python 2用户需要注意 ：从Python 2.4开始才可以使用@staticmethod 和@classmethod 装饰器，因此此后的版本才能运行这个示例。另外，还需要使用class MyClass(object) 这种语法来声明这是继承自object 的新式类，而不是使用普通的class MyClass 语法。除了这些之外就没有其他问题了。

4.8.1　实例方法

MyClass 上的第一种方法名为method ，这是一个普通的实例方法 。代码中一般出现的都是这种简单基础的实例方法。method 方法需要一个参数self ，在调用时指向MyClass 的一个实例。当然，实例方法可以接受多个参数。
实例方法通过self 参数在同一个对象上自由访问该对象的其他属性和方法，因此特别适合修改对象的状态。
实例方法不仅可以修改对象状态，也可以通过self.__class__ 属性访问类本身。这意味着实例方法也可以修改类的状态。

4.8.2　类方法

与第一种方法相比，第二种方法MyClass.classmethod 使用了@classmethod 装饰器7 ，将其标记为类方法 。
7 详见Python文档：“@classmethod ”。
类方法并不接受self 参数，而是在调用方法时使用cls 参数指向类（不是对象实例）。
由于类方法只能访问这个cls 参数，因此无法修改对象实例的状态，这需要用到self 。但类方法可以修改应用于类所有实例的类状态。

4.8.3　静态方法

第三种方法MyClass.staticmethod 使用@staticmethod 装饰器8 将其标记为静态方法 。
8 详见Python 文档：“@staticmethod ”。
这种类型的方法不接受self 或cls 参数，但可以接受任意数量的其他参数。
因此，静态方法不能修改对象状态或类状态，仅能访问特定的数据，主要用于声明属于某个命名空间的方法。

4.8.4　在实践中探寻

到目前为止都是非常理论化的讨论，而重要的是在实践中直观地理解这些方法之间的区别，因此这里来介绍一些具体的例子。
让我们来看看调用这些方法时其各自的行为。首先创建一个类的实例，然后调用三种不同的方法。
MyClass 中进行了一些设置，其中每个方法的实现都会返回一个元组，包含当前方法的说明信息和该方法可访问的类或对象的内容。
以下是调用实例方法 时的情况：

>>> obj = MyClass()
>>> obj.method()
('instance method called', <MyClass instance at 0x11a2>)

从中可以确认，名为method 的实例方法可以通过self 参数访问对象实例（输出为<MyClass instance> ）。
调用该方法时，Python用实例对象obj 替换self 变量。如果不用obj.method() 这种点号调用语法糖，手动 传递实例对象也会获得相同的结果：

>>> MyClass.method(obj)
('instance method called', <MyClass instance at 0x11a2>)

顺便说一下，在实例方法中也可以通过self.__class__ 属性访问类本身 。这使得实例方法在访问方面几乎没什么限制，可以自由修改对象实例和类本身的状态。
接下来尝试一下类方法 ：

>>> obj.classmethod()
('class method called', <class MyClass at 0x11a2>)

调用classmethod() 的结果表明其不能访问<MyClass instance> 对象，只能访问<class MyClass> 对象，这个对象用来表示类本身（Python中一切皆为对象，类本身也是对象）。
注意，在调用MyClass.classmethod() 时，Python自动将类作为第一个参数传递给该函数。在Python中用点语法 （dot syntax）调用该方法就会触发这个行为。实例方法的self 参数的工作方式也是如此。
注意，self 和cls 这些参数的命名只是一个约定。你可以将其命名为the_object 和the_class ，结果相同，只要这些参数位于相关方法中参数列表的第一个位置即可。
现在来调用静态方法 ：

>>> obj.staticmethod()
'static method called'

注意到没有，在对象上可以调用staticmethod() 。有些开发人员在得知可以在对象实例上调用静态方法时会感到惊讶。
从实现上来说，Python在使用点语法调用静态方法时不会传入self 或cls 参数，从而限制了静态方法访问的内容。
这意味着静态方法既不能访问对象实例状态，也不能访问类的状态。静态方法与普通函数一样，但属于类（和每个实例）的名称空间。
现在不创建对象实例，看看在类本身上调用静态方法时会发生什么：

>>> MyClass.classmethod()
('class method called', <class MyClass at 0x11a2>)
>>> MyClass.staticmethod()
'static method called'
>>> MyClass.method()
TypeError: """unbound method method() must be
    called with MyClass instance as first
    argument (got nothing instead)"""

调用classmethod() 和staticmethod() 没有问题，但试图调用实例方法method() 会失败并出现TypeError 。
这是预料之中的。由于没有创建对象实例，而是直接在类蓝图（blueprint）上调用实例方法，意味着Python无法填充self 参数，因此调用实例方法method 会失败并抛出TypeError 异常。
通过这些实验，你应该更清楚这三种方法类型之间的区别了。别担心，现在还不会结束这个话题。在接下来的两节中，还将用两个更接近实际的例子来使用这些特殊方法。
下面以前面的例子为基础，创建一个简单的Pizza 类：

class Pizza:
    def __init__(self, ingredients):
        self.ingredients = ingredients
    def __repr__(self):
        return f'Pizza({self.ingredients!r})'
>>> Pizza(['cheese', 'tomatoes'])
Pizza(['cheese', 'tomatoes'])

4.8.5　使用@classmethod 的Pizza 工厂类

如果你在现实世界中吃过比萨，那么就会知道比萨有很多种口味可供选择：

Pizza(['mozzarella', 'tomatoes'])
Pizza(['mozzarella', 'tomatoes', 'ham', 'mushrooms'])
Pizza(['mozzarella'] * 4)

几个世纪以前，意大利人就对比萨进行了分类，所以这些美味的比萨饼都有自己的名字。下面根据这个特性为Pizza 类提供更好的接口，让用户能创建所需的比萨对象。
使用类方法作为工厂函数9 能够简单方便地创建不同种类的比萨：
9 详见维基百科：“工厂（面向对象编程）”。

class Pizza:
    def __init__(self, ingredients):
        self.ingredients = ingredients
    def __repr__(self):
        return f'Pizza({self.ingredients!r})'
    @classmethod
    def margherita(cls):
        return cls(['mozzarella', 'tomatoes'])
    @classmethod
    def prosciutto(cls):
        return cls(['mozzarella', 'tomatoes', 'ham'])

注意我们在margherita 和prosciutto 工厂方法中使用了cls 参数，而没有直接调用Pizza 构造函数。
这个技巧遵循了“不要重复自己”（DRY）10 原则。如果打算在将来重命名这个类，就不必更新所有工厂函数中的构造函数名称。
10 详见维基百科：“Don’t repeat yourself”。
那么这些工厂方法能做什么？来尝试一下：

>>> Pizza.margherita()
Pizza(['mozzarella', 'tomatoes'])
>>> Pizza.prosciutto()
Pizza(['mozzarella', 'tomatoes', 'ham'])

从中可以看到，工厂函数创建的新Pizza 对象按照期望的方式进行了配置，这些函数在内部都使用相同的__init__ 构造函数，作为一种快捷的方式来记录不同的配方。
从另一个角度来说，这些类方法为类定义了额外的构造函数。
Python只允许每个类有一个__init__ 方法。使用类方法可以按需添加额外的构造函数，使得类的接口在一定程度上能做到“自说明”，同时简化了类的使用。

4.8.6　什么时候使用静态方法

为这个主题提供一个好例子有点难，所以继续使用前面的比萨例子，把比萨烤得越来越薄……（要流口水了！）
下面是我想到的：

import math
class Pizza:
    def __init__(self, radius, ingredients):
        self.radius = radius
        self.ingredients = ingredients
    def __repr__(self):
        return (f'Pizza({self.radius!r}, '
                f'{self.ingredients!r})')
    def area(self):
        return self.circle_area(self.radius)
    @staticmethod
    def circle_area(r):
        return r ** 2 * math.pi

这里做了哪些改动呢？
首先，修改了构造函数和__repr__ 以接受额外的radius 参数。
其次，添加了一个area() 实例方法用于计算并返回比萨的面积。虽然这里更适合使用@property 装饰器，不过对于这个简单的示例来说，那么做的话就有些大动干戈了。
area() 并没有直接计算面积，而是调用circle_area() 静态方法，后者使用众所周知的圆面积公式来计算。
下面来试试吧！

>>> p = Pizza(4, ['mozzarella', 'tomatoes'])
>>> p
Pizza(4, {self.ingredients})
>>> p.area()
50.26548245743669
>>> Pizza.circle_area(4)
50.26548245743669

当然这仍然是一个简单的例子，不过有助于说明静态方法的好处。
之前已经介绍了，静态方法不能访问类或实例的状态，因为静态方法不会接受cls 或self 参数。这是一个很大的局限性，但也很好地表明了静态方法与类的其他所有内容都无关。
在上面的例子中，很明显circle_area() 不能以任何方式修改类或类实例。（当然，你可以用全局变量来解决这个问题，不过这不是重点。）
那么这种功能有什么用呢？
将方法标记为静态方法不仅是一种提示，告诉大家这个方法不会修改类或实例状态，而且从上面可以看到，Python运行时也会实际落实这些限制。
通过这样的技术可以清晰地识别出类架构的各个部分，因而新的开发工作能够很自然地分配到对应的部分中。虽然不遵守这种限制也没什么大问题，但在实践中常常能避免与原始设计相悖的意外修改。
换句话说，使用静态方法和类方法不仅能传达开发人员的意图，还能够强制贯彻设计思路，避免许多心不在焉的错误以及会破坏设计的bug。
因此请谨慎地按需使用静态方法，添加静态方法对代码维护有好处，能避免其他开发人员误用你的类。
静态方法也有助于编写测试代码。由于circle_area() 方法与类的其余部分完全独立，因此测试起来更加容易。
在单元测试中测试静态方法时不需要建立完整的类实例，可以像测试普通函数那样直接测试静态方法。这不仅简化了维护，而且在面向对象和面向过程的编程风格之间建立了联系。

4.8.7　关键要点

• 实例方法需要一个类实例，可以通过self 访问实例。
• 类方法不需要类实例，不能访问实例（self ），但可以通过cls 访问类本身。
• 静态方法不能访问cls 或self ，其作用和普通函数相同，但属于类的名称空间。
• 静态方法和类方法能（在一定程度上）展示和贯彻开发人员对类的设计意图，有助于代码维护。

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

  有没有什么是每个Python开发者都应该进一步练习和学习的呢？
  那就是数据结构。数据结构是构建程序的基础。各个数据结构在组织方式上有自己的特点，以便在不同情况下高效访问数据。
  我相信无论程序员的技术水平或经验如何，掌握一些基本功总是有好处的。
  我并不主张只专注于掌握更多的数据结构知识，这是一种“失效模式”（failure mode），只会让人陷入假想理论上的幻境，而不会带来任何实际的结果。
  不过花一些时间来补习数据结构（和算法）的知识总会有好处。
  无论是花几天时间“突击”，还是利用零碎的时间持续学习，在数据结构上下点功夫都是值得的。
  那么Python中有哪些数据结构呢？列表、字典、集合，还有……栈？Python有栈吗？
  看到没？Python在其标准库中提供了大量的数据结构，但问题在于各自的命名有点词不达意。
  举例来说，很多人甚至不清楚Python是否具体实现了像栈这样著名的“抽象数据类型”。相比之下，Java等其他语言则更“计算机科学化”，其中的命名很明确。比如，Java中的列表还细分成了LinkedList 和ArrayList 。
  这种细分的命名便于我们识别各个数据类型的预期行为和计算复杂度。Python也倾向于使用简单且“人性化”的命名方案。我喜欢Python的方案，因为人性化也是Python编程更有趣的原因之一。
  这种方案的缺点在于，即使是经验丰富的Python开发人员，也不清楚内置的列表类型是以链表还是动态数组实现的。如果需要用到这些知识却没有掌握，则会让人感到沮丧，也可能导致面试被拒。
  本章将介绍Python及其标准库内置的基本数据结构和抽象数据类型的实现。
  我的目标是阐释常见的抽象数据类型在Python中对应的名称及实现，并逐个进行简单的介绍。这些内容也会帮助你在Python面试中大放异彩。
  如果你正在寻找一本能够用来温习通用数据结构知识的好书，我强烈推荐Steven S. Skiena的《算法设计手册》。
  这本书介绍了各种数据结构及其各自在不同算法中的实际应用，并在这两个方面之间取得了很好的平衡。它对我编写本章提供了很大的帮助。

  5.1　字典、映射和散列表

  在Python中，字典是核心数据结构。字典可以存储任意数量的对象，每个对象都由唯一的字典键 标识。
  字典通常也被称为映射 、散列表 、查找表 或关联数组 。字典能够高效查找、插入和删除任何与给定键关联的对象。
  这在现实中意味着什么呢？字典对象相当于现实世界中的电话簿。

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

若想研究以何种方式组织信息才有利于快速检索，上述类比就不那么贴切了。但基本性能特征相同，即字典能够用来快速查找与给定键相关的信息。
总之，字典是计算机科学中最常用且最重要的数据结构之一。
那么Python如何处理字典呢？
我们来看看Python及其标准库中可用的字典实现。

5.1.1　dict ——首选字典实现

由于字典非常重要，因此Python直接在语言核心中实现了一个稳健的字典1 ：dict 数据类型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字典基于经过充分测试和精心调整过的散列表实现，提供了符合期望的性能特征。一般情况下，用于查找、插入、更新和删除操作的时间复杂度都为 。
大部分情况下，应该使用Python自带的标准字典实现。但是也存在专门的第三方字典实现，例如跳跃表4 或基于B树的字典。
4 一种数据结构，详见http://www.cl.cam.ac.uk/teaching/0506/Algorithms/skiplists.pdf 。——译者注
除了通用的dict 对象外，Python的标准库还包含许多特殊的字典实现。它们都基于内置的字典类，基本性能特征相同，但添加了其他一些便利特性。
下面来逐个了解一下。

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

collections.OrderedDict 5 是特殊的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标准库包含的功能。
  本章还会介绍每种实现的优缺点，这样就能根据实际情况选择合适的实现。不过在介绍之前，先来了解一些基础知识。
  首先要知道数组的原理及用途。
  数组由大小固定的数据记录组成，根据索引能快速找到其中的每个元素。
  因为数组将信息存储在依次连接的内存块中，所以它是连续 的数据结构（与链式列表等链式数据结构不同）。
  现实世界中能用来类比数组数据结构的是停车场。

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

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

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

在性能方面，根据元素的索引能快速查找数组中对应的元素。合理的数组实现能够确保索引访问的耗时为常量时间。
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字符的不可变数组

Python3.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 从概念上讲，bytes 与str 对象类似，可认为是不可变的字节数组。
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（含）。bytearray 与bytes 对象关系密切，主要区别在于bytearray 可以自由修改，如覆盖、删除现有元素和添加新元素，此时bytearray 对象将相应地增长和缩小。
16 详见Python文档：“bytearray ”。
bytearray 数可以转换回不可变的bytes 对象，但是这需要复制所存储的数据，是耗时为 的慢操作。

>>> 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 指只含有数据本身，不含有业务逻辑的数据类型，参见https://en.wikipedia.org/wiki/Plain_old_Java_object 。
顺便说一句，这里的“记录”定义很宽泛。例如，这里也会介绍像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.c 和listobject.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.Struct 类25 用于在Python值和C结构体之间转换，并将其序列化为Python字节对象。例如可以用来处理存储在文件中或来自网络连接的二进制数据。
25 详见Python文档：“struct.Struct ”。
结构体使用与格式化字符串类似的语法来定义，能够定义并组织各种C数据类型（如char 、int 、long ，以及对应的无符号的变体）。
序列化结构体一般不用来表示只在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.SimpleNamespace 26 。该类添加自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.namedtuple 或typing.NamedTuple 这样的简单元组。
如果想锁定字段名称来避免输入错误 ，同样建议使用collections.namedtuple 和typing.NamedTuple 。
如果希望保持简单 ，建议使用简单的字典对象，其语法方便，和JSON也类似。
如果需要对数据结构完全掌控 ，可以用@property 加上设置方法和获取方法来编写自定义的类。
如果需要向对象添加行为（方法） ，则应该从头开始编写自定义类，或者通过扩展collections.namedtuple 或typing.NamedTuple 来编写自定义类。
如果想严格打包数据以将其序列化到磁盘上或通过网络发送 ，建议使用struct.Struct 。
一般情况下，如果想在Python中实现一个普通的记录、结构体或数据对象，我的建议是在Python2.x 中使用collections.namedtuple ，在Python 3中使用其姊妹typing.NamedTuple 。

5.4　集合和多重集合

本节将用标准库中的内置数据类型和类在Python中实现可变集合、不可变集合和多重集合（背包）数据结构。首先来快速回顾一下集合数据结构。
集合 含有一组不含重复元素的无序对象。集合可用来快速检查元素的包含性，插入或删除值，计算两个集合的并集或交集。
在“合理”的集合实现中，成员检查预计耗时为 。并集、交集、差集和子集操作应平均耗时为 。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中的内置集合实现。28 set 类型是可变的，能够动态插入和删除元素。
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）。
在性能方面，合理的栈实现在插入和删除操作的预期耗时是 。
栈在算法中有广泛的应用，比如用于语言解析和运行时的内存管理（“调用栈”）。树或图数据结构上的深度优先搜索（DFS）是简短而美丽的算法，其中就用到了栈。
Python中有几种栈实现，每个实现的特性略有不同。下面来分别介绍并比较各自的特性。

5.5.1　列表——简单的内置栈

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

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

Python的列表在内部以动态数组实现，这意味着在添加或删除时，列表偶尔需要调整元素的存储空间大小。列表会预先分配一些后备存储空间，因此并非每个入栈或出栈操作都需要调整大小，所以这些操作的均摊时间复杂度为 。
这么做的缺点是列表的性能不如基于链表的实现（如collections.deque ，下面会介绍），后者能为插入和删除操作提供稳定的 时间复杂度。另一方面，列表能在 时间快速随机访问堆栈上的元素，这能带来额外的好处。
使用列表作为堆栈应注意下面几个重要的性能问题。
为了获得 的插入和删除性能，必须使用append() 方法将新项添加到列表的末尾，删除时也要使用pop() 从末尾删除。为了获得最佳性能，基于Python列表的栈应该向高索引增长并向低索引缩小。
从列表前部添加和删除元素很慢，耗时为 ，因为这种情况下必须移动现有元素来为新元素腾出空间。这是一个性能反模式，应尽可能避免。

>>> 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 类实现了一个双端队列，支持在 时间（非均摊）从两端添加和移除元素。因为双端队列支持从两端添加和删除元素，所以既可以作为队列也可以作为栈。33

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

Python的deque 对象以双向链表实现，这为插入和删除元素提供了出色且一致的性能，但是随机访问位于栈中间元素的性能很差，耗时为 。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 模块还包含其他几个类，都实现了用于并行计算的多生产者/多用户队列。
在不同情况下，锁语义即可能会带来帮助，也可能会导致不必要的开销。在后面这种情况下，最好使用list 或deque 作为通用栈。

>>> 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 。两者背后使用的数据结构和总体易用性有所不同。

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

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

5.5.5　关键要点

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

  5.6　队列（先进先出）

  本节将介绍仅使用Python标准库中的内置数据类型和类来实现FIFO队列数据结构，首先来回顾一下什么是队列。
  队列是含有一组对象的容器，支持快速插入和删除的先进先出 语义。插入和删除操作有时称为入队 （enqueue）和出队 （dequeue）。与列表或数组不同，队列通常不允许随机访问所包含的对象。
  来看一个先进先出队列在现实中的类比。

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

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

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

队列与栈类似，但删除元素的方式不同。
队列 删除的是最先添加的项（先进先出 ），而栈删除的是最近添加的项（后进先出 ）。
在性能方面，实现合理的队列在插入和删除方面的操作预计耗时为 。插入和删除是队列上的两个主要操作，在正确的实现中应该很快。
队列在算法中有广泛的应用，经常用于解决调度和并行编程问题。在树或图数据结构上进行宽度优先搜索（BFS）是一种简短而美丽的算法，其中就用到了队列。
调度算法通常在内部使用优先级队列。这些是特化的队列，其中元素的顺序不是基于插入时间，而是基于优先级 。队列根据元素的键计算到每个元素的优先级。下一节详细介绍优先级队列以及它们在Python中的实现方式。
不过普通队列无法重新排列所包含的元素。就像在管道示例中一样，元素输入和输出的顺序完全一致。
Python中实现了几个队列，每种实现的特征略有不同，下面就来看看。

5.6.1　列表——非常慢的队列

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

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 类实现了一个双端队列，支持在 时间（非均摊）中从任一端添加和删除元素。由于deque 支持从两端添加和移除元素，因此既可用作队列也可用作栈。37

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

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

38 CPython源码：_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　列表——手动维护有序队列

使用有序列表能够快速识别并删除最小或最大的元素，缺点是向列表插入元素表是很慢的 操作。
虽然用标准库中的bisect.insort42 能在 时间内找到插入位置，但缓慢的插入操作才是瓶颈。

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

向列表添加并重新排序来维持顺序也至少需要 的时间。另一个缺点是在插入新元素时，必须手动重新排列列表。缺少这一步就很容易引入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 是二叉堆，通常用普通列表实现，能在 时间内插入和获取最小的元素。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 模块。