这篇文章主要是写一些自己对Python原生Dict的理解和感悟
1.对比
游戏里面很多策划表是以Python Dict的形式存在的，并且这些Python Dict是常驻内存的，在Python的GC机制里面也是存在于最老的generation里面的。那么Python Dict到底有多耗内存呢？我利用pymalloctrace做过一个简单的对比。
Case One：
构建一个如下数据
d = {
1 : {1:1, 2:4, 3:9, ... 19:361}
2 : {...}
...
9999: {...}
}
利用pytracemalloc看一下它的内存占用量到底有多少，测试代码如下：
1 # -*- coding:utf-8 -*-
2
3 import os
4 import sys
5 import tracemalloc
6
7 tracemalloc.start()
8
9 d = {}
10 for i in xrange(1, 10000):
11 sub_d = {}
12 for j in xrange(1, 20):
13 sub_d[j] = j*j
14 d[i] = sub_d
15
16 snapshot = tracemalloc.take_snapshot()
17 statis = snapshot.statistics("lineno")
18 total = 0
19 for stat in statis:
20 total += stat.size
21
22 for stat in statis[:10]:
23 print stat
24
25 print total / 1024.0 / 1024.0, "M"
最后输出的结果：
test_dict.py:13: size=8208 KiB, count=10731, average=783 B
test_dict.py:11: size=2734 KiB, count=9999, average=280 B
test_dict.py:14: size=768 KiB, count=1, average=768 KiB
test_dict.py:10: size=229 KiB, count=237, average=992 B
test_dict.py:16: size=456 B, count=1, average=456 B
11.66065979 M
11M，占用最多的地方就是在Dict被赋值的地方。
Case Two
接下来换一种方式：数据使用tuple进行存储，索引用dict，输入格式如下：
value_index = {1 : 0, 2 : 1, ... 19: 18}
top_index = {1 : 0, 2 : 1, ... 9999 : 9998}
d = (
(1, 4, 9, ..., 361),
(1, 4, 9, ..., 361),
...
)
测试代码如下：
1 # -*- coding:utf-8 -*-
2
3 import os
4 import sys
5 import tracemalloc
6
7 def sub_gen():
8 for i in xrange(1, 20):
9 yield i*i
10
11 def gen():
12 for i in xrange(1, 10000):
13 yield tuple(sub_gen())
14
15 tracemalloc.start()
16
17 value_index = {}
18 for i in xrange(1, 20):
19 value_index[i] = i - 1
20
21 top_index = {}
22 for i in xrange(1, 10000):
23 top_index[i] = i - 1
24
25 d = tuple(gen())
26
27 snapshot = tracemalloc.take_snapshot()
28 statis = snapshot.statistics("lineno")
29 total = 0
30 for stat in statis:
31 total += stat.size
32
33 for stat in statis[:10]:
34 print stat
35
36 print total / 1024.0 / 1024.0, "M"
运行结果如下：
test_tuple.py:13: size=2031 KiB, count=10000, average=208 B
test_tuple.py:23: size=998 KiB, count=239, average=4278 B
test_tuple.py:9: size=478 KiB, count=494, average=992 B
test_tuple.py:22: size=229 KiB, count=237, average=992 B
test_tuple.py:12: size=229 KiB, count=237, average=992 B
test_tuple.py:25: size=78.0 KiB, count=2, average=39.0 KiB
test_tuple.py:19: size=768 B, count=1, average=768 B
test_tuple.py:27: size=456 B, count=1, average=456 B
test_tuple.py:21: size=280 B, count=1, average=280 B
3.95300292969 M
结果才3M，为什么会差距这么大，原因就是在tuple和dict的内部实现的不同。
2.Dict内部实现说明
Python Dict是一个Hash表，其解决冲突的方式是开放寻址法。在Dict中存储数据是一个线性数组，key值通过hash函数转换为一个整数，对应于数组中的索引，如果此索引下的数据没有被占用，怎将数据存储；否则，当存在冲突的时候，开放寻址法利用冲突函数找到下一个索引，重复上面的步骤。
基于某些理论，当数组中可用空间小于1/3时，此线性数据将会进行扩展，下面是Python Dict中在插入数据之后会进行检查，如果空间不满足要求则进行扩展。
# in dictobject.c
static int
dict_set_item_by_hash_or_entry(register PyObject *op, PyObject *key,
long hash, PyDictEntry *ep, PyObject *value)
{
....
if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))
return 0;
return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);
}
我们看到最后一段，dict的扩容将会以使用数量的2倍或者4倍进行扩容，保守上说整个线性数组中有1/3的空间是没有用的。
3.Tuple内部实现说明
tuple的内部实现则很简单。
typedef struct {
PyObject_VAR_HEAD
PyObject *ob_item[1];
} PyTupleObject;
ob_item存储tuple数据，可以理解为一个线性的数组，其大小在初始化的时候已经确定且无法改变。
4.小结
Python dict和tuple内存占用为何差这么多，原因不仅是上面提到的线性数组利用率的问题，还有线性数组存储的数据：tuple只是存储PyObject，但是dict要存储对应的hash值，key和value，这也是导致内存占用差距变大的原因。