python - 最好使用整数键的字典或很长的列表？

Question

基本上，我需要制作一个包含非连续整数 ID 的查找表。我想知道，就查找速度而言，我通常最好还是使用带有整数键的 dict ，或者使用一个很长的 list 有很多空索引。在我看来，list 可能仍然更快，因为 Python 应该确切地知道要查找的位置，但我想知道是否有任何后端进程使用 dict 来补偿以及那些空 list 插槽的额外内存要求是否会抵消(可能)更容易遍历 list 的速度增益。 list 和 dict 是否有任何替代方案可能更适合于此？

我看过这个问题，但它并没有完全回答我的问题:Dictionary access speed comparison with integer key against string key

预计到达时间:我在我的程序中执行了两次这样的查找表。一个实例的最大 ID 为 5,000，其中填充了 70-100 个对象；另一个的最大 ID 为 750，其中填充了 20-30 个。

Answer 1

回答关于 dict 的问题对比list您必须提供有关元素数量、缺失元素数量等的确切信息，以便我们可以准确估计两个数据结构的内存使用情况并尝试预测和/或检查他们的表现。

一般来说 dict的 N键值对需要比 list 更多的内存与 N值(value)观:

• dict必须跟踪 key
• dict永远不会超过 2/3 满。发生这种情况时，分配的内存会加倍(这需要在 dict 上进行 O(1) 分摊时间操作)。

但是有一个替代这些数据结构应该提供非常好的性能: blist . blist包提供与 list 相匹配的接口(interface)，只有它是使用 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

完整文档为 here .

请注意 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占用更少的内存(在第一种情况下，它占用等效内存的 1/3 dict )。请注意 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就您所拥有的小型列表的查找性能而言。