实现Python整数键值的numpy字典

Question

我有一大堆数据需要快速查找，通常我会用字典来处理。但是，我需要存储大约6亿对键值对，结果发现把这些放进字典里会占用太多内存。

我意识到，如果字典把键和值都存成固定长度的整数（比如32位），就能节省内存。我可以通过使用numpy数组，先对数据进行排序，然后再搜索来找到正确的值（这样大约占用8GB的内存）：

import numpy as np    
key_a = np.zeros(600e6, dtype=np.int64)
values_a = np.zeros(600e6, dtype=np.int32)

# ... Fill arrays ...

# Find value using key:
index = np.searchsorted(key_a, key_to_find)    
value_to_find = values_a[index]

不过，这种方法的速度没有用哈希表快。

我理想中的做法是实现一个字典，但用固定大小的numpy数组作为基础，这样可以节省空间。我还希望这个字典能针对整数进行优化。为什么numpy没有提供这样的功能呢？我该怎么做才能实现这个呢？

Answer 1

我理想中的做法是实现一个字典，但用固定大小的numpy数组作为基础，这样可以节省空间。

固定大小的数组显然会让你得到一个固定大小的字典。（你显然不能用链表，因为你不能把链表放进一个整数的numpy数组里……）这样可以接受吗？

我还希望这个字典能针对整数进行优化。

这具体是什么意思呢？你仍然需要对整数进行哈希处理，以便获得合理的键分布。也许你可以为固定大小的整数想出一个稍微快一点的哈希函数，但我怀疑这会带来太大的性能提升。

为什么numpy没有提供这样的东西呢？

因为这和numpy的核心内容——数值编程关系不大。实际上，即使是那些和numpy有点关系但不够“基础”的东西，通常也会被放到像scipy这样的库里，而不是放在numpy里。

我该怎么做呢？

你不知道怎么实现哈希表吗？在StackOverflow上回答这个问题并不是学习基础数据结构的好地方，但维基百科的文章看起来不错。

如果你想让它尽可能像Python的dict的哈希表工作，最好的办法就是查看源代码。CPython在注释中很好地解释了它是如何工作的。不过当然，这段代码是C语言的，不是Python，所以除非你懂一些基本的C语言，否则可能看不懂。你也可以看看PyPy——虽然它的源代码稍微复杂一些（它有一些CPython没有的优化），但它是用Python写的。

在PyPI上还有很多自定义的哈希表实现。

你还可以看看fixedhash。我写这个是为了尽可能简单地实现一个哈希表，作为展示不同探测函数影响的基础（它开始用的是简单的线性探测），但我想它也可以作为展示如何构建一个尽可能简单的哈希表的基础。:) 它是围绕一个bytearray构建的，用来存储8字节的bytes键和值；把它改成用np.ndarray来存储4字节的整数键和值应该很明显，而且你可以使用Nx3或Nx4的数组，这样会更易读（不需要那些struct.pack的东西）。