Ray*_*Luo 22 python memory dictionary tuples list
关于不同python数据类型的内存消耗有很多问题和讨论.然而,其中很少(如果有的话)来到一个非常具体的场景.当你想在内存中存储很多键值数据时,哪个数据结构更节省内存,dict还是一个元组列表？
一开始我认为dict比元组列表更强大,并且权力必须有一些代价,实际上一个空的dict占用的内存比空列表或元组更多(参见Python结构的内存大小),所以我以为使用[(key1, value1), (key2, value2), ...]会比内存更有效{key1: value1, key2: value2, ...}.
看起来我错了.只需启动以下代码段,然后查看操作系统报告的内存消耗情况.我正在使用Windows XP,以便任务管理器告诉我,一个大字典只吃"40MB Ram和40MB VIRTURAL Ram",但是一个元组列表吃掉了60MB Ram和60MB Virtual 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")
更新:
感谢下面的一些评论.我想澄清一下:我在谈论内存效率.不,在这种情况下无需担心键值查找效率,让我们假设我的算法将通过迭代器逐个使用它们.
Mar*_*ers 26
你list的tuples增加了一层.你有3层物品:
虽然你dict唯一持有:
这是100万个元组加上列表来保存对它们的引用,这些引用比100万个缓存的哈希值占用更多内存.这里涉及的指针多了50%,很容易占到你看到的内存使用量的50%.
您的元组列表还有另一个缺点:查找时间.要在字典中找到匹配的密钥,存在O(1)复杂度成本.要在元组列表中执行相同操作,您必须扫描整个列表以获得O(n)成本.如果需要将键映射到值,请不要使用元组列表.
sen*_*rle 10
在这种情况下,你实际上得到的内存使用情况不完整.字典的总大小会以不规则的间隔翻倍,如果你在字典大小增加后比较这两个结构的大小,它会再次变大.一个带有递归大小函数的简单脚本(参见下面的代码)显示了一个非常清晰的模式:
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是正确的,元组列表中的元组增加了内存开销,取消了列表在字典上的内存优势.但平均而言,结果并不是字典更好; 这是字典大致相同.所以回答你原来的问题:
当你想在内存中存储很多键值数据时,哪个数据结构更节省内存,dict还是一个元组列表？
如果你所关心的只是记忆,这并不重要.
但是,请注意,迭代字典通常比迭代列表慢一些,因为没有好的方法可以避免迭代字典中的所有空容器.所以有一点权衡 - 字典在执行随机密钥查找时(更快),但在迭代时列表更快(一点点).字典在大多数情况下可能会更好,但在极少数情况下,列表可能会提供微观优化.
这是测试大小的代码.它可能不会为所有极端情况生成正确的结果,但它应该处理这样的简单结构而没有任何问题.(但是如果你发现任何问题,请告诉我.)
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