内存效率:一个大字典或较小字典的字典？

我正在用Python(2.6)编写一个应用程序,它要求我使用字典作为数据存储.

我很好奇是否有更大的内存效率来拥有一个大字典,或者将其分解为许多(更多)更小的字典,然后有一个"索引"字典,其中包含对所有较小字典的引用.

我知道列表和词典通常会有很多开销.我在某处读到python内部分配了足够的空间,字典/列出项目的数量为2的幂.

我对python有足够的新意,我不确定是否还有其他意想不到的内部复杂性/类似的事情,这对普通用户来说并不明显,我应该考虑到这一点.

其中一个困难是知道2系统的功能如何计算"项目"？是每个键:对计为1项？这似乎很重要,因为如果你有一个100项单片词典,那么将分配空间100 ^ 2项.如果你有100个单项词典(1键:对),那么每个词典只会分配1 ^ 2(也就是没有额外的分配)？

任何清晰的信息都会非常有用!

三点建议:

使用一本字典.
它更容易,更直接,而其他人已经为您优化了这个问题.在您实际测量代码并追踪性能问题之前,您没有理由不做简单,直接的事情.

稍后优化.
如果你真的担心性能,那么抽象问题就要创建一个类来包装你最终使用的查找机制,并编写你的代码来使用这个类.如果您发现需要其他数据结构以获得更高性能,则可以稍后更改实施.

阅读哈希表.
字典是哈希表,如果你担心它们的时间或空间开销,你应该阅读它们是如何实现的.这是基础计算机科学.缺点是哈希表是:

平均情况O(1)查找时间

O(n)空间(预计约2n,取决于各种参数)

我不知道你在哪里读到它们是O(n ^ 2)空间,但如果它们是,那么它们就不会像今天的大多数语言那样广泛,实用.哈希表的这些不错的属性有两个优点:

O(1)查找时间意味着您不会为查找时间支付更大的字典,因为查找时间不依赖于大小.

O(n)空间意味着你不会从将字典分成更小的部分中获得太多收益.空间与元素的数量呈线性关系,因此许多小字典不会占用比一个大字体少得多的空间,反之亦然.如果它们是O(n ^ 2)空间,那就不是真的,但幸运的是,它们不是.

以下是一些可能有用的资源:

关于哈希表的维基百科文章给出了哈希表中使用的各种查找和分配方案的精彩列表.

在GNU计划的文件有多少,你可以指望的空间,以哈希表占用,包括为什么一个正式讨论一个很好的讨论"的空间由哈希表的使用量是成正比的表关联的数量".这可能会让你感兴趣.

如果您发现实际需要优化字典实现,可以考虑以下事项:

这是Python字典的C源代码,以防您需要所有细节.这里有大量的文档:

dictobject.h

dictobject.c

这是一个python实现,如果你不喜欢阅读C.
(感谢Ben Peterson)

在Java的Hashtable类文档讨论一下客座率是如何工作的,以及它们如何影响您空间站哈希占用.请注意,您的加载因子与需要重新加密的频率之间需要权衡.重做可能代价高昂.

如果你正在使用Python,那么你真的不应该担心这类事情.只需以最适合您需求的方式构建数据结构,而不是计算机.

这有点过早优化,而不是性能提升.如果某些东西实际上是瓶颈,那么就会对你的代码进行分析,但在那之前,让Python做它所做的事情,并专注于实际的编程任务,而不是底层的机制.

"简单"通常比"聪明"更好,特别是如果你没有经过考验的理由超越"简单".无论如何,"内存高效"是一个模糊的术语,当你考虑持久化,序列化,缓存,交换以及其他人已经考虑过的一大堆其他内容时会有权衡,所以在大多数情况下你不会需要.

认为"正确处理它的最简单方法"稍后进行优化.

过早优化bla bla,不要做bla bla.

我认为你错了两个额外分配的力量.我认为它只是两倍的乘数.x*2,而不是x ^ 2.

我在各种python邮件列表上看过几次这个问题.

关于内存,这里是一个这样的讨论的解释版本(该帖子想要存储数亿个整数):

如果你只想测试成员资格,set()比dict()更节省空间

gmpy有一个bitvector类型类,用于存储密集的整数集

Dicts保持在50%到30%之间,并且条目大约是12个字节(尽管真实数量会因平台而有所不同).

因此,您拥有的对象越少,您将要使用的内存越少,您将要执行的查找越少(因为您必须在索引中查找,然后在实际值中进行第二次查找) .

像其他人一样说,看看你的瓶颈.保持成员资格set()和值dict()可能会更快,但您将使用更多内存.

我还建议将它重新发布到一个特定于python的列表,例如comp.lang.python,它比我自己的知识渊博的人更多,他会给你各种有用的信息.

如果你的字典太大而不适合内存,你可能想看看ZODB,一个非常成熟的Python对象数据库.

db的'root'与字典具有相同的接口,您不需要立即将整个数据结构加载到内存中,例如,您可以通过提供开始和结束键来迭代结构的一部分.

它还提供事务和版本控制.