代码之家 › 专栏 › 技术社区 › Bolo

python中的内存高效int int dict

memory-optimization dictionary data-structures python

Bolo · 技术社区 · 14 年前

我需要一个python中的内存高效的int int dict,它将支持 O(对数N) 时间:

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

我要拿250米左右的鞋子,所以 真正地 一定要紧。

您是否知道合适的实现(python 2.7)?

编辑删除了不可能的要求和其他胡说八道。谢谢,克雷格和基洛坦!

重新措辞。下面是一个有1百万对的普通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字节 .

下面是一个2米整数数组:

>>> 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字典是否有一个内存高效的实现,它使用的字节/对远远小于49个?

6 回复 | 直到 12 年前

John La Rooy 14 年前

你可以使用 IIBtree 来自Zope

Community CDub 8 年前

我不知道这是一个一次性解决方案,还是正在进行的项目的一部分,但如果是前者,是不是在用比必要的开发人员时间更便宜的内存来优化内存使用?即使每对64个字节,您仍然只能看到15GB,这将很容易适合大多数桌面设备。

我认为正确的答案可能在scipy/numpy库中,但我对这个库还不够熟悉,无法确切地告诉你该在哪里查找。

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

您还可以在这个主题中找到一些有用的想法: Memory Efficient Alternatives to Python Dictionaries

Kylotan 14 年前

在任何实现(Python或其他)下,每个键/值对8个字节都是相当困难的。如果不能保证键是连续的,那么要么使用数组表示法在键之间浪费大量空间(同时需要某种死值来指示空键),要么需要维护一个单独的索引到键/值对,根据定义这对索引到键/值对每对超过8个字节(即使只有一小部分)。

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

rrauenza 12 年前

如果你是从整数映射过来的,那朱迪数组呢?这是一种稀疏的数组…使用字典实现空间的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,btw,所以我的基数可能会因为64位指针而膨胀)

Lennart Regebro 14 年前

看看上面的数据,这不是每个整数49个字节,而是25个字节。每个条目的其他24个字节是int对象本身。所以你需要一些比 二十五 每个条目的字节数。除非您还打算重新实现int对象,至少对于键散列是可能的。或者在C中实现它,在C中可以完全跳过对象(这是ZopesIIbtree所做的,如上所述)。

老实说,python字典的调优方式多种多样。打败它并不容易,但祝你好运。

Community CDub 8 年前

我已经实现了我自己的int字典, available here (BSD许可证)。简而言之,我使用 array.array('i') 存储按键排序的键值对。事实上,我保留了一个较小数组的字典(键值对存储在 key/65536 th数组)以加速插入时的移位和检索时的二进制搜索。每个数组按以下方式存储键和值:

key0 value0 key1 value1 key2 value2 ...

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

处理“密钥冲突”有三种可能的策略,即尝试为同一密钥分配不同的值。默认策略允许这样做。“删除”将删除该键并将其标记为碰撞,因此任何进一步尝试为其赋值都将无效。“叫喊”策略在任何覆盖尝试和对任何冲突密钥的任何进一步访问期间抛出异常。

请看 my answer 到 a related question 对我的方法有不同的描述。