在Python中可以实现一个巨大的查找表（超过1亿个键）吗？

Question

我想写一个程序，生成一亿个独特的钥匙，每个钥匙都有一个值（最多四位数字）。然后我希望能尽可能快地访问这些数据，这样我就可以查找一个钥匙并得到它的值。理想情况下，我希望每秒能查找至少一百万次。

假设我的计算能力是正常的，这样做可能吗？我是不是应该把它做成一个字典，还是说我应该开始学习数据库之类的东西？

任何能让我朝正确方向前进的建议都会非常有帮助。

Answer 1

我没有足够的内存来测试一亿个数据，但我生成了一个包含五千万个项目的字典，并在我的笔记本上进行了100万次查找，花了0.25秒。你的估计差不多。

import time

d = dict((k,k) for k in range(5*10**7))
time.sleep(2) # let system settle
print('start')
start = time.time()
for i in range(10**6):
    x = d[i]
print(time.time() - start)

给我带来了

start
.25

Answer 2

简单算一下，如果你在一个32位的系统上用Python，内存里是做不了的。因为如果你有10⁸个键的话，只有30个字节可以给每个键用，如果你的地址空间是3GB。

在64位系统上，存储一个键和一个值至少需要：

• 每个指针在桶里占8个字节，还有一个指针分别指向键和值，
• 每个键和值可能还需要28个字节（在我的64位系统上，使用sys.getsizeof(0)得到的是28）。

所以我们估计至少需要7.2GB的内存。你是可以做到的，但性能可能会很差。我建议你使用一些简单的工具，比如Kyoto Cabinet。