美文网首页
python 源码阅读(一)listObject

python 源码阅读(一)listObject

作者: 寒夏凉秋 | 来源:发表于2017-05-20 12:09 被阅读0次

    python中 list的实现

    python中的LIST非常强大,它既有数组的下标查询优势,
    又有链表这样动态增减的高速率;

    列表对象的C语言结构体:

    typedef struct {
      
        int ob_refcnt;    # 列表对象引用计数
       
        struct _typeobject *ob_type; # 列表类型对象      
       
        int ob_size;  # 列表元素的长度
        //这三个也可以用一个结构体 PyObject_VAR_HEAD 来代替
        
        PyObject **ob_item;  # 真正存放列表元素容器的指针,list[0] 就是 ob_item[0]
        
        Py_ssize_t allocated;  # 当前列表可容纳的元素大小
    } PyListObject;
    

    满足条件:

    1. 0 <= ob_size <= allocated
    2. len(list) == ob_size
    3. ob_item == NULL 时 ob_size == allocated == 0

    ref_count,ob_size,allocated, ob_item -> list[]
    列表对象的创建:

    // 列表缓冲池, PyList_MAXFREELIST为80
    static PyListObject *free_list[PyList_MAXFREELIST];
    //缓冲池当前大小
    static int numfree = 0;
    
    PyObject *PyList_New(Py_ssize_t size)
    {
        PyListObject *op; //列表对象
        size_t nbytes;    //创建列表对象需要分配的内存大小
    
        if (size < 0) {
            PyErr_BadInternalCall();
            return NULL;
        }
        //如果size小于0 直接返回NULL,创建失败
        /* Check for overflow without an actual overflow,
         *  which can cause compiler to optimise out */
        if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
            return PyErr_NoMemory();
            //如果size超过了python 能接受的大小,内存溢出
        nbytes = size * sizeof(PyObject *);
        //获取所需内存大小
        if (numfree) {
            numfree--;
            op = free_list[numfree];
            _Py_NewReference((PyObject *)op);
        //如果缓冲区有内存,先拿缓冲区的内存
        } else {
            op = PyObject_GC_New(PyListObject, &PyList_Type);
            if (op == NULL)
                return NULL;
        //不然就申请新的内存
        }
        如果申请一个空的列表,下一项就为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);
        }
        # 设置ob_size
        Py_SIZE(op) = size;
        op->allocated = size;
        _PyObject_GC_TRACK(op);
        return (PyObject *) op;
    }
    

    创建的过程:

    1. 检查size参数是否有效,如果小于0,直接返回NULL,创建失败
    2. 检查size参数是否超出Python所能接受的大小,如果大于PY_SIZE_MAX(64位机器为8字节,在32位机器为4字节),内存溢出。
    3. 检查缓冲池free_list是否有可用的对象,有则直接从缓冲池中使用,没有则创建新的PyListObject,分配内存。
    4. 初始化ob_item中的元素的值为Null
    5. 设置PyListObject的allocated和ob_size。

    list_dealloc函数,用来销毁列表返回内存给缓冲池:

    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);//释放ob_item的内存
        }
        if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
            free_list[numfree++] = op;
            //如果当前缓冲区还有位置,将op直接放到缓冲区,免得重复申请新内存来new 一个List (为什么能直接归还,因为每个listobject不同的地方在于ob-item ,其他属性可以在从缓冲区拿出来的时候赋值变化,避免了多次malloc)
            //(此时PyListObject占用的内存并不会正真正回收给系统,下次创建PyListObject优先从缓冲池中获取PyListObject)
        else
            Py_TYPE(op)->tp_free((PyObject *)op);//没有就直接归还整个结构体的内存
        Py_TRASHCAN_SAFE_END(op)
    }
    }
    

    当PyListObject对象被销毁的时候,首先将列表中所有元素的引用计数减一,然后释放ob_item占用的内存,只要缓冲池空间还没满,那么就把该PyListObject加入到缓冲池中(此时PyListObject占用的内存并不会正真正回收给系统,下次创建PyListObject优先从缓冲池中获取PyListObject),否则释放PyListObject对象的内存空间。

    查看列表的某个下标元素值的时候:

    PyObject *
    PyList_GetItem(PyObject *op, Py_ssize_t i)
    {
        if (!PyList_Check(op)) {
            PyErr_BadInternalCall();
            return NULL;
        }
        if (i < 0 || i >= Py_SIZE(op)) {
            if (indexerr == NULL) {
                indexerr = PyString_FromString(
                    "list index out of range");
                if (indexerr == NULL)
                    return NULL;
            }
            PyErr_SetObject(PyExc_IndexError, indexerr);
            return NULL;
        }
        return ((PyListObject *)op) -> ob_item[i];
    }
    

    直接检查是否越界,没越界直接返回ob_item[i]所在元素,跟普通数组类似

    list 位置调整,这段代码解释了Python 动态调整的原理

    static int
    list_resize(PyListObject *self, Py_ssize_t newsize)
    {
        PyObject **items;
        size_t new_allocated;
        Py_ssize_t allocated = self->allocated;
    
     //当 newsize  位于当前大小的一半以上时候,将list大小变为newsize
        if (allocated >= newsize && newsize >= (allocated >> 1)) {
            assert(self->ob_item != NULL || newsize == 0);
            Py_SIZE(self) = newsize;
            return 0;
        }
    
    
    //需要增大列表的时候,这与列表大小成比例地分配,
    //创造空间进一步增长。 过度分配是温和的.
    //新增的长度 趋势是  0,4,8,16,25,35,46
        new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
        /* check for integer overflow */
        if (new_allocated > PY_SIZE_MAX - newsize) {
            PyErr_NoMemory();
            return -1;
        } else {
            new_allocated += newsize;
        }
    
        if (newsize == 0)
            new_allocated = 0;
        items = self->ob_item;
        if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
            PyMem_RESIZE(items, PyObject *, new_allocated);
    //给列表新增空间
        else
            items = NULL;
        if (items == NULL) {
            PyErr_NoMemory();
            return -1;
        }
        self->ob_item = items;
        Py_SIZE(self) = newsize;
        self->allocated = new_allocated;
        return 0;
    }
    

    list_resize() 函数。它会多申请一些内存,避免频繁调用 list_resize() 函数。列表的增长模式为:0,4,8,16,25,35,46,58,72,88

    插入:

    static int
    app1(PyListObject *self, PyObject *v)
    {
        Py_ssize_t n = PyList_GET_SIZE(self);//获取list 大小
    
        assert (v != NULL);
        if (n == PY_SSIZE_T_MAX) {
            PyErr_SetString(PyExc_OverflowError,
                "cannot add more objects to list");
            return -1;
        }//如果超过List 长度,则报错
    
        if (list_resize(self, n+1) == -1)
            return -1;
    //调整list大小,增添一个空间的(实际上是得到4个新增空间)
    // new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
    //new_allocated+=newsize
        Py_INCREF(v);
        PyList_SET_ITEM(self, n, v);
        return 0;
    //增加引用,加一
    }
    

    append 方法 实现

    int
    PyList_Append(PyObject *op, PyObject *newitem)
    {
    //引用app1 然后将元素添加到最后一位
        if (PyList_Check(op) && (newitem != NULL))
            return app1((PyListObject *)op, newitem);
        PyErr_BadInternalCall();
        return -1;
    }
    

    现在分配了 4 个用来装列表元素的槽空间,并且第一个空间中为整数 1。如下图显示 l[0] 指向我们新添加的整数对象。虚线的方框表示已经分配但没有使用的槽空间。

    列表追加元素操作的平均复杂度为 O(1)。

    image.png

    继续添加新的元素:l.append(2)。调用 list_resize 函数,参数为 n+1 = 2, 但是因为已经申请了 4 个槽空间,所以不需要再申请内存空间。再添加两个整数的情况也是一样的:l.append(3),l.append(4)。下图显示了我们现在的情况:

    image.png

    插入算法:

    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;
        }
    //如果加上长度都小于0 ,证明越界了 只能变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_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
    {
        if (!PyList_Check(op)) {
            PyErr_BadInternalCall();
            return -1;
        }
        return ins1((PyListObject *)op, where, newitem);
    }
    

    插入是 ,,先确定插入位置,再新建列表保存之前的元素,新加插入元素到新的列表:

    1. resize n+1
    2. 确定插入点
    3. 插入点后所有元素后移
    4. 执行插入
    remove 函数
    static PyObject *
    listremove(PyListObject *self, PyObject *v)
    {
        Py_ssize_t i;
    
        for (i = 0; i < Py_SIZE(self); i++) {
            int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
            if (cmp > 0) {
                if (list_ass_slice(self, i, i+1,
                                   (PyObject *)NULL) == 0)
                    Py_RETURN_NONE;
                return NULL;
            }
            else if (cmp < 0)
                return NULL;
        }
        PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
        return NULL;
    }
    
    

    为了做列表的切片并且删除元素,调用了 list_ass_slice() 函数,

    1. 找到要删除元素位置
    2. 删除之, 后面元素前移
    Py_INCREF(pyObject *o) 增加该变量的引用
    

    相关文章

      网友评论

          本文标题:python 源码阅读(一)listObject

          本文链接:https://www.haomeiwen.com/subject/lhuuxxtx.html