开发,设计,生活

编程语言

  • 2014-08-19 06:28:16 2014-08-26 05:38:20[U] 编程语言

    list 对象

    list 对象的定义

    list对象内部是使用数组实现,在数组中存储的是指针,指向要保存的对象。

    allocated是list中数组的大小,ob_size是当前已经使用的数组大小。

    typedef struct {
        // 可变长对象中有 ob_size,保存当前已经使用的数组大小
        PyObject_VAR_HEAD
        PyObject **ob_item; // 数组的指针
        Py_ssize_t allocated; // 分配的数组长度
    } PyListObject;
    


    list 对象的缓存

    list对象有缓存机制,对象在释放时会保存到空闲缓存池,待下一次申请的时候使用。 缓存池可以缓存80个list对象,缓存池满的时候list对象直接释放。

    从list对象的创建和销毁过程了解它的缓存机制(为了关注重点,代码被简化过)。

    // 缓存池的大小定义
    #define PyList_MAXFREELIST 80
    
    // 创建新的list对象
    PyObject* PyList_New(Py_ssize_t size)
    {
        PyListObject *op;
        size_t nbytes = size * sizeof(PyObject *);
        // 如果缓存有空闲,直接从缓存中分配list对象的内存
        if (numfree) {
            numfree--;
            op = free_list[numfree];
            _Py_NewReference((PyObject *)op);
        } else {
            op = PyObject_GC_New(PyListObject, &PyList_Type);
            if (op == NULL)
                return NULL;
        }
        if (size <= 0)
            op->ob_item = NULL;
        else {
            op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
            if (op->ob_item == NULL) {
                Py_DECREF(op);
                return PyErr_NoMemory();
            }
            memset(op->ob_item, 0, nbytes);
        }
        Py_SIZE(op) = size;
        op->allocated = size;
        _PyObject_GC_TRACK(op);
        return (PyObject *) op;
    }
    
    // 销毁list对象
    static void list_dealloc(PyListObject *op)
    {
        Py_ssize_t i;
        PyObject_GC_UnTrack(op);
        Py_TRASHCAN_SAFE_BEGIN(op)
        if (op->ob_item != NULL) {
            i = Py_SIZE(op);
            while (--i >= 0) {
                Py_XDECREF(op->ob_item[i]);
            }
            PyMem_FREE(op->ob_item);
        }
        // 保存list对象到空闲的缓存
        if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
            free_list[numfree++] = op;
        else
            Py_TYPE(op)->tp_free((PyObject *)op);
        Py_TRASHCAN_SAFE_END(op)
    }
    


    list 的插入,删除,添加操作

    list的内部实现是数组,所以在插入和删除的操作会引起内部元素的移动。在添加操作时,如果目前list对象分配的内存没有使用完,则直接在尾部追加。

    看下list的插入和添加操作。

    // 插入操作
    int PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
    {
        if (!PyList_Check(op)) {
            PyErr_BadInternalCall();
            return -1;
        }
        return ins1((PyListObject *)op, where, newitem);
    }
    
    static int ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
    {
        Py_ssize_t i, n = Py_SIZE(self);
        PyObject **items;
        if (v == NULL) {
            PyErr_BadInternalCall();
            return -1;
        }
        if (n == PY_SSIZE_T_MAX) {
            PyErr_SetString(PyExc_OverflowError,
                "cannot add more objects to list");
            return -1;
        }
        // 判断是否重新分配长度
        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;
    }
    
    // 添加操作
    int PyList_Append(PyObject *op, PyObject *newitem)
    {
        if (PyList_Check(op) && (newitem != NULL))
            return app1((PyListObject *)op, newitem);
        PyErr_BadInternalCall();
        return -1;
    }
    
    static int app1(PyListObject *self, PyObject *v)
    {
        Py_ssize_t n = PyList_GET_SIZE(self);
    
        assert (v != NULL);
        if (n == PY_SSIZE_T_MAX) {
            PyErr_SetString(PyExc_OverflowError,
                "cannot add more objects to list");
            return -1;
        }
    
        if (list_resize(self, n+1) == -1)
            return -1;
    
        Py_INCREF(v);
        PyList_SET_ITEM(self, n, v);
        return 0;
    }
    


    list对象总结

    1. list对象内部有定量的缓存,提高创建list对象的速度
    2. list对象的插入,删除操作成本较高,不适宜频繁操作。
    3. append操作速度较快。


    dict 对象

    dict对象的定义

    dict对象的实现内部是散列表,散列函数采用的开放地址法,理论上算法的时间复杂度是 O(1) 。

    dict对象在散列表小于8的时候,使用对象内部数组 ma_smalltable 的内存。

    // 字典内部数组,创建长度较小的散列时使用
    #define PyDict_MINSIZE 8
    
    // 散列表的数据项
    typedef struct {
        Py_ssize_t me_hash;
        PyObject *me_key;
        PyObject *me_value;
    } PyDictEntry;
    
    // dict 对象
    struct _dictobject {
        PyObject_HEAD
        Py_ssize_t ma_fill;  // 使用的计数 + 伪删除的dummy计数
        Py_ssize_t ma_used;  // 使用的计数
    
        Py_ssize_t ma_mask;
    
        PyDictEntry *ma_table; // 散列表内存指针
        PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
        PyDictEntry ma_smalltable[PyDict_MINSIZE]; // 内部优化,散列表较小时的内存
    };
    


    dict对象的缓存

    dict对象也有缓存机制,对象释放时保存到缓存池中,待下一次申请的时候使用。缓存池可以缓存80个dict对象,缓存池满的时候dict对象直接释放。

    从dict对象的创建和销毁过程了解它的缓存机制(为了关注重点,代码被简化过)。

    // 缓存池的大小定义
    #define PyDict_MAXFREELIST 80
    
    // 创建 dict 对象
    PyObject* PyDict_New(void)
    {
        register PyDictObject *mp;
        // 创建 dummy对象,在删除的时候占位使用
        if (dummy == NULL) { /* Auto-initialize dummy */
            dummy = PyString_FromString("<dummy key>");
            if (dummy == NULL)
                return NULL;
        }
        // 判断如果缓存有空闲,使用缓存中的 dict对象
        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 {
                INIT_NONZERO_DICT_SLOTS(mp);
            }
            assert (mp->ma_used == 0);
            assert (mp->ma_table == mp->ma_smalltable);
            assert (mp->ma_mask == PyDict_MINSIZE - 1);
        } else {
            mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
            if (mp == NULL)
                return NULL;
            EMPTY_TO_MINSIZE(mp);
        }
        mp->ma_lookup = lookdict_string;
    
        return (PyObject *)mp;
    }
    
    // 释放dict的函数
    static void dict_dealloc(register PyDictObject *mp)
    {
        register PyDictEntry *ep;
        Py_ssize_t fill = mp->ma_fill;
        PyObject_GC_UnTrack(mp);
        Py_TRASHCAN_SAFE_BEGIN(mp)
        for (ep = mp->ma_table; fill > 0; ep++) {
            if (ep->me_key) {
                --fill;
                Py_DECREF(ep->me_key);
                Py_XDECREF(ep->me_value);
            }
        }
        if (mp->ma_table != mp->ma_smalltable)
            PyMem_DEL(mp->ma_table);
        // 如果缓存还有空闲空间,则缓存释放的 dict 对象
        if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
            free_list[numfree++] = mp;
        else
            Py_TYPE(mp)->tp_free((PyObject *)mp);
        Py_TRASHCAN_SAFE_END(mp)
    }
    


    开放地址散列表的主要查找算法

    dict 对象散列查找算法,首先比较key是否相同,不相同则探测下一个位置,一直到找到元素,或者查找失败。在查找失败的时候,返回第一个可用的位置。

    static PyDictEntry *
    lookdict(PyDictObject *mp, PyObject *key, register long hash)
    {
        register size_t i;
        register size_t perturb;
        register PyDictEntry *freeslot;
        register size_t mask = (size_t)mp->ma_mask;
        PyDictEntry *ep0 = mp->ma_table;
        register PyDictEntry *ep;
        register int cmp;
        PyObject *startkey;
    
        // 查找散列位置
        i = (size_t)hash & mask;
        ep = &ep0[i];
        if (ep->me_key == NULL || ep->me_key == key)
            return ep;
    
        // 判断散列位置是否为删除后的占位对象
        if (ep->me_key == dummy)
            freeslot = ep;
        else {
            // 散列hash匹配,进一步查找
            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 {
                    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) {
                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 {
                    return lookdict(mp, key, hash);
                }
            }
            else if (ep->me_key == dummy && freeslot == NULL)
                freeslot = ep;
        }
        return 0;
    }
    


    dict 对象总结

    1. dict对象采用开放地址散列法。
    2. dict对象内部有定量的缓存,提高创建dict对象的速度。
    3. 对于长度较小的dict对象,直接使用对象内部的内存,无需二次分配内存,性能较好。