9

我需要一个 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）吗？

编辑删除了不可能的要求和其他废话。谢谢，克雷格和凯洛坦！

改写。这是一个包含 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 个字节/对？

4

6 回答 6

6

你可以使用Zope的IIBtree

于 2010-10-26T11:46:51.530 回答
5

我不知道这是一次性解决方案，还是正在进行的项目的一部分，但如果是前者，是否比开发人员优化内存使用所需的时间更便宜？即使每对 64 字节，您仍然只能看到 15GB，这足以轻松放入大多数台式机盒中。

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

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

您可能还会在此线程中找到一些有用的想法： Python 字典的内存高效替代方案

于 2010-10-26T13:59:25.877 回答
4

在任何实现（Python 或其他方式）下，每个键/值对 8 个字节都非常困难。如果你不能保证键是连续的，那么要么你会通过使用数组表示来浪费键之间的大量空间（以及需要某种死值来指示空键），或者你'd 需要为键/值对维护一个单独的索引，根据定义，该索引将超过每对 8 个字节（即使只是少量）。

我建议您使用数组方法，但最好的方法将取决于我期望的键的性质。

于 2010-10-26T11:47:21.697 回答
3

如果您从整数映射，那么 Judy 数组怎么样？它是一种稀疏数组...使用字典实现空间的 1/4。

朱迪：

$ cat j.py ; time python j.py 
import judy, random, sys
from guppy import hpy
random.seed(0)
h = hpy()
h.setrelheap()
d = judy.JudyIntObjectMap()
for _ in xrange(4000000):
    d[random.randint(0, sys.maxint)] = random.randint(0, sys.maxint)

print h.heap()
Partition of a set of 4000004 objects. Total size = 96000624 bytes.
 Index  Count   %     Size   % Cumulative  % Kind (class / dict of class)
     0 4000001 100 96000024 100  96000024 100 int
     1      1   0      448   0  96000472 100 types.FrameType
     2      1   0       88   0  96000560 100 __builtin__.weakref
     3      1   0       64   0  96000624 100 __builtin__.PyJudyIntObjectMap

real    1m9.231s
user    1m8.248s
sys     0m0.381s

字典：

$ cat d.py ; time python d.py   
import random, sys
from guppy import hpy
random.seed(0)
h = hpy()
h.setrelheap()
d = {}
for _ in xrange(4000000):
    d[random.randint(0, sys.maxint)] = random.randint(0, sys.maxint)

print h.heap()
Partition of a set of 8000003 objects. Total size = 393327344 bytes.
 Index  Count   %     Size   % Cumulative  % Kind (class / dict of class)
     0      1   0 201326872  51 201326872  51 dict (no owner)
     1 8000001 100 192000024  49 393326896 100 int
     2      1   0      448   0 393327344 100 types.FrameType

real    1m8.129s
user    1m6.947s
sys     0m0.559s

~1/4 的空间：

$ echo 96000624 / 393327344 | bc -l
.24407309958089260125

（我使用的是 64 位 python，顺便说一句，所以我的基数可能会因 64 位指针而膨胀）

于 2013-05-21T21:42:15.000 回答
2

查看上面的数据，这不是每个 int 49 个字节，而是 25 个。每个条目的其他 24 个字节是 int 对象本身。因此，您需要每个条目显着小于25个字节的内容。除非您还打算重新实现 int 对象，否则至少对于键散列是可能的。或者在 C 中实现它，您可以在其中完全跳过对象（这就是 Zopes IIBTree 所做的，如上所述）。

老实说，Python 字典在各种方面都经过了高度调整。打败它并不容易，但祝你好运。

于 2010-12-28T20:40:20.277 回答
1

我已经实现了自己的 int-int 字典，可在此处获得（BSD 许可证）。简而言之，我array.array('i')用来存储按键排序的键值对。事实上，我保留了一个较小数组的字典（键值对存储在第key/65536th 数组中）而不是一个大数组，以便在插入期间加快移位和检索期间的二进制搜索。每个数组以下列方式存储键和值：

key0 value0 key1 value1 key2 value2 ...

实际上，它不仅是一个 int-int 字典，而且是一个通用的 object-int 字典，其中对象被简化为它们的哈希值。因此，hash-int 字典可以用作一些持久存储字典的缓存。

处理“键冲突”有三种可能的策略，即尝试为同一个键分配不同的值。默认策略允许它。“删除”删除键并将其标记为冲突，因此任何进一步尝试为其分配值的尝试都将无效。“大喊”策略在任何覆盖尝试期间以及对任何冲突键的任何进一步访问时都会引发异常。

请参阅我对相关问题的回答，以获得对我的方法的不同措辞描述。

于 2010-12-28T18:35:55.930 回答