python - Python中的内存高效int-int dict

Question

我需要 Python 中的内存高效 int-int dict，它可以在 O(log n) 时间内支持以下操作:

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

我需要容纳约 2.5 亿对，所以它真的必须很紧。

您碰巧知道合适的实现(Python 2.7)吗？

编辑 删除了不可能的要求和其他废话。谢谢，Craig 和 Kylotan!

---

改写。这是一个包含 1M 对的普通 int-int 字典:

>>> 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 个字节。

这是一个 2M 整数数组:

>>> 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 个字节/对的 int-int 字典的内存高效实现？

Answer 1

您可以使用 IIBtree来自 Zope