Python的清单是如何实现的?

发布于 2021-02-02 23:17:38

它是一个链表,一个数组吗?我四处搜寻,只发现有人猜测。我的C语言知识不足以查看源代码。

关注者
0
被浏览
83
1 个回答
  • 面试哥
    面试哥 2021-02-02
    为面试而生,有面试问题,就找面试哥。

    这是一个动态数组。实际证明:无论使用什么索引,索引都需要同时花时间(当然,差异很小(0.0013微秒!)

    ...>python -m timeit --setup="x = [None]*1000" "x[500]"
    10000000 loops, best of 3: 0.0579 usec per loop
    
    ...>python -m timeit --setup="x = [None]*1000" "x[0]"
    10000000 loops, best of 3: 0.0566 usec per loop
    

    如果IronPython或Jython使用链接列表,我会感到惊讶-它们会破坏许多基于列表是动态数组的假设而广泛使用的库的性能。



  • 面试哥
    面试哥 2021-02-02
    为面试而生,有面试问题,就找面试哥。

    实际上,C代码非常简单。扩展一个宏并修剪一些不相关的注释,其基本结构在中listobject.h,该结构将列表定义为:

    typedef struct {
        PyObject_HEAD
        Py_ssize_t ob_size;
    
        /* 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
         */
        Py_ssize_t allocated;
    } PyListObject;
    

    PyObject_HEAD包含一个引用计数和一个类型标识符。因此,它是一个整体的向量/数组。用于在此类数组已满时调整其大小的代码在中listobject.c。它实际上并没有将数组加倍,而是通过分配来增长

    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
    new_allocated += newsize;
    

    每次达到最大容量时,newsize请求的大小在哪里(不一定allocated + 1是因为你可以添加extend任意数量的元素,而不是append一个个地添加它们)。



知识点
面圈网VIP题库

面圈网VIP题库全新上线,海量真题题库资源。 90大类考试,超10万份考试真题开放下载啦

去下载看看