240

是链表还是数组?我四处寻找,只发现人们在猜测。我的 C 知识还不够好,无法查看源代码。

4

9 回答 9

288

实际上,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一个一个地处理它们)。

另请参阅Python 常见问题解答

于 2010-10-18T10:39:40.133 回答
73

这是一个动态数组。实际证明:无论索引如何,索引都需要(当然差异极小(0.0013 µsecs!))相同的时间:

...>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 使用链表,我会感到震惊——它们会破坏许多基于列表是动态数组的假设而广泛使用的库的性能。

于 2010-10-12T18:04:10.837 回答
54

我建议Laurent Luce 的文章“Python 列表实现”。对我来说真的很有用,因为作者解释了列表是如何在 CPython 中实现的,并为此使用了优秀的图表。

列表对象 C 结构

CPython 中的列表对象由以下 C 结构表示。ob_item是指向列表元素的指针列表。已分配是内存中分配的插槽数。

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

重要的是要注意分配的插槽和列表大小之间的差异。列表的大小与 相同len(l)。分配的插槽数是在内存中分配的。通常,您会看到已分配可能大于大小。这是为了避免realloc每次将新元素附加到列表时都需要调用。

...

附加

我们将一个整数附加到列表中:l.append(1). 怎么了?
在此处输入图像描述

我们继续添加一个元素:l.append(2). list_resize使用 n+1 = 2 调用,但由于分配的大小为 4,因此无需分配更多内存。当我们再添加 2 个整数时也会发生同样的情况:l.append(3), l.append(4). 下图显示了我们目前所拥有的。

在此处输入图像描述

...

插入

让我们在位置 1: 处插入一个新整数 (5),l.insert(1,5)然后看看内部发生了什么。在此处输入图像描述

...

流行音乐

当您弹出最后一个元素时:l.pop(),listpop()被调用。list_resize在内部调用listpop(),如果新大小小于分配大小的一半,则列表将缩小。在此处输入图像描述

您可以观察到插槽 4 仍然指向整数,但重要的是列表的大小现在是 4。让我们再弹出一个元素。在list_resize()中,size – 1 = 4 – 1 = 3 小于分配槽的一半,因此列表缩小到 6 个槽,列表的新大小现在为 3。

您可以观察到插槽 3 和 4 仍然指向一些整数,但重要的是列表的大小现在为 3。在此处输入图像描述

...

移除 Python 列表对象有一个移除特定元素的方法:l.remove(5).在此处输入图像描述

于 2017-07-20T10:50:05.363 回答
45

这取决于实现,但 IIRC:

  • CPython 使用指针数组
  • Jython 使用ArrayList
  • IronPython 显然也使用数组。您可以浏览源代码以找出答案。

因此它们都有 O(1) 随机访问。

于 2010-10-12T17:59:29.740 回答
40

在 CPython 中,列表是指针数组。Python 的其他实现可能会选择以不同的方式存储它们。

于 2010-10-12T18:00:23.480 回答
26

According to the documentation,

Python’s lists are really variable-length arrays, not Lisp-style linked lists.

于 2012-06-01T15:07:33.230 回答
5

正如其他人在上面所说的那样,列表(当相当大时)是通过分配固定数量的空间来实现的,如果该空间应该填满,则分配更多的空间并复制元素。

为了理解为什么该方法是 O(1) 摊销,而不失一般性,假设我们已经插入了 a = 2^n 个元素,我们现在必须将我们的表加倍到 2^(n+1) 大小。这意味着我们目前正在进行 2^(n+1) 次操作。最后一个副本,我们做了 2^n 次操作。在此之前,我们做了 2^(n-1)... 一直到 8,4,2,1。现在,如果我们把这些加起来,我们得到 1 + 2 + 4 + 8 + ... + 2^(n+1) = 2^(n+2) - 1 < 4*2^n = O(2^ n) = O(a) 总插入次数(即 O(1) 摊销时间)。此外,应该注意的是,如果表允许删除,则必须以不同的因素(例如 3 倍)进行表收缩

于 2013-10-22T03:00:45.573 回答
2

Python 中的列表类似于数组,您可以在其中存储多个值。List 是可变的,这意味着您可以更改它。您应该知道的更重要的事情是,当我们创建一个列表时,Python 会自动为该列表变量创建一个 reference_id。如果您通过分配其他变量来更改它,则主列表将被更改。让我们尝试一个例子:

list_one = [1,2,3,4]

my_list = list_one

#my_list: [1,2,3,4]

my_list.append("new")

#my_list: [1,2,3,4,'new']
#list_one: [1,2,3,4,'new']

我们追加my_list,但我们的主列表已更改。那意味着的列表没有分配为副本列表分配为其参考。

于 2019-08-20T12:36:15.723 回答
-2

在 CPython 中,列表是作为动态数组实现的,因此当我们追加时,不仅添加了一个宏,而且分配了更多空间,因此每次都不应添加新空间。

于 2020-03-19T14:31:24.407 回答