使用整数键的字典好还是很长的列表好？

Question

基本上，我需要创建一个查找表，里面的整数ID不是连续的。我在想，从查找速度来看，使用一个带有整数键的 dict 会不会更好，还是用一个很长的 list，里面有很多空位。看起来 list 可能会更快，因为Python应该知道确切的位置，但我在想 dict 是否有一些后台处理来弥补这个差距，以及那些空的 list 位置所需的额外内存是否会抵消 list 可能更容易遍历的速度优势。有没有其他替代 list 和 dict 的方法，可能更适合这个需求？

我见过这个问题，但它并没有完全回答我的疑问：使用整数键和字符串键的字典访问速度比较

补充说明：我在程序中实现这样的查找表有两次。一个实例的最大ID是5000，里面有70到100个对象；另一个实例的最大ID是750，里面有20到30个对象。

Answer 1

我觉得这个问题没有一个通用的答案。具体要看整数id的分布情况、可用的内存以及你的性能需求。以下是一些基本规则：

• 查找列表会更快，因为你不需要计算键的哈希值。
• 如果键的最大值很大，字典可能会更紧凑。
• 如果你的最大键值非常大（大约是2的30次方），你会浪费很多内存，系统会开始交换内存，这会大大降低性能。

这里有一些经验法则：

• 如果有“少量”的空值，或者你知道最大键值会“相对”较低（相对于你愿意花费的内存） => 使用列表。
• 如果不满足上面的条件，并且你没有强烈的性能需求 => 使用字典。
• 如果以上两个条件都不成立，你需要尝试一些哈希函数的优化 - 我会在下面详细说明。

字典的理论是一个数组，索引是对键应用哈希函数的结果。Python的算法经过了合理的优化，但它是通用的。如果你知道你的数据分布有特殊性，可以尝试找一个特别适合你数据分布的哈希函数。你可以在维基百科的哈希函数文章中找到更多信息，或者查看老牌的C标准库中的hash。

Answer 2

列表:
1. 从列表的末尾添加（append）和删除（pop）元素是很快的。
2. 从列表的开头插入（insert）和删除（pop）元素是比较慢的，因为这两个操作背后有比较复杂的处理。
3. 对于第二种情况，使用collection.deque会更好。

字典:
4. 访问字典中的元素比访问列表中的元素要快。

遍历字典和列表:

1. 字典使用iteritems()方法可以同时获取键和对应的值。
   
2. 列表则使用enumerate()来达到同样的目的。
   
   注意事项:
3. 如果你只是关心遍历的速度，iteritems()和enumerate()之间没有明显的区别。
4. 在Python 3.x中，iteritems()已经被移除了。
5. zip()方法是一个比较复杂的过程，建议避免使用。

Answer 3

关于你提到的 dict 和 list 的问题，我们需要知道一些具体的信息，比如元素的数量、缺失元素的数量等等，这样才能准确估算这两种数据结构的内存使用情况，并尝试预测或检查它们的性能。

一般来说，一个包含 N 个键值对的 dict 需要的内存比一个包含 N 个值的 list 要多得多：

• dict 需要记录所有的键
• dict 的使用率通常不会超过 2/3。当使用率达到这个水平时，分配的内存会翻倍（这是为了确保 dict 的操作在平均情况下是 O(1) 的时间复杂度）。

不过，还有一种替代的数据结构可以提供非常好的性能，那就是 blist。blist 包提供的接口与 list 相似，但它是通过 B 树实现的。它可以高效地处理稀疏列表。大多数操作的时间复杂度是 O(1) 或 O(log n)，所以效率相当高。

例如，你可以先创建一个稀疏的 blist，方法是：

from blist import blist

seq = blist([None])
seq *= 2**30    # create a 2**30 element blist. Instantaneous!

然后你可以只设置那些有值的索引：

for i, value in zip(indices, values):
    seq[i] = value

完整的文档可以在 这里 找到。

需要注意的是，blist 还提供其他高效的操作，比如：

• 连接两个 blist 的时间复杂度是 O(log n)
• 取一个 [i:j] 的切片时间复杂度是 O(log n)
• 在给定索引插入一个元素的时间复杂度是 O(log n)
• 从任意位置弹出一个元素的时间复杂度是 O(log n)

---

既然你提供了一些数字，下面是它们与 dict 的比较：

>>> from blist import blist
>>> b = blist([None])
>>> b *= 5000
>>> for i in range(100):b[i] = i
... 
>>> b.__sizeof__()
2660
>>> d = dict()
>>> for i in range(100):d[i] = i
... 
>>> d.__sizeof__()
6216
>>> b = blist([None])
>>> b *= 750
>>> for i in range(30):b[i] = i
... 
>>> b.__sizeof__()
1580
>>> d = dict()
>>> for i in range(30):d[i] = i
... 
>>> d.__sizeof__()
1608

在这两种情况下，blist 占用的内存更少（在第一种情况下，它只占用相应 dict 内存的 1/3）。需要注意的是，blist 占用的内存还取决于索引是否连续（连续的效果更好）。不过即使使用随机索引：

>>> b = blist([None])
>>> b *= 5000
>>> import random
>>> for i in range(100):b[random.randint(0, 4999)] = i
... 
>>> b.__sizeof__()
2916

它仍然比 dict 要好得多。

即使是查找时间也更快：

In [1]: from blist import blist
   ...: import random
   ...: 

In [2]: b = blist([None])

In [3]: b *= 5000

In [4]: for i in range(100):b[random.randint(0, 4999)] = i

In [5]: %timeit b[0]
10000000 loops, best of 3: 50.7 ns per loop

In [6]: d = dict()

In [7]: for i in range(100):d[random.randint(0, 4999)] = i

In [10]: %timeit d[1024]   # 1024 is an existing key in this dictionary
10000000 loops, best of 3: 70.7 ns per loop

In [11]: %timeit b[1024]
10000000 loops, best of 3: 50.7 ns per loop

注意，在我的机器上，list 查找一个索引大约需要 47 ns，所以在小列表的查找性能上，blist 和 list 非常接近。