1. Why Dictionary Lookups Are Faster Than List Lookups
First, take a look at the following piece of code.
1
2
3
4
5
6
7
8
9
10
11
12
13
| from time import time
t = time()
data = [chr(i) for i in range(97, 123)]
# data = dict.fromkeys(data,True)
print data
for i in range(9999999):
after_filter = []
for find in ['aa', 'b', 'cc', 'd', 'ee']:
if find not in data:
after_filter.append(find)
print after_filter
print time() - t
|
Run it as is:
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
['aa', 'cc', 'ee']
24.5699999332
After removing the comment on data = dict.fromkeys(data,True):
{'a': True, 'c': True, 'b': True, 'e': True, 'd': True, 'g': True, 'f': True, 'i': True, 'h': True, 'k': True, 'j': True, 'm': True, 'l': True, 'o': True, 'n': True, 'q': True, 'p': True, 's': True, 'r': True, 'u': True, 't': True, 'w': True, 'v': True, 'y': True, 'x': True, 'z': True}
['aa', 'cc', 'ee']
17.8080000877
Repeated many times, the result does not vary by more than 1 second. Why does converting the list into a dictionary with the dict.fromkeys function make it run noticeably faster?
A Python dictionary uses a hash table, so the complexity of a lookup is O(1), while a list is really an array; searching a list requires traversing the whole list, with complexity O(n). So for operations such as member lookup and access, a dictionary is faster than a list. Below, let us look together at how the list and dictionary structures are implemented in the Python source code.
2. Common Objects in the Python Source Code
All objects in Python inherit from PyObject or PyVarObject. Objects that inherit from PyObject have a fixed length, such as int. Objects that inherit from PyVarObject have a variable length, such as list and dict. PyObject and PyVarObject share the same header, PyObject_HEAD.
Defined in include/object.h
1
2
3
4
| #define PyObject_HEAD \
_PyObject_HEAD_EXTRA \
Py_ssize_t ob_refcnt; \
struct _typeobject *ob_type;
|
_PyObject_HEAD_EXTRA is a doubly linked list structure used for garbage collection. ob_refcnt is the object’s reference count; when there are no references to it, the memory is reclaimed automatically. ob_type is a pointer to the type object and determines the object’s type.
Defined in include/object.h
1
2
3
| typedef struct _object {
PyObject_HEAD
} PyObject;
|
Defined in include/object.h
1
2
3
4
5
6
7
| #define PyObject_VAR_HEAD \
PyObject_HEAD \
Py_ssize_t ob_size; // 可变部分的元素数量
typedef struct {
PyObject_VAR_HEAD
} PyVarObject;
|
PyVarObject contains a set of objects, whose count is given by ob_size.
3. How Lists Are Implemented in Python
include/listobject.h
1
2
3
4
5
6
7
| #define PyList_MAXFREELIST 80
typedef struct {
PyObject_VAR_HEAD // 表示变长对象，其中的 ob_size 表示实际使用的内存大小
PyObject **ob_item; // 列表元素所在内存块的首地址
Py_ssize_t allocated; // 列表总共分配的内存数量
} PyListObject;
|
Objects/listobject.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| static PyMethodDef list_methods[] = {
{"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc},
{"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc},
{"__sizeof__", (PyCFunction)list_sizeof, METH_NOARGS, sizeof_doc},
{"append", (PyCFunction)listappend, METH_O, append_doc},
{"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc},
{"extend", (PyCFunction)listextend, METH_O, extend_doc},
{"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc},
{"remove", (PyCFunction)listremove, METH_O, remove_doc},
{"index", (PyCFunction)listindex, METH_VARARGS, index_doc},
{"count", (PyCFunction)listcount, METH_O, count_doc},
{"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
{"sort", (PyCFunction)listsort, METH_VARARGS | METH_KEYWORDS, sort_doc},
{NULL, NULL} /* sentinel */
};
|
In the file that defines the list, the C functions corresponding to Python’s built-in list methods are defined. Below is a quick look at the implementation logic of these functions.
Objects/listobject.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| PyList_New(Py_ssize_t size)
{
...
// 如果缓冲池非空, 从缓冲池取
if (numfree) {
numfree--;
op = free_list[numfree];
_Py_NewReference((PyObject *)op);
...
} else {
// 否则, 申请新的内存空间
op = PyObject_GC_New(PyListObject, &PyList_Type);
...
}
if (size <= 0)
op->ob_item = NULL;
else {
...
// 初始化
memset(op->ob_item, 0, nbytes);
}
...
}
|
Call flow: listappend -> app1 -> after list_resize +1, PyList_SET_ITEM
include/listobject.h
1
| #define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))
|
Objects/listobject.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated;
Py_ssize_t allocated = self->allocated;
// 如果内存大小够用，并且新内存大小超过之前的一半，则需要分配新内存
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SIZE(self) = newsize;
return 0;
}
//否则分配新的内存空间
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
...
}
|
list_resize() requests a bit more space than needed in order to avoid frequent memory operations; the growth trend is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, … In fact, memory is allocated by calling C’s realloc.
Call flow: listinsert -> ins1 -> list_resize +1, then shift the elements and insert the new data.
Objects/listobject.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
...
if (list_resize(self, n+1) == -1)
return -1;
// 如果插入位置为负数，则加上列表长度一次，如果依然为负数，则插在首位
if (where < 0) {
where += n;
if (where < 0)
where = 0;
}
// 如果插入位置超过列表长度，则插在列表末尾处
if (where > n)
where = n;
items = self->ob_item;
// 向后移动元素，再插入新的数据
for (i = n; --i >= where; )
items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;
return 0;
}
|
The other methods are not listed one by one here.
4. How Dictionaries Are Implemented in Python
A dictionary in Python is implemented with a hash table. A hash table is an array whose index is obtained by applying a hash function to the key; collisions are resolved with the open addressing method.
Include/dictobject.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| typedef struct {
Py_ssize_t me_hash; //用于缓存 me_key 的哈希值，避免每次查询都需要计算 hash
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;
typedef struct _dictobject PyDictObject;
struct _dictobject {
PyObject_HEAD
Py_ssize_t ma_fill; //表示所有激活元素（active entry）和虚拟元素（dummy entry）的计数。
Py_ssize_t ma_used; //所有激活元素的计数
Py_ssize_t ma_mask; //哈希表的位掩码，这个表中包含 ma_mask + 1 个哈希槽(slot)。
PyDictEntry *ma_table; //PyDictEntry 结构体的数组， PyDictEntry 包含 key 对象、value 对象，以及 key 的哈希；
PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);//用于查找 key 的函数指针
PyDictEntry ma_smalltable[PyDict_MINSIZE]; //最小有 8 个槽的哈希表
};
|
The above is the state transition diagram for a dictionary key. If a key is deleted, the entry is set to dummy; it is not really removed. An entry in the dummy state becomes active again after a new element is inserted.
Objects/dictobject.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| static PyMethodDef mapp_methods[] = {
...
sizeof__doc__},
{"has_key", (PyCFunction)dict_has_key, METH_O,
has_key__doc__},
{"get", (PyCFunction)dict_get, METH_VARARGS,
get__doc__},
{"setdefault", (PyCFunction)dict_setdefault, METH_VARARGS,
setdefault_doc__},
{"pop", (PyCFunction)dict_pop, METH_VARARGS,
pop__doc__},
{"popitem", (PyCFunction)dict_popitem, METH_NOARGS,
popitem__doc__},
{"keys", (PyCFunction)dict_keys, METH_NOARGS,
keys__doc__},
{"items", (PyCFunction)dict_items, METH_NOARGS,
items__doc__},
{"values", (PyCFunction)dict_values, METH_NOARGS,
values__doc__},
{"viewkeys", (PyCFunction)dictkeys_new, METH_NOARGS,
viewkeys__doc__},
{"viewitems", (PyCFunction)dictitems_new, METH_NOARGS,
viewitems__doc__},
{"viewvalues", (PyCFunction)dictvalues_new, METH_NOARGS,
viewvalues__doc__},
{"update", (PyCFunction)dict_update, METH_VARARGS | METH_KEYWORDS,
update__doc__},
{"fromkeys", (PyCFunction)dict_fromkeys, METH_VARARGS | METH_CLASS,
fromkeys__doc__},
{"clear", (PyCFunction)dict_clear, METH_NOARGS,
clear__doc__},
{"copy", (PyCFunction)dict_copy, METH_NOARGS,
copy__doc__},
{"iterkeys", (PyCFunction)dict_iterkeys, METH_NOARGS,
iterkeys__doc__},
{"itervalues", (PyCFunction)dict_itervalues, METH_NOARGS,
itervalues__doc__},
{"iteritems", (PyCFunction)dict_iteritems, METH_NOARGS,
iteritems__doc__},
{NULL, NULL} /* sentinel */
};
|
Objects/dictobject.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| PyObject *
PyDict_New(void)
{
register PyDictObject *mp;
// 初始化dummy
if (dummy == NULL) { /* Auto-initialize dummy */
dummy = PyString_FromString("<dummy key>");
if (dummy == NULL)
return NULL;
}
...
// 如果缓冲池可用，取最后一个可用对象，并将其清空、初始化。
if (numfree) {
mp = free_list[--numfree];
assert (mp != NULL);
assert (Py_TYPE(mp) == &PyDict_Type);
_Py_NewReference((PyObject *)mp);
if (mp->ma_fill) {
EMPTY_TO_MINSIZE(mp);
} else {
/* At least set ma_table and ma_mask; these are wrong
if an empty but presized dict is added to freelist */
INIT_NONZERO_DICT_SLOTS(mp);
}
...
} else {
// 否则，申请新的内存对象
mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
if (mp == NULL)
return NULL;
...
}
// 设置搜索方法
mp->ma_lookup = lookdict_string;
...
return (PyObject *)mp;
}
|
A note here: the dictionary object’s buffer pool free_list is an array of length 80.
Call flow: dict_get -> lookdict_string -> lookdict, returning the value found.
Objects/dictobject.c
1
2
3
4
5
6
7
8
9
10
| static PyObject *
dict_get(register PyDictObject *mp, PyObject *args)
{
...
ep = (mp->ma_lookup)(mp, key, hash);
...
val = ep->me_value;
...
return val;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| static PyDictEntry *
lookdict(PyDictObject *mp, PyObject *key, register long hash)
{
...
register PyDictEntry *freeslot;
register size_t mask = (size_t)mp->ma_mask; // 掩码等于数组长度 - 1
...
// 计算所在 entry 位置.
i = (size_t)hash & mask;
ep = &ep0[i];
// 如果找到，则返回 entry
if (ep->me_key == NULL || ep->me_key == key)
return ep;
// 如果是 dummy，赋值给 freeslot，freeslot 用来指向探测序列中第一个处于dummy 态的 entry。如果搜索失败，则返回 freeslot，其指向的 enery ->me_value 为 NULL
if (ep->me_key == dummy)
freeslot = ep;
else {
// 搜索成功
if (ep->me_hash == hash) {
startkey = ep->me_key;
Py_INCREF(startkey);
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
if (cmp < 0)
return NULL;
if (ep0 == mp->ma_table && ep->me_key == startkey) {
if (cmp > 0)
return ep;
}
else {
/* The compare did major nasty stuff to the
* dict: start over.
* XXX A clever adversary could prevent this
* XXX from terminating.
*/
return lookdict(mp, key, hash);
}
}
freeslot = NULL;
}
// 冲突时，二次探测
for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
i = (i << 2) + i + perturb + 1;
ep = &ep0[i & mask];
if (ep->me_key == NULL)
return freeslot == NULL ? ep : freeslot;
if (ep->me_key == key)
return ep;
if (ep->me_hash == hash && ep->me_key != dummy) {
...
}
else if (ep->me_key == dummy && freeslot == NULL)
freeslot = ep;
}
...
}
|
5. References
