Python的清单是如何实现的？

Question

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

Answer 1

这是一个动态数组。实际证明：无论使用什么索引，索引都需要同时花时间(当然，差异很小（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使用链接列表，我会感到惊讶-它们会破坏许多基于列表是动态数组的假设而广泛使用的库的性能。

Answer 2

实际上，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一个个地添加它们）。