python - 内存效率 : One large dictionary or a dictionary of smaller dictionaries?

Question

我正在用 Python (2.6) 编写一个应用程序，需要我使用字典作为数据存储。

我很好奇拥有一个大字典是否更节省内存，或者将其分解为许多(很多)较小的字典，然后拥有一个包含对所有较小字典的引用的“索引”字典字典。

我知道列表和字典通常会产生很多开销。我在某处读到，python 在内部分配了足够的空间，字典/列表项的数量是 2 的幂。

我对 python 还很陌生，我不确定是否还有其他类似的意外内部复杂性/惊喜，这对普通用户来说并不明显，我应该考虑到这一点。

其中一个困难是知道 2 系统的力量如何计算“项目”？每个 key:pair 是否计为 1 个项目？知道这一点似乎很重要，因为如果您有一个 100 项的整体字典，那么将分配 100^2 项空间。如果您有 100 个单项字典(1 个键:对)，那么每个字典只会分配 1^2(也就是没有额外分配)？

任何明确列出的信息都会非常有帮助!

Answer 1

三个建议:

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

2. 稍后优化。
   如果您真的担心性能问题，那么将问题抽象为一个类来包装您最终使用的任何查找机制并编写代码来使用该类。如果您发现需要其他数据结构以获得更高的性能，您可以稍后更改实现。

3. 阅读哈希表。
   字典是 hash tables ，如果你担心它们的时间或空间开销，你应该阅读它们是如何实现的。这是基本的计算机科学。简短的是哈希表是:

   • 平均情况 O(1) 查找时间
   • O(n) 空间(预计大约 2n，取决于各种参数)

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

   1. O(1) 查找时间意味着您不会为拥有更大的字典而支付查找时间成本，因为查找时间不取决于大小。
   2. O(n) 空间意味着您将字典分解成更小的部分不会有任何收获。空间与元素的数量成线性关系，所以很多小字典不会比一个大字典占用更少的空间，反之亦然。如果它们是 O(n^2) 空间，这将是不正确的，但幸运的是，它们不是。

   这里还有一些可能会有所帮助的资源:

   • Wikipedia article on Hash Tables列出了哈希表中使用的各种查找和分配方案。
   • GNU Scheme documentation很好地讨论了您可以期望哈希表占用多少空间，包括正式讨论为什么“哈希表使用的空间量与表中的关联数量成正比” .这可能会让您感兴趣。

   如果您发现确实需要优化字典实现，可以考虑以下几点:

   • 这里是 Python 字典的 C 源代码，以防您需要所有详细信息。这里有丰富的文档:
     • dictobject.h
     • dictobject.c
   • 这里是 python implementation其中，如果你不喜欢读 C。
     (感谢 Ben Peterson)
   • Java Hashtable class docs谈谈负载因子是如何工作的，以及它们如何影响散列占用的空间。请注意，在您的负载系数和您需要重新散列 的频率之间进行权衡。重新散列的成本可能很高。