首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >python 元组的实现和探析

python 元组的实现和探析

原创
作者头像
Yerik
修改2021-05-10 10:44:42
1.1K0
修改2021-05-10 10:44:42
举报
文章被收录于专栏:烹饪一朵云烹饪一朵云

其实就表面感官来说,元组和列表的样子大同小异,面试中经常会遇到的,tuplelist 有什么区别?这种问题几乎都问烂了,大部分人可以回答的七七八八了,什么tuple不能变,list可以进行增删改;tuple创建是通过()list是通过[],短短两句话道尽其功能与生成,然而道不尽其本质与性能,其丰富的内涵还需要细细展开与推演。

源码解析对比

首先来分析list 列表,它的具体结构如下所示:

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;
    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

有兴趣的读者,可直接阅读 list 列表实现的源码文件listobject.hlistobject.c

在最近的一篇文章中我们分析到list 本质上是一个长度可变的连续数组,其中ob_item是一个指针列表,里边的每一个指针都指向列表中的元素,而allocated则用于存储该列表目前已被分配的空间大小。需要注意的是allocated 和列表的实际空间大小不同,列表实际空间大小,指的是len(list)返回的结果,也就是上边代码中注释中的 ob_size,表示该列表总共存储了多少个元素,而在实际情况中,为了优化存储结构,避免每次增加元素都要重新分配内存,列表预分配的空间allocated 往往会大于ob_size

因此allocatedob_size 的关系是:allocated >= len(list) = ob_size >= 0

如果当前列表分配的空间已满(即allocated == len(list)),则会向系统请求更大的内存空间,并把原来的元素全部拷贝过去。

接下来再分析元组,如下所示为 Python 3.7 tuple 元组的具体结构:

typedef struct {
    PyObject_VAR_HEAD
    PyObject *ob_item[1];
    /* ob_item contains space for 'ob_size' elements.
     * Items must normally not be NULL, except during construction when
     * the tuple is not yet visible outside the function that builds it.
     */
} PyTupleObject;

有兴趣的读者,可阅读tuple元组实现的源码文件 tupleobject.htupleobject.c

他的memory layout 如下所示

memory.png
memory.png

我们可以看到,PyTupleObject 只存储了两个对象,分别是:

  • PyObject_VAR_HEAD: cpython中容器对象的头部
  • ob_item: 一个长度为 1 的存储内容为 PyObject * 的数组

tuple 和 list 相似,本质也是一个数组,但是空间大小固定。不同于一般数组,Python 的 tuple 做了许多优化,来提升在程序中的效率。

举个例子,为了提高效率,避免频繁的调用系统函数freemalloc向操作系统申请和释放空间,tuple 在文件Objects/tupleobject.c 中第 28 行定义了一个free_list

static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];

所有申请过的,小于一定大小的元组,在释放的时候会被放进这个free_list中以供下次使用。也就是说,如果以后需要再去创建同样的tuple,Python 就可以直接从缓存中载入。

free_list.png
free_list.png
  • free_list[0] 用于存储长度为 0 的tuple 对象,整个解释器的生命周期里面只有一个长度为 0 的tuple 对象实例
  • free_list[1] 用于存储长度为 1 的tuple 对象,可以通过tuple 对象的ob_item[0] 指针遍历到下一个长度为 1 的tuple 对象
  • free_list[2] 用于存储长度为 2 的tuple 对象,上图画的free_list[2] 中只有一个对象
  • free_list 每一格最多能存储PyTuple_MAXFREELISTtuple 链表长度,这里定义的是 2000

我们来看下PyTuple_New 函数

/* Objects/tupleobject.c 79 - 136 行 */
 
PyObject *
PyTuple_New(Py_ssize_t size)
{
    PyTupleObject *op;
    Py_ssize_t i;
    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
/* 如果启动了 free_list 存储 */
#if PyTuple_MAXSAVESIZE > 0
    if (size == 0 && free_list[0]) {
        /* 如果 size 为 0, 则返回 free_list 的第一个元素 */
        op = free_list[0];
        Py_INCREF(op);
#ifdef COUNT_ALLOCS
        _Py_tuple_zero_allocs++;
#endif
        return (PyObject *) op;
    }
    if (size < PyTuple_MAXSAVESIZE && (op = free_list[size]) != NULL) {
        /* 如果 size 在 free_list 范围内,并且 free_list[size] 存有之前回收过的对应size的tuple 对象 
        把 free_list[size] 指向 op 的下一个链表地址
        */
        free_list[size] = (PyTupleObject *) op->ob_item[0];
        numfree[size]--;
#ifdef COUNT_ALLOCS
        _Py_fast_tuple_allocs++;
#endif
        /* Inline PyObject_InitVar */
#ifdef Py_TRACE_REFS
        Py_SIZE(op) = size;
        Py_TYPE(op) = &PyTuple_Type;
#endif
        _Py_NewReference((PyObject *)op);
    }
    else
#endif
    {
        /* free_list 未找到对应大小的 tuple 并且 size 不为 0,向操作系统分配 */
        /* Check for overflow */
        if ((size_t)size > ((size_t)PY_SSIZE_T_MAX - sizeof(PyTupleObject) -
                    sizeof(PyObject *)) / sizeof(PyObject *)) {
            return PyErr_NoMemory();
        }
        op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
        if (op == NULL)
            return NULL;
    }
    /* 把 tuple 里面的元素设置为空指针 */
    for (i=0; i < size; i++)
        op->ob_item[i] = NULL;
#if PyTuple_MAXSAVESIZE > 0
    if (size == 0) {
        free_list[0] = op;
        ++numfree[0];
        Py_INCREF(op);          /* extra INCREF so that this is never freed */
    }
#endif
#ifdef SHOW_TRACK_COUNT
    count_tracked++;
#endif
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

从函数名也大概可以猜出功能了

元组真的不能修改吗?

嘿嘿,这倒不一定,比如说进行以下操作

>>> t = ([1,2,3,4],[5,4,5,6,4])
>>> t
([1, 2, 3, 4], [5, 4, 5, 6, 4])
>>> t[1].append("hello yerik")
>>> t
([1, 2, 3, 4], [5, 4, 5, 6, 4, 'hello yerik'])
>>> t[1].pop()
'hello yerik'
>>> t[1].pop(2)
5
>>> t
([1, 2, 3, 4], [5, 4, 6, 4])

这个tuple定义的时候有2个元素,都是两个list。不是说tuple一旦定义后就不可变了吗?怎么后来又变了?

别急别急,案例中的t包含两个元素,都是list

tuple元素.png
tuple元素.png

当我们我们对tuple中的元素进行修改的时候,表面上tuple中的元素确实变化了,然而这并不影响tuple中的元素指针指向list,我们修改list中的元素也并没有变成别的list。tuple中的不变,指的是元素指针指向的元素地址起始位置不变,而元素地址对应的数据结构是可变还是不可变的数据类型都是没有关系的。通过这个我们其实可以根据list和tuple来进行组合了,比如说我们在list中嵌入tuple做成一串只能添加不能修改的核心不变数据集;通过在tuple中嵌入list构建成可变元素的定长数据集。

参考文章

  1. http://c.biancheng.net/view/5360.html
  2. https://blog.csdn.net/qq_31720329/article/details/885297922. https://blog.csdn.net/qq_31720329/article/details/88529792

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 源码解析对比
  • 元组真的不能修改吗?
  • 参考文章
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档