Python内存消耗: dict VS list of tuples

Question

有很多关于不同 python 数据类型的内存消耗的问题和讨论。然而，他们中很少有人(如果有的话)遇到非常具体的情况。当你想在内存中存储大量的键值数据时，哪种数据结构更节省内存，字典还是元组列表？

一开始我认为 dict 比元组列表更强大，而且这种力量必须付出一些代价，实际上空 dict 确实比空列表或元组占用更多内存(参见 In-memory size of a Python structure )，所以我认为使用[(key1, value1), (key2, value2), ...] 会比 {key1: value1, key2: value2, ...} 更节省内存>.

看来我错了。只需启动以下代码片段，然后查看您的操作系统报告的内存消耗。我正在使用 Windows XP，因此任务管理器告诉我，一个大字典“只”吃掉了 40MB 内存和 40MB 虚拟内存，但元组列表吃掉了 60MB 内存和 60MB 虚拟内存。

怎么可能？

from sys import getsizeof as g
raw_input('ready, press ENTER')
i = 1000000
#p = [(x, x) for x in xrange(i)] # Will print 4,348,736 40,348,736
p = dict((x, x) for x in xrange(i)) # Will print 25,165,964 37,165,964
print g(p), g(p) + sum(g(x) for x in p)
raw_input("Check your process's memory consumption now, press ENTER to exit")

更新:

感谢下面的一些评论。我想澄清一下:我说的是内存效率。不，在这种情况下无需担心键值查找效率，假设我的算法将通过迭代器一一消耗它们。

Answer 1

您的 tuple 的 list 添加了一个额外的层。您有 3 层项目:

• 长度为100万的外层列表，所以100万个指针
  • 100 万个 2 槽元组，因此 200 万个指针
    • 200 万个对 100 万个整数值的引用

而您的 dict 仅适用:

• 带有 200 万个指针的字典(包括 100 万个缓存哈希)+ 用于增长表的额外空间
  • 200 万个对 100 万个整数值的引用

正是这 100 万个元组加上保存对它们的引用的列表比 100 万个缓存的哈希值占用更多的内存。这里涉及多 50% 的指针，很容易解释您看到的多 50% 的内存使用。

您的元组列表还有一个缺点:查找时间。要在 dict 中找到匹配的键，需要 O(1) 复杂度成本。要在元组列表中执行相同操作，您必须潜在地扫描整个列表以获得 O(n) 成本。如果您需要将键映射到值，请不要使用元组列表。