Question

读完本章之后你将能够回答下列问题

字典和集合各自适用于什么情况？

字典和集合的共同点是什么？

字典的开销在哪里？

我如何优化字典的性能？

Python如何使用字典记录命名空间？

如果你有一些无序数据但它们可以被唯一的索引对象来引用（任何可以被散列的类型都可以成为索引对象，索引对象通常会是一个字符串），那么集合和字典就是理想的数据结构。索引对象被称为“键”，而数据被称为“值”。字典和集合几乎一模一样，只是集合实际上并不包含值：一个集合只不过是一堆键的组合。顾名思义，集合非常适用于集合操作。

　备忘　

可以被散列的类型是一种同时实现了__hash__魔法函数以及__eq__或__cmp__两者之一的类型。所有的Python原生类型都实现了它们，而用户自定义类则都有默认的值。4.1.4节中会介绍更多细节。

在上一章，我们看到对次序未知的列表/元组的最优查询时间是O(log n)（使用搜索操作），而字典和集合基于键的查询则可以带给我们O(1)（译注：原文这里为O(n)，根据上下文判断应为O(1)）的查询时间。除此之外，和列表/元组一样，字典和集合的插入时间是`O(1)·^[1]。在4.1节中我们会看到，为了达到这一速度，它们在底层所使用的数据结构是一个开放地址散列表。

然而，使用字典和集合有其代价。首先它们通常会占用更多的内存。同时，虽然插入/查询的复杂度是O(1)，但实际的速度极大取决于其使用的散列函数。如果散列函数的运行速度较慢，那么在字典和集合上进行的任何操作也会相应变慢。

让我们看一个例子。假设我们需要存储一个电话簿中每个人的联系信息，并且能够在将来轻松回答问题“John Doe的电话号码是什么？”如果使用列表，我们会将电话号码和名字依次存储并在需要查询时检索整个列表，如例4-1所示。

例4-1　列表查询电话簿

def find_phonenumber(phonebook, name):
  for n, p in phonebook:
    if n == name:
      return p
  return None

phonebook = [
  ("John Doe", "555-555-5555"),
  ("Albert Einstein", "212-555-5555"),
]
print "John Doe's phone number is", find_phonenumber(phonebook, "John Doe")

　备忘　

我们也可以将列表排序并用bisect模块获得O(log n)的性能。

但如果使用字典，我们只需要以名字为“键”，以电话号码为“值”，如例4-2所示。这让我们得以通过简单查询就获得我们需要的值的直接引用，而不是去数据集中读取每一个值。

例4-2　字典查询电话簿

phonebook = {
  "John Doe": "555-555-5555",
  "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

对大型电话簿来说，字典的O(1)查询和列表的O(n)线性搜索（或使用bisect模块后的O(log n)）之间的区别是十分可观的。

　问题　

创建一个脚本来比较bisect列表和字典在解决电话簿查询问题上的时间。当电话簿大小增长时，时间会如何变化？

另一方面，如果我们想要回答的问题是“我的电话簿中有多少个不同的名字？”我们就可以使用集合的能力。记住集合就是一堆键的组合——这正是我们需要给数据添加的属性。这跟基于列表的解决方案是一个鲜明的对比，为了给列表加上这一属性，我们将不得不拿出每一个名字并和其他所有名字进行比较，见例4-3。

例4-3　用列表和集合查询不同的名字

def list_unique_names(phonebook):
  unique_names = []
  for name, phonenumber in phonebook:       #　❶
    first_name, last_name = name.split(" ", 1)
    for unique in unique_names:         #　❷
      if unique == first_name:
        break
    else:
      unique_names.append(first_name)
  return len(unique_names)

def set_unique_names(phonebook):
  unique_names = set()
  for name, phonenumber in phonebook:       #　❸
    first_name, last_name = name.split(" ", 1)
    unique_names.add(first_name)        #　❹
  return len(unique_names)

phonebook = [
  ("John Doe", "555-555-5555"),
  ("Albert Einstein", "212-555-5555"),
  ("John Murphey", "202-555-5555"),
  ("Albert Rutherford", "647-555-5555"),
  ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

❶❸ 我们必须遍历电话簿的每一项，所以这一循环的代价是O(n)。

❷ 这里，我们必须比较当前的名字和所有已知的名字。如果它是一个新名字，则加入已知名字列表。我们继续遍历列表进行这一步骤，直到电话簿中所有的项都被遍历。

❹ 对于集合，我们只需要简单地将当前名字添加进集合，而无须遍历所有的已知名字。因为集合保证了它包含的键的唯一性，如果你尝试添加一个已有的项，该项不会被添加进集合。另外，这一操作的代价是O(1)。

列表算法的内循环会遍历unique_names，它从空列表开始增长，在最坏情况下，所有的名字都是唯一的，那么它最终会增长到跟电话簿一样大小。这可以被看作是在一个不断增长的列表上线性搜索电话簿中的每一个名字。因此，完整算法具有O(n log n)的复杂度，因为外循环的贡献是O(n)而内循环的贡献则是O(log n)。

另一方面，集合算法没有内循环，无论电话簿多大，set.add操作都可以在一个固定的操作次数中完成，是一个代价为O(1)的过程（关于这点，我们在讨论字典和集合的实现时会有一些细节方面的警告）。因此，对于这一算法复杂度的唯一非常数贡献是对电话簿的遍历，整个算法的复杂度就是O(n)。

我们用一个具有10 000个条目以及7 422个唯一名字的电话簿对这两个算法进行计时，我们会看到O(n)和O(n log n)能有多大的差距：

>>> %timeit list_unique_names(large_phonebook)
1 loops, best of 3: 2.56 s per loop

>>> %timeit set_unique_names(large_phonebook)
100 loops, best of 3: 9.57 ms per loop

也就是说，集合算法的速度是列表的267倍！另外，当电话簿大小增长时，速度的提升也在增加（对于一个具有100 000个条目以及15 574个唯一名字的电话簿，这一差距是557倍）。