logo标签列表

Python内存消耗：字典 VS 元组列表

pythonlistdictionarymemorytuples
30

有很多关于不同Python数据类型的内存消耗的问题和讨论。然而，很少有人（如果有的话）针对一个非常具体的场景进行讨论。当你想要在内存中存储大量的键值数据时，哪种数据结构更节省内存，在字典和元组列表之间选择？

起初，我认为字典比元组列表更强大，这种力量必须付出一些代价，实际上，一个空字典占用的内存比一个空列表或元组多（请参见Python结构的内存大小），所以我认为使用[(key1, value1), (key2, value2), ...]比{key1: value1, key2: value2, ...}更节省内存。

看起来我错了。只需运行以下代码片段，并查看操作系统报告的内存消耗。我正在使用Windows XP，因此任务管理器告诉我，一个大型字典仅占用“仅有”的40MB RAM和40MB虚拟RAM，但是一个元组列表却占用了60MB RAM和60MB虚拟RAM。

怎么会这样呢？

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")

更新:

感谢下面一些评论。我想澄清一下：我在谈论内存效率。在这种情况下，不需要担心键值查找效率，假设我的算法将通过迭代器逐个使用它们。

你问错了问题。如果你需要键值查找，那么使用字典。如果你需要一个数组，那么使用列表或元组。 - Hai Vu
Python为字典保留了一个哈希表。这个链接来自于另一个答案，我认为，字典在查找方面更快，而元组使用的内存较少。 - mbowden
对于某些类型的数据，您可以使用比您提供的两个选项更优化的东西，例如 trie。 - wRAR
1
高效用于什么？用于高效利用内存还是进行快速查找？ - Brian Neal
2个回答
34

您的list中包含一个额外的层级。您有3个项目层级：

  • 长度为100万个元素的外部列表，因此有100万个指针
    • 100万个2个插槽元组，因此有200万个指针
      • 200万个对100万个整数值的引用

而您的dict仅包含：

  • 带有200万个指针+额外空间以扩展表的dict（包括100万个缓存散列）
  • 200万个对100万个整数值的引用

正是这1百万个元组加上保存对它们的引用的列表占用了比1百万个缓存散列更多的内存。这里涉及到50％以上的指针，轻松解释了您看到的50％以上的内存使用。

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

我认为你对于额外的层级的事情是正确的。那么在这种情况下，即使我只想“持有”这些数据，你认为字典仍然是最节省内存的吗？（假设我不需要随机查找。） - RayLuo
@Iceberg：我不会保留这些数据。如果你不需要在其中查找东西，那还有什么意义呢？你也可以使用一个平的元组，这样就不需要嵌套对了；你仍然可以轻松地重新创建这些对。 - Martijn Pieters
我想要的是将它们保持并迭代它们。使用平坦元组技巧可能会有所帮助，但代价是失去可读性。 - RayLuo
@Iceberg：成对迭代：在列表中迭代每两个元素 - Martijn Pieters
13

在这种情况下，您实际上得到了内存使用的不完整图片。字典的总大小会不定期地增加一倍以上，如果您比较字典大小增加后这两个结构的大小，那么它又会更大。一个具有递归大小函数的简单脚本（请参见下面的代码）显示出了一个相当清晰的模式：

i:  2  list size:  296  dict size:  328  difference:  -32
i:  3  list size:  392  dict size:  352  difference:  40
i:  4  list size:  488  dict size:  376  difference:  112
i:  5  list size:  616  dict size:  400  difference:  216
i:  7  list size:  808  dict size:  1216  difference:  -408
i:  10  list size:  1160  dict size:  1288  difference:  -128
i:  13  list size:  1448  dict size:  1360  difference:  88
i:  17  list size:  1904  dict size:  1456  difference:  448
i:  23  list size:  2480  dict size:  3904  difference:  -1424
i:  31  list size:  3328  dict size:  4096  difference:  -768
i:  42  list size:  4472  dict size:  4360  difference:  112
i:  56  list size:  5912  dict size:  4696  difference:  1216
i:  74  list size:  7880  dict size:  5128  difference:  2752
i:  100  list size:  10520  dict size:  14968  difference:  -4448
i:  133  list size:  14024  dict size:  15760  difference:  -1736
i:  177  list size:  18672  dict size:  16816  difference:  1856

当 i 增大时，这种模式会继续下去。 （您可以使用自己的方法测试此内容-尝试将 i 设置在接近 2636744 的位置。该字典的大小在那一点上更大，至少对我来说是这样。）Martijn 是正确的，元组列表中的元组会增加内存开销，抵消了列表比字典更具有内存优势的优势。 但结果平均而言，并不是字典更好；它只是与字典相似。因此，针对您最初的问题：

当您想要在内存中存储大量键值数据时，哪种数据结构更节省内存，字典还是元组列表？

如果您所关心的仅仅是内存，那么实际上并没有什么影响。

然而，请注意，遍历字典通常比遍历列表略慢，因为无法避免遍历字典中所有空桶。因此存在一些权衡 - 字典用于随机键查找（快得多），但列表在迭代时速度（稍微）更快。字典大多数情况下可能会更好，但在一些罕见情况下，列表可能提供微小的优化。

以下是测试大小的代码。它可能无法为所有边缘情况生成正确结果，但对于像这样的简单结构，它应该没有任何问题。（但如果您遇到任何问题，请让我知道。）

import sys, collections, itertools, math

def totalsize(x):
    seen = set()
    return ts_rec(x, seen)

def ts_rec(x, seen):
    if id(x) in seen:
        return 0
    else:
        seen.add(id(x))

    x_size = sys.getsizeof(x)
    if isinstance(x, collections.Mapping):
        kv_chain = itertools.chain.from_iterable(x.iteritems())
        return x_size + sum(ts_rec(i, seen) for i in kv_chain)
    elif isinstance(x, collections.Sequence):
        return x_size + sum(ts_rec(i, seen) for i in x)
    else:
        return x_size

for i in (10 ** (e / 8.0) for e in range(3, 19)):
    i = int(i)
    lsize = totalsize([(x, x) for x in xrange(i)])
    dsize = totalsize(dict((x, x) for x in xrange(i)))

    print "i: ", i,
    print " list size: ", lsize, " dict size: ", dsize,
    print " difference: ", lsize - dsize
感谢您的帮助尝试。至少您比那些评论我的问题的人更好地理解了原始问题。所以我对您的观点的理解是“这取决于要容纳多少项，如果长度已知且固定，最好有一个基准”。顺便说一下，我修改了您的脚本为for i in (10 ** (e /8.0) for e in range(3, 49)):，并且发现在i=42169、56234、74989等直到i=1000000时，字典总是优于元组列表。哦，谢谢您提到了迭代速度。 - RayLuo
@Iceberg，是的，这大概就是我的意思。但我想要补充的是，除非你在进行一些严肃的微观优化，否则基准测试并不值得麻烦；使用对你的问题有实际意义的结构。另一方面，如果你正在进行微观优化，并且不关心随机键访问，那么你可能会从一个平面列表中获得最佳结果，就像Martijn建议的那样。 - senderle
当人们说“微优化”时，可能意味着一种不值得付出努力的努力？但在这种面向内存的情况下，加/减差异可以范围从2%到71%。这是很显著的！此外，字典在语义上类似于元组列表，但不是平面列表。总之，现在我们知道了所有的利弊，所以我们可以在特定情况下选择其中任何一个。感谢所有为本帖做出贡献的人！ - RayLuo
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接