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

我需持〜250M对,所以它确实有紧.

你碰巧知道一个合适的实现(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个字节/对通常很难实现. 重新提问:是否有一个内存高效的int-int字典实现,使用相当少于49字节/对？

Answer 1

你可以使用Zope 的IIBtree

Answer 2

我不知道这是一次性解决方案,还是正在进行的项目的一部分,但是如果它是前者,是否会比开发时间优于内存使用的开发时间更便宜？即使每对64字节,你仍然只看15GB,这对于大多数桌面盒来说都很容易.

我认为正确的答案可能在SciPy/NumPy库中,但我对库不熟悉,无法告诉您确切的位置.

http://docs.scipy.org/doc/numpy/reference/

您可能还会在此主题中找到一些有用的想法: Python词典的内存有效替代方案