Python 附带了几个非常有用的集合，其中一些是基本的 Python 集合数据类型。其余的是这些类型的高级组合。在本章中，我们将解释其中的一些收藏，如何使用它们，以及它们各自的优缺点。
在正确讨论数据结构和相关性能之前，需要对时间复杂性（特别是大 O 表示法）有一个基本的了解。不用担心！这个概念非常简单，但如果没有它，我们就无法轻松解释操作的性能特征。
一旦大 O 符号明确，我们将讨论基本数据结构：
listdictsettuple
在基本数据结构的基础上，我们将继续使用更高级的集合，例如：
- 类似字典的类型：
ChainMapCounterDefaultdictOrderedDict
- 列表类型：
DequeHeapq
- 元组类型：
NamedTuple
- 其他类型：
Enum
在我们开始本章之前，您需要了解一个简单的符号。本章大量使用大 O 符号表示操作的时间复杂度。如果你已经熟悉这个符号，可以跳过这一段。虽然这个符号听起来很复杂，但这个概念实际上很简单。
当我们说一个函数需要O(1)时间时，这意味着它通常只需要1步执行。类似地，带有O(n)的函数将执行n步骤，其中n通常是对象的大小。这个时间复杂度只是执行代码时预期的基本指示，因为它通常是最重要的。
该系统的目的是指示操作的近似性能；这与代码速度无关，但仍然相关。一段代码执行单个步骤的速度要快1000倍，但需要O(2**n)步才能执行，这段代码仍然比另一个版本的代码慢，该版本的 n 等于10或更大，只需要O(n)步。这是因为n=10的2**n是2**10=1024，即执行相同代码的 1024 个步骤。这使得选择正确的算法非常重要。尽管C代码通常比 Python 快，但如果它使用了错误的算法，它将毫无帮助。
例如，假设您有一个1000项的列表，并遍历它们。这需要O(n)时间，因为有n=1000项。检查列表中是否存在项目需要O(n)，因此需要 1000 个步骤。这样做 100 次需要你100*O(n) = 100 * 1000 = 100,000步。当您将其与dict进行比较时，检查项目是否存在需要only O(1)时间，差异是巨大的。有了dict，就有100*O(1) = 100 * 1 = 100步了。因此，使用dict而不是list对于一个包含 1000 个项目的对象来说，速度大约要快 1000 倍：
n = 1000
a = list(range(n))
b = dict.fromkeys(range(n))
for i in range(100):
i in a # takes n=1000 steps
i in b # takes 1 step为了说明O(1)、O(n)和O(n**2)功能：
def o_one(items):
return 1 # 1 operation so O(1)
def o_n(items):
total = 0
# Walks through all items once so O(n)
for item in items:
total += item
return total
def o_n_squared(items):
total = 0
# Walks through all items n*n times so O(n**2)
for a in items:
for b in items:
total += a * b
return total
n = 10
items = range(n)
o_one(items) # 1 operation
o_n(items) # n = 10 operations
o_n_squared(items) # n*n = 10*10 = 100 operations需要注意的是，本章中的大 O 是关于平均情况，而不是最坏情况。在某些情况下，情况可能更糟，但在一般情况下，这些情况非常罕见，可以忽略不计。
在本章后面的中我们可以了解更高级的组合集合之前，您需要了解核心 Python 集合的工作原理。然而，这不仅仅与用法有关；它还涉及到所涉及的时间复杂性，这会严重影响应用在增长时的行为。如果您非常熟悉这些对象的时间复杂性，并且了解 Python 3 元组打包和解包的可能性，那么您可以跳到高级集合部分。
list很可能是 Python 中最常用的容器结构。它使用简单，在大多数情况下，它表现出良好的性能。
虽然您可能已经非常熟悉 list 的用法，但您可能没有意识到list对象的时间复杂性。幸运的是，list的许多时间复杂性非常低；append、get、set和len都尽可能地利用O(1)时间。但是，您可能没有意识到remove和insert具有O(n)时间复杂性。因此，要从 1000 个条目中删除一个条目，Python 必须遍历 1000 个条目。在内部，remove和insert操作沿着这条线执行某些操作：
>>> def remove(items, value):
... new_items = []
... found = False
... for item in items:
... # Skip the first item which is equal to value
... if not found and item == value:
... found = True
... continue
... new_items.append(item)
...
... if not found:
... raise ValueError('list.remove(x): x not in list')
...
... return new_items
>>> def insert(items, index, value):
... new_items = []
... for i, item in enumerate(items):
... if i == index:
... new_items.append(value)
... new_items.append(item)
... return new_items
>>> items = list(range(10))
>>> items
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> items = remove(items, 5)
>>> items
[0, 1, 2, 3, 4, 6, 7, 8, 9]
>>> items = insert(items, 2, 5)
>>> items
[0, 1, 5, 2, 3, 4, 6, 7, 8, 9]要从列表中删除或插入单个项目，Python 需要复制整个列表，对于较大的列表，这一点尤其重要。如果只执行一次，当然也没那么糟糕。但是当执行大量删除时，filter或list理解是更快的解决方案，因为如果结构正确，它只需要复制列表一次。例如，假设我们希望从列表中删除一组特定的数字。我们有很多选择。第一个是使用remove的解决方案，然后是列表理解，然后是filter语句。第 4 章函数式编程——可读性与简洁性将更详细地解释list理解和filter陈述。但首先，让我们看看这个例子：
>>> primes = set((1, 2, 3, 5, 7))
# Classic solution
>>> items = list(range(10))
>>> for prime in primes:
... items.remove(prime)
>>> items
[0, 4, 6, 8, 9]
# List comprehension
>>> items = list(range(10))
>>> [item for item in items if item not in primes]
[0, 4, 6, 8, 9]
# Filter
>>> items = list(range(10))
>>> list(filter(lambda item: item not in primes, items))
[0, 4, 6, 8, 9]对于大型项目列表，后两种方法要快得多。这是因为操作要快得多。比较使用n=len(items)和m=len(primes)时，第一个采用O(m*n)=5*10=50操作，而后两个采用O(n*1)=10*1=10操作。
第一种方法实际上略好于第二种方法，因为在循环过程中n会减少。所以，它实际上是10+9+8+7+6=40，但这是一个可以忽略的效应。在n=1000的情况下，这将是1000+999+998+997+996=4990和5*1000=5000之间的差异，在大多数情况下可以忽略不计。
当然，min、max和in也都采用O(n)，但对于未针对这些类型的查找进行优化的结构来说，这是意料之中的。
它们可以这样实现：
>>> def in_(items, value):
... for item in items:
... if item == value:
... return True
... return False
>>> def min_(items):
... current_min = items[0]
... for item in items[1:]:
... if current_min > item:
... current_min = item
... return current_min
>>> def max_(items):
... current_max = items[0]
... for item in items[1:]:
... if current_max < item:
... current_max = item
... return current_max
>>> items = range(5)
>>> in_(items, 3)
True
>>> min_(items)
0
>>> max_(items)
4在这些示例中，in操作符显然也可以工作O(1)，如果您运气好的话，但我们将其计算为O(n)，因为它可能不存在，在这种情况下，需要检查所有值。
dict必须至少在 Python 中使用的前三个容器结构中。它的速度快，使用简单，非常有效。平均时间复杂度与您所期望的完全一样-get、set和del的时间复杂度为O(1)，但在某些情况下，这是不正确的。dict的工作方式是使用hash函数（调用对象的__hash__函数）将密钥转换为哈希，并将其存储在哈希表中。然而，哈希表有两个问题。第一个也是最明显的一个是，项目将按散列排序，在大多数情况下，散列是随机出现的。哈希表的第二个问题是它们可能有哈希冲突，哈希冲突的结果是，在最坏的情况下，前面的所有操作都可以使用O(n)。散列冲突不太可能发生，但它们也可能发生，如果一个大的dict执行子类，那就是要查看的地方。
让我们看看这在实践中是如何工作的。在本例中，我将使用我能想到的最简单的哈希算法，即数字的最高有效位。所以对于12345的情况，返回1，对于56789的情况，返回5：
>>> def most_significant(value):
... while value >= 10:
... value //= 10
... return value
>>> most_significant(12345)
1
>>> most_significant(99)
9
>>> most_significant(0)
0现在，我们将使用这个散列方法使用列表的list来模拟dict。我们知道我们的散列方法只能返回从0到9的数字，所以我们的列表中只需要 10 个 bucket。现在，我们将添加一些值，并展示鸡蛋中的垃圾邮件是如何工作的：
>>> def add(collection, key, value):
... index = most_significant(key)
... collection[index].append((key, value))
>>> def contains(collection, key):
... index = most_significant(key)
... for k, v in collection[index]:
... if k == key:
... return True
... return False
# Create the collection of 10 lists
>>> collection = [[], [], [], [], [], [], [], [], [], []]
# Add some items, using key/value pairs
>>> add(collection, 123, 'a')
>>> add(collection, 456, 'b')
>>> add(collection, 789, 'c')
>>> add(collection, 101, 'c')
# Look at the collection
>>> collection
[[], [(123, 'a'), (101, 'c')], [], [],
[(456, 'b')], [], [], [(789, 'c')], [], []]
# Check if the contains works correctly
>>> contains(collection, 123)
True
>>> contains(collection, 1)
False此代码显然与dict实现不同，但实际上内部非常相似。因为我们可以通过简单的索引获得值为123的项目1，所以在一般情况下，我们只有O(1)查找成本。但是，由于两个密钥123和101都在1存储桶内，因此在所有密钥都具有相同哈希的最坏情况下，运行时间实际上可以增加到O(n)。这就是我们所说的散列冲突。
要调试散列冲突，您可以使用与计数器集合配对的hash()函数，在计数器–跟踪最常出现的元素一节中讨论。
除了哈希冲突性能问题之外，还有另一个行为可能会让您感到惊讶。从字典中删除项时，实际上还不会在内存中调整字典的大小。结果是复制和迭代整个字典都需要O(m)时间（其中 m 是字典的最大大小）；n，不使用当前项数。因此，如果您向dict添加 1000 个项目并删除 999，迭代和复制仍然需要 1000 个步骤。解决此问题的唯一方法是重新创建字典，copy和insert操作都将在内部执行此操作。请注意，insert操作期间的娱乐不受保证，取决于内部可用的空闲插槽数量。
set是一个结构，它使用哈希方法获取值的唯一集合。在内部，它与dict非常相似，具有相同的哈希冲突问题，但 set 有一些方便的特性需要显示：
# All output in the table below is generated using this function
>>> def print_set(expression, set_):
... 'Print set as a string sorted by letters'
... print(expression, ''.join(sorted(set_)))
>>> spam = set('spam')
>>> print_set('spam:', spam)
spam: amps
>>> eggs = set('eggs')
>>> print_set('eggs:', spam)
eggs: amps前几个与预期基本一致。在运营商那里，它变得有趣。
|表示
|
输出
|
解释
|
| --- | --- | --- |
| spam | amps | 所有独特的项目。Aset不允许重复。 |
| eggs | egs |
| spam & eggs | s | 两者中的每一项。 |
| spam | eggs | aegmps | 其中一项或两项中的每一项。 |
| spam ^ eggs | aegmp | 其中一项中的每一项，但不是两项中的每一项。 |
| spam - eggs | amp | 第一项中的每一项，但不是后一项。 |
| eggs - spam | eg |
| spam > eggs | False | 如果后者中的每一项都在第一项中，则为 True。 |
| eggs > spam | False |
| spam > sp | True |
| spam < sp | False | 如果第一个项目中的每个项目都包含在后一个项目中，则为 True。 |
set操作的一个有用示例是计算两个对象之间的差异。例如，假设我们有两个列表：
current_users：组中当前用户new_users：组中新的用户列表
在权限系统中，这是一种非常常见的场景，即从组中大量添加和/或删除用户。在许多权限数据库中，不可能一次设置整个列表，因此需要插入列表和删除列表。这就是set真正有用的地方：
The set function takes a sequence as argument so the double ( is
required.
>>> current_users = set((
... 'a',
... 'b',
... 'd',
... ))
>>> new_users = set((
... 'b',
... 'c',
... 'd',
... 'e',
... ))
>>> to_insert = new_users - current_users
>>> sorted(to_insert)
['c', 'e']
>>> to_delete = current_users - new_users
>>> sorted(to_delete)
['a']
>>> unchanged = new_users & current_users
>>> sorted(unchanged)
['b', 'd']现在我们有所有添加、删除和未更改的用户列表。请注意，sorted仅用于一致的输出，因为set类似于dict没有预定义的排序顺序。
tuple是一个你经常使用却没有注意到的对象。当你一开始看它时，它似乎是一个无用的数据结构。它就像一个不能修改的列表，为什么不使用list呢？在一些情况下，tuple提供了list没有的一些真正有用的功能。
首先，它们是可以使用的。这意味着您可以使用tuple作为dict中的键，这是list无法做到的：
>>> spam = 1, 2, 3
>>> eggs = 4, 5, 6
>>> data = dict()
>>> data[spam] = 'spam'
>>> data[eggs] = 'eggs'
>>> import pprint # Using pprint for consistent and sorted output
>>> pprint.pprint(data)
{(1, 2, 3): 'spam', (4, 5, 6): 'eggs'}然而，它实际上可以不仅仅是简单的数字。只要tuple的所有元素都是可散列的，它就可以工作。这意味着您可以使用嵌套的元组、字符串、数字和任何其他，hash()函数返回一致的结果：
>>> spam = 1, 'abc', (2, 3, (4, 5)), 'def'
>>> eggs = 4, (spam, 5), 6
>>> data = dict()
>>> data[spam] = 'spam'
>>> data[eggs] = 'eggs'
>>> import pprint # Using pprint for consistent and sorted output
>>> pprint.pprint(data)
{(1, 'abc', (2, 3, (4, 5)), 'def'): 'spam',
(4, ((1, 'abc', (2, 3, (4, 5)), 'def'), 5), 6): 'eggs'}您可以根据需要将其复杂化。只要所有部分都是可散列的，它就会按预期运行。
也许更有用的是，元组还支持元组打包和解包：
# Assign using tuples on both sides
>>> a, b, c = 1, 2, 3
>>> a
1
# Assign a tuple to a single variable
>>> spam = a, (b, c)
>>> spam
(1, (2, 3))
# Unpack a tuple to two variables
>>> a, b = spam
>>> a
1
>>> b
(2, 3)除了常规打包和解包之外，从 Python 3 开始，我们实际上可以打包和解包具有可变数量项的对象：
# Unpack with variable length objects which actually assigns as a
list, not a tuple
>>> spam, *eggs = 1, 2, 3, 4
>>> spam
1
>>> eggs
[2, 3, 4]
# Which can be unpacked as well of course
>>> a, b, c = eggs
>>> c
4
# This works for ranges as well
>>> spam, *eggs = range(10)
>>> spam
0
>>> eggs
[1, 2, 3, 4, 5, 6, 7, 8, 9]
# Which works both ways
>>> a
2
>>> a, b, *c = a, *eggs
>>> a, b
(2, 1)
>>> c
[2, 3, 4, 5, 6, 7, 8, 9]这种非常的方法可以应用于许多情况，甚至对于函数参数：
>>> def eggs(*args):
... print('args:', args)
>>> eggs(1, 2, 3)
args: (1, 2, 3)从函数返回多个参数同样有用：
>>> def spam_eggs():
... return 'spam', 'eggs'
>>> spam, eggs = spam_eggs()
>>> print('spam: %s, eggs: %s' % (spam, eggs))
spam: spam, eggs: eggs以下集合大多只是基本集合的扩展，其中一些相当简单，而另一些则更高级。然而，对于所有这些问题，了解底层结构的特征是很重要的。如果不了解它们，就很难理解这些收藏品的特征。
出于性能原因，有一些集合是用本机 C 代码实现的，但它们都可以用纯 Python 轻松实现。
在 Python 3.3 中引入的ChainMap允许您将多个映射（例如字典）组合成一个映射。这在组合多个上下文时特别有用。例如，在当前范围内查找变量时，默认情况下，Python 将在locals()、globals()和最后一个builtins中搜索。
通常，您会这样做：
import builtins
builtin_vars = vars(builtins)
if key in locals():
value = locals()[key]
elif key in globals():
value = globals()[key]
elif key in builtin_vars:
value = builtin_vars[key]
else:
raise NameError('name %r is not defined' % key)这是可行的，但至少可以说是丑陋的。当然，我们可以让它更漂亮：
import builtins
mappings = globals(), locals(), vars(builtins)
for mapping in mappings:
if key in mapping:
value = mapping[key]
break
else:
raise NameError('name %r is not defined' % key)好多了！此外，这实际上可以被认为是一个很好的解决方案。但是自从 Python3.3 以来，它就更容易了。现在，我们可以简单地使用以下代码：
import builtins
import collections
mappings = collections.ChainMap(globals(), locals(), vars(builtins))
value = mappings[key]ChainMap集合对于命令行应用非常有用。最重要的配置是通过命令行参数进行的，其次是目录本地配置文件，其次是全局配置文件，最后是默认值：
import argparse
import collections
defaults = {
'spam': 'default spam value',
'eggs': 'default eggs value',
}
parser = argparse.ArgumentParser()
parser.add_argument('--spam')
parser.add_argument('--eggs')
args = vars(parser.parse_args())
# We need to check for empty/default values so we can't simply use vars(args)
filtered_args = {k: v for k, v in args.items() if v}
combined = collections.ChainMap(filtered_args, defaults)
print(combined ['spam'])请注意，仍然可以访问特定映射：
print(combined.maps[1]['spam'])
for map_ in combined.maps:
print(map_.get('spam'))counter是一个用于跟踪元素出现次数的类。其基本用途如您所料：
>>> import collections
>>> counter = collections.Counter('eggs')
>>> for k in 'eggs':
... print('Count for %s: %d' % (k, counter[k]))
Count for e: 1
Count for g: 2
Count for g: 2
Count for s: 1然而，counter可以做的不仅仅是返回计数。它也有一些非常有用且快速的（它使用heapq方法来获取大多数公共元素。即使计数器中添加了一百万个元素，它仍会在一秒钟内执行：
>>> import math
>>> import collections
>>> counter = collections.Counter()
>>> for i in range(0, 100000):
... counter[math.sqrt(i) // 25] += 1
>>> for key, count in counter.most_common(5):
... print('%s: %d' % (key, count))
11.0: 14375
10.0: 13125
9.0: 11875
8.0: 10625
12.0: 10000但是等等，还有更多！除了获取最频繁的元素外，还可以添加、减去、相交和“并集”计数器，这与我们前面看到的set操作非常类似。那么，添加两个计数器和合并它们之间的区别是什么呢？正如你所料，它们是相似的，但有一点不同。让我们看看它的工作原理：
>>> import collections
>>> def print_counter(expression, counter):
... sorted_characters = sorted(counter.elements())
... print(expression, ''.join(sorted_characters))
>>> eggs = collections.Counter('eggs')
>>> spam = collections.Counter('spam')
>>> print_counter('eggs:', eggs)
eggs: eggs
>>> print_counter('spam:', spam)
spam: amps
>>> print_counter('eggs & spam:', eggs & spam)
eggs & spam: s
>>> print_counter('spam & eggs:', spam & eggs)
spam & eggs: s
>>> print_counter('eggs - spam:', eggs - spam)
eggs - spam: egg
>>> print_counter('spam - eggs:', spam - eggs)
spam - eggs: amp
>>> print_counter('eggs + spam:', eggs + spam)
eggs + spam: aeggmpss
>>> print_counter('spam + eggs:', spam + eggs)
spam + eggs: aeggmpss
>>> print_counter('eggs | spam:', eggs | spam)
eggs | spam: aeggmps
>>> print_counter('spam | eggs:', spam | eggs)
spam | eggs: aeggmps前两个是显而易见的。eggs字符串只是一个字符序列，包含两个“g、一个“s、一个“e”，垃圾邮件几乎相同，但字母不同。
spam & eggs（反之亦然）的结果也是可以预测的。垃圾邮件和鸡蛋之间共享的唯一字母是s，所以这就是结果。当涉及到计数时，它只需对两个共享元素执行一个min(element_a, element_b)，并得到最低值。
从鸡蛋中减去字母s、p、a和m后，剩下的是e和g。同样，当从垃圾邮件中删除e、g和s时，剩下的是p、a和m。
现在，添加就像您所期望的那样，只是两个计数器的元素逐个添加。
那么工会有什么不同呢？它获取任一计数器中每个元素的max(element_a, element_b)，而不是添加它们；与添加的情况相同。
最后，如前面代码所示，elements 方法返回一个扩展列表，其中包含计数重复的所有元素。
在执行数学运算期间，Counter对象将自动删除零或更少的元素。
deque（双端队列的缩写）对象是最早的集合之一。它是在 Python2.4 中引入的，所以到为止，它已经可用了 10 多年。一般来说，现在这个对象对于大多数用途来说都太低级了，因为许多本来可以使用它的操作都有支持良好的库，但这并不会降低它的实用性。
在内部，deque被创建为一个双链接列表，这意味着每个项目都指向下一个和上一个项目。因为deque是双端的，所以列表本身同时指向第一个和最后一个元素。这使得从开始或结束添加和删除项目成为一个非常轻松的O(1)操作，因为只有指向列表开始/结束的指针需要更改，并且需要将指针添加到第一个/最后一个项目，这取决于项目是在开始还是结束添加。
出于简单的堆栈/队列目的，使用双端队列似乎是浪费，但性能足够好，我们不必关心由此产生的开销。deque类完全用 C 语言实现（使用 CPython）。
它作为队列的用法非常简单：
>>> import collections
>>> queue = collections.deque()
>>> queue.append(1)
>>> queue.append(2)
>>> queue
deque([1, 2])
>>> queue.popleft()
1
>>> queue.popleft()
2
>>> queue.popleft()
Traceback (most recent call last):
...
IndexError: pop from an empty deque正如预期的那样，这些项目后面跟着一个IndexError，因为只有两个项目，而我们正试图得到三个。
堆栈的用法几乎相同，但我们必须使用pop而不是popleft（或者使用appendleft而不是append：
>>> import collections
>>> queue = collections.deque()
>>> queue.append(1)
>>> queue.append(2)
>>> queue
deque([1, 2])
>>> queue.pop()
2
>>> queue.pop()
1
>>> queue.pop()
Traceback (most recent call last):
...
IndexError: pop from an empty deque另一个非常有用的特性是deque可以用作带有maxlen参数的循环队列。通过使用它，它可以用来保存最后的n状态消息或类似信息：
>>> import collections
>>> circular = collections.deque(maxlen=2)
>>> for i in range(5):
... circular.append(i)
... circular
deque([0], maxlen=2)
deque([0, 1], maxlen=2)
deque([1, 2], maxlen=2)
deque([2, 3], maxlen=2)
deque([3, 4], maxlen=2)
>>> circular
deque([3, 4], maxlen=2)当您需要单线程应用中的队列或堆栈类时，deque是一个非常方便的选项。如果您需要为多线程操作同步对象，则更适合使用queue.Queue类。在内部，它封装了deque，但它是线程安全的替代方案。在同一类别中，还有用于异步操作的asyncio.Queue和用于多进程操作的multiprocessing.Queue。在第 7 章、异步 IO–无线程多线程和第 13 章、多进程中可以分别找到asyncio和多进程的示例，当单个 CPU 核心不够时。
到目前为止，defaultdict是我收藏包中最喜欢的对象。我仍然记得在添加到核心之前，我编写了自己的版本。虽然它是一个相当简单的对象，但它对于各种设计模式都非常有用。您不必每次都检查是否存在键并添加值，只需从一开始就声明默认值，而无需担心其他问题。
例如，假设我们正在从连接节点列表构建一个非常基本的图结构。
这是我们的连接节点列表（单向）：
nodes = [
('a', 'b'),
('a', 'c'),
('b', 'a'),
('b', 'd'),
('c', 'a'),
('d', 'a'),
('d', 'b'),
('d', 'c'),
]现在，让我们将此图放入普通字典：
>>> graph = dict()
>>> for from_, to in nodes:
... if from_ not in graph:
... graph[from_] = []
... graph[from_].append(to)
>>> import pprint
>>> pprint.pprint(graph)
{'a': ['b', 'c'],
'b': ['a', 'd'],
'c': ['a'],
'd': ['a', 'b', 'c']}当然，有些变化是可能的，例如使用setdefault。但它们仍然比需要的更加复杂。
真正的 Python 版本使用defaultdict代替：
>>> import collections
>>> graph = collections.defaultdict(list)
>>> for from_, to in nodes:
... graph[from_].append(to)
>>> import pprint
>>> pprint.pprint(graph)
defaultdict(<class 'list'>,
{'a': ['b', 'c'],
'b': ['a', 'd'],
'c': ['a'],
'd': ['a', 'b', 'c']})这不是一段漂亮的代码吗？defaultdict实际上可以被视为counter对象的前身。它没有counter那样的花哨，也没有counter那样的钟声和口哨声，但在许多情况下，它确实起到了作用：
>>> counter = collections.defaultdict(int)
>>> counter['spam'] += 5
>>> counter
defaultdict(<class 'int'>, {'spam': 5})defaultdict的默认值需要是一个可调用的对象。在前面的例子中，它们是int和list，但是您可以轻松地定义自己的函数作为默认值使用。这就是下面的示例所使用的，尽管我不推荐产品使用，因为它缺乏一点可读性。然而，我确实相信，这是 Python 强大功能的一个很好的例子。
这就是我们如何在一行 Python 中创建一个tree：
import collections
def tree(): return collections.defaultdict(tree)太棒了，不是吗？下面是我们如何实际使用它：
>>> import json
>>> import collections
>>> def tree():
... return collections.defaultdict(tree)
>>> colours = tree()
>>> colours['other']['black'] = 0x000000
>>> colours['other']['white'] = 0xFFFFFF
>>> colours['primary']['red'] = 0xFF0000
>>> colours['primary']['green'] = 0x00FF00
>>> colours['primary']['blue'] = 0x0000FF
>>> colours['secondary']['yellow'] = 0xFFFF00
>>> colours['secondary']['aqua'] = 0x00FFFF
>>> colours['secondary']['fuchsia'] = 0xFF00FF
>>> print(json.dumps(colours, sort_keys=True, indent=4))
{
"other": {
"black": 0,
"white": 16777215
},
"primary": {
"blue": 255,
"green": 65280,
"red": 16711680
},
"secondary": {
"aqua": 65535,
"fuchsia": 16711935,
"yellow": 16776960
}
}好的一点是，你可以让它深入到你想要的深度。由于defaultdict基，它递归地生成自己。
namedtuple对象正是名称所暗示的——一个具有名称的元组。它有一些有用的用例，尽管我必须承认我在野外没有发现太多用例，除了一些 Python 模块，如 inspect 和urllib.parse。二维或三维空间中的点就是一个很好的例子，说明它在哪些方面绝对有用：
>>> import collections
>>> Point = collections.namedtuple('Point', ['x', 'y', 'z'])
>>> point_a = Point(1, 2, 3)
>>> point_a
Point(x=1, y=2, z=3)
>>> point_b = Point(x=4, z=5, y=6)
>>> point_b
Point(x=4, y=6, z=5)关于namedtuple可以说的不多；它实现了您所期望的功能，最大的优点是属性可以通过名称和索引执行，这使得元组解包非常容易：
>>> x, y, z = point_a
>>> print('X: %d, Y: %d, Z: %d' % (x, y, z))
X: 1, Y: 2, Z: 3
>>> print('X: %d, Y: %d, Z: %d' % point_b)
X: 4, Y: 6, Z: 5
>>> print('X: %d' % point_a.x)enum包与namedtuple非常相似，但的目标和界面完全不同。基本的enum对象使得在模块中设置常数变得非常容易，同时仍然避免了使用幻数。这是一个基本的例子：
>>> import enum
>>> class Color(enum.Enum):
... red = 1
... green = 2
... blue = 3
>>> Color.red
<Color.red: 1>
>>> Color['red']
<Color.red: 1>
>>> Color(1)
<Color.red: 1>
>>> Color.red.name
'red'
>>> Color.red.value
1
>>> isinstance(Color.red, Color)
True
>>> Color.red is Color['red']
True
>>> Color.red is Color(1)
Trueenum包的一些方便的特性是，对象是可移植的，可以通过数值和文本表示的值来访问，并且，通过适当的继承，甚至可以与其他类进行比较。
下面的代码显示了基本 API 的用法：
>>> for color in Color:
... color
<Color.red: 1>
<Color.green: 2>
<Color.blue: 3>
>>> colors = dict()
>>> colors[Color.green] = 0x00FF00
>>> colors
{<Color.green: 2>: 65280}不过，还有更多。enum包中一个鲜为人知的可能性是，您可以通过继承特定类型来进行值比较，这不仅适用于整数，也适用于（您自己的）自定义类型。
这是常规的enum：
>>> import enum
>>> class Spam(enum.Enum):
... EGGS = 'eggs'
>>> Spam.EGGS == 'eggs'
False以下是具有str继承的enum：
>>> import enum
>>> class Spam(str, enum.Enum):
... EGGS = 'eggs'
>>> Spam.EGGS == 'eggs'
TrueOrderdDict是一个dict，用于跟踪项目插入的顺序。而普通dict将按照散列的顺序返回密钥，OrderedDict将按照插入的顺序返回密钥。因此，它不是按键或值排序的，但也很容易做到：
>>> import collections
>>> spam = collections.OrderedDict()
>>> spam['b'] = 2
>>> spam['c'] = 3
>>> spam['a'] = 1
>>> spam
OrderedDict([('b', 2), ('c', 3), ('a', 1)])
>>> for key, value in spam.items():
... key, value
('b', 2)
('c', 3)
('a', 1)
>>> eggs = collections.OrderedDict(sorted(spam.items()))
>>> eggs
OrderedDict([('a', 1), ('b', 2), ('c', 3)])虽然您可能会猜到它是如何工作的，但其内部结构可能会让您有点惊讶。我知道我期待着一个不同的实现。
在内部，OrderedDict使用普通dict进行键/值存储，此外，它还使用双链表跟踪下一个/上一个项目。为了跟踪反向关系（从双链接列表回到键），内部存储了一个额外的dict。
简单地说，OrderedDict可以是一个非常方便的工具来保持您的dict分类，但它确实要付出代价。该系统的结构使得set和get速度非常快O(1)，但与常规dict相比，该对象仍然要重很多（内存使用量增加一倍或更多）。当然，在许多情况下，内部对象的内存使用量将超过dict本身的内存使用量，但这是需要记住的。
heapq模块是一个非常小的模块，它使得在 Python 中创建优先级队列非常容易。一种结构，它总是以最小的努力使最小的（或最大的，取决于实现）项可用。API 非常简单，在OrderedDict对象中可以看到其使用的最佳示例之一。您可能不想直接使用heapq，但要分析像OrderedDict这样的类是如何工作的，理解内部工作原理是很重要的。
如果您正在寻找一种结构来保持列表始终处于排序状态，请尝试使用bisect模块。
但基本用法非常简单：
>>> import heapq
>>> heap = [1, 3, 5, 7, 2, 4, 3]
>>> heapq.heapify(heap)
>>> heap
[1, 2, 3, 7, 3, 4, 5]
>>> while heap:
... heapq.heappop(heap), heap
(1, [2, 3, 3, 7, 5, 4])
(2, [3, 3, 4, 7, 5])
(3, [3, 5, 4, 7])
(3, [4, 5, 7])
(4, [5, 7])
(5, [7])
(7, [])这里需要注意的一点是，您可能已经从前面的示例中了解到，heapq模块并不创建特殊对象。它只是一系列将常规列表视为heap的方法。这并不会降低它的实用性，但这是需要考虑的。您可能还想知道为什么heap没有排序。实际上，它是被分类的，但不是你期望的那样。如果你将heap视为一棵树，它会变得更加明显：
1
2 3
7 3 4 5最小的数字总是在树的顶部，最大的数字总是在树的底部。正因为如此，找到最小的数字确实很容易，但找到最大的数字却不那么容易。要获得堆的排序版本，我们只需不断移除树的顶部，直到所有项都消失。
我们已经看到了上一段中的模块，它使得总是从列表中获取最小的数字变得非常简单，因此很容易对对象列表进行排序。当heapq模块附加项以形成树状结构时，bisect模块插入项的方式使其保持排序。一个很大的区别是使用heapq模块添加/删除项目非常简单，而使用bisect模块查找项目非常简单。如果你的主要目的是搜索，那么bisect应该是你的选择。
与heapq一样，bisect并没有真正创建特殊的数据结构。它只是在一个标准list上工作，并期望list总是被排序。理解这一点对绩效的影响很重要；使用bisect算法简单地将项目添加到列表中可能会非常慢，因为在列表中插入需要O(n)。实际上，使用对分创建排序列表需要O(n*n)，这相当慢，特别是因为使用heapq或O(n * log(n))创建相同的排序列表。
log(n)表示以 2 为底的对数函数。要计算该值，可以使用math.log2()函数。这将导致每次该数字的大小翻倍时增加 1。对于n=2，log(n)的值为1，因此对于n=4和n=8，日志值分别为2和3。
这意味着一个 32 位的数字，即2**32 = 4294967296，其日志为32。
如果您有一个排序结构，并且只需要添加一个项目，那么可以使用bisect算法进行插入。否则，通常只需附加这些项并在之后调用一个.sort()会更快。
为了举例说明，我们有以下几行：
>>> import bisect
Using the regular sort:
>>> sorted_list = []
>>> sorted_list.append(5) # O(1)
>>> sorted_list.append(3) # O(1)
>>> sorted_list.append(1) # O(1)
>>> sorted_list.append(2) # O(1)
>>> sorted_list.sort() # O(n * log(n)) = O(4 * log(4)) = O(8)
>>> sorted_list
[1, 2, 3, 5]
Using bisect:
>>> sorted_list = []
>>> bisect.insort(sorted_list, 5) # O(n) = O(1)
>>> bisect.insort(sorted_list, 3) # O(n) = O(2)
>>> bisect.insort(sorted_list, 1) # O(n) = O(3)
>>> bisect.insort(sorted_list, 2) # O(n) = O(4)
>>> sorted_list
[1, 2, 3, 5]对于少量的项目，差异可以忽略不计，但它会迅速增长到差异很大的程度。对于n=4，差异仅在4 * 1 + 8 = 12和1 + 2 + 3 + 4 = 10之间，使得对分解更快。但如果我们插入 1000 个项目，它将是1000 + 1000 * log(1000) = 10966对1 + 2 + … 1000 = 1000 * (1000 + 1) / 2 = 500500。因此，在插入许多项目时要非常小心。
但在列表中搜索速度非常快；因为它是经过排序的，所以我们可以使用一个非常简单的二进制搜索算法。例如，如果我们想检查列表中是否存在一些数字，该怎么办？
>>> import bisect
>>> sorted_list = [1, 2, 3, 5]
>>> def contains(sorted_list, value):
... i = bisect.bisect_left(sorted_list, value)
... return i < len(sorted_list) and sorted_list[i] == value
>>> contains(sorted_list, 2)
True
>>> contains(sorted_list, 4)
False
>>> contains(sorted_list, 6)
False正如您所看到的，bisect_left函数查找数字应该位于的位置。这实际上也是insort函数所做的；它通过搜索号码的位置将号码插入正确的位置。
那么这与sorted_list中的常规值有何不同？最大的区别在于，ORT T1 在内部进行二进制搜索，这意味着它在中间开始，并且根据值大于或小于值而向左或向右跳跃。为了说明，我们将在0到14之间的数字列表中搜索4：
sorted_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
Step 1: 4 > 7 ^
Step 2: 4 > 3 ^
Step 3: 4 > 5 ^
Step 4: 4 > 5 ^正如您所看到的，在仅经过四个步骤（实际上是三个步骤；第四个步骤仅用于说明）之后，我们找到了我们搜索的号码。根据号码（7，例如），它可能会更快，但找到一个号码永远不会超过O(log(n))步。
对于常规列表，搜索只需遍历所有项目，直到找到所需的项目。如果你运气好，它可能是你遇到的第一个数字，但如果你运气不好，它可能是最后一个项目。对于 1000 个项目，这就是 1000 个步骤和log(1000) = 10步骤之间的差异。
Python 内置了很多非常有用的集合。由于定期添加越来越多的收藏，最好的办法就是跟踪收藏手册。你有没有想过这些结构是如何或为什么工作的？只要看看这里的来源：
https://hg.python.org/cpython/file/default/Lib/collections/init.py
完成本章后，您应该了解 collections 模块中的核心集合和最重要的集合，但更重要的是这些集合在多个场景中的性能特征。在应用中选择正确的数据结构是迄今为止代码将经历的最重要的性能因素，这对于任何程序员来说都是必不可少的知识。
接下来，我们将继续进行函数式编程，包括lambda函数、list理解、dict理解、set理解以及一系列相关主题。这包括一些有关数学的背景信息，这些信息可能很有趣，但可以安全地跳过。