29

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

一开始我认为 dict 比元组列表更强大，而且这种能力必须付出一些代价，实际上空 dict 确实比空列表或元组占用更多内存（请参阅Python 结构的内存大小），所以我认为 using[(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")

更新：

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

4

2 回答 2

31

你list的tuples 增加了一个额外的层。您有3层项目：

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

而你dict唯一的持有：

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

正是这 100 万个元组加上保存对它们的引用的列表比 100 万个缓存散列占用更多的内存。这里涉及的指针多出 50%，很容易说明您看到的内存使用量增加了 50%。

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

于 2013-03-26T15:50:53.460 回答
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增长而继续存在。（您可以使用您的方法对此进行测试——尝试设置inear 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
于 2013-03-26T17:24:04.400 回答