Python中内存高效的int-int字典

Question

我需要在Python中实现一个内存使用效率高的整数到整数的字典，这个字典需要支持以下操作，时间复杂度是O(log n)：

d[k] = v  # replace if present
v = d[k]  # None or a negative number if not present

我需要存储大约250M对数据，所以它真的必须非常节省内存。

你知道有没有合适的实现方式吗（Python 2.7）？

编辑 删除了不可能的要求和其他无关的内容。谢谢，Craig和Kylotan！

---

换句话说，这里有一个简单的整数到整数的字典，包含100万对：

>>> import random, sys
>>> from guppy import hpy
>>> h = hpy()
>>> h.setrelheap()
>>> d = {}
>>> for _ in xrange(1000000):
...     d[random.randint(0, sys.maxint)] = random.randint(0, sys.maxint)
... 
>>> h.heap()
Partition of a set of 1999530 objects. Total size = 49161112 bytes.
 Index  Count   %     Size   % Cumulative  % Kind (class / dict of class)
     0      1   0 25165960  51  25165960  51 dict (no owner)
     1 1999521 100 23994252  49  49160212 100 int

平均来说，一对整数大约使用49字节。

这里有一个包含200万整数的数组：

>>> import array, random, sys
>>> from guppy import hpy
>>> h = hpy()
>>> h.setrelheap()
>>> a = array.array('i')
>>> for _ in xrange(2000000):
...     a.append(random.randint(0, sys.maxint))
... 
>>> h.heap()
Partition of a set of 14 objects. Total size = 8001108 bytes.
 Index  Count   %     Size   % Cumulative  % Kind (class / dict of class)
     0      1   7  8000028 100   8000028 100 array.array

平均来说，一对整数大约使用8字节。

我接受在字典中实现每对8字节是相当困难的。重新表述一下问题：有没有一种内存使用效率高的整数到整数字典实现，能显著少于每对49字节的内存使用？

Answer 1

每个键值对占用8个字节，这在任何实现中都挺难的，不管是Python还是其他语言。如果你不能保证这些键是连续的，那么用数组来表示的话，就会在键之间浪费很多空间（还需要一些特殊的值来表示没有键的情况）。或者，你就得维护一个单独的索引来管理键值对，而这本身就会超过每对8个字节的限制（即使只多一点点）。

我建议你使用数组的方法，但最好的办法还是要看你所期望的键的特点。

Answer 2

我不知道这是不是一次性解决方案，还是一个正在进行的项目。如果是一次性解决方案的话，增加更多的内存（RAM）是不是比花开发者的时间去优化内存使用更划算呢？即使每对数据占用64字节，你也只需要大约15GB的内存，这在大多数桌面电脑上都能轻松放下。

我觉得正确的答案可能在SciPy和NumPy这两个库里，但我对这个库不够熟悉，没办法告诉你具体该去哪里找。

你也可以在这个讨论串中找到一些有用的想法：Python字典的内存高效替代方案

Answer 3

你可以使用Zope中的IIBtree。