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

1
2
3
4

#define PyObject_HEAD                   \
    _PyObject_HEAD_EXTRA                \
    Py_ssize_t ob_refcnt;               \
    struct _typeobject *ob_type;

1
2
3

typedef struct _object {
    PyObject_HEAD
} PyObject;

1
2
3
4
5
6
7

#define PyObject_VAR_HEAD               \
    PyObject_HEAD                       \
    Py_ssize_t ob_size; // 可变部分的元素数量

typedef struct {
    PyObject_VAR_HEAD
} PyVarObject;

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;

 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 */
};

 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);
    }
    ...
}

1

#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))

 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);
    ...
}

 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;
}

 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 个槽的哈希表
};

 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 */
};

 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;
}

 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;
    }
    ...
}