是链表还是数组?我四处寻找,只发现人们在猜测。我的 C 知识还不够好,无法查看源代码。
9 回答
实际上,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 常见问题解答。
这是一个动态数组。实际证明:无论索引如何,索引都需要(当然差异极小(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 使用链表,我会感到震惊——它们会破坏许多基于列表是动态数组的假设而广泛使用的库的性能。
我建议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)
. 下图显示了我们目前所拥有的。
...
插入
...
流行音乐
当您弹出最后一个元素时:
l.pop()
,listpop()
被调用。list_resize
在内部调用listpop()
,如果新大小小于分配大小的一半,则列表将缩小。您可以观察到插槽 4 仍然指向整数,但重要的是列表的大小现在是 4。让我们再弹出一个元素。在
list_resize()
中,size – 1 = 4 – 1 = 3 小于分配槽的一半,因此列表缩小到 6 个槽,列表的新大小现在为 3。
...
这取决于实现,但 IIRC:
- CPython 使用指针数组
- Jython 使用
ArrayList
- IronPython 显然也使用数组。您可以浏览源代码以找出答案。
因此它们都有 O(1) 随机访问。
在 CPython 中,列表是指针数组。Python 的其他实现可能会选择以不同的方式存储它们。
According to the documentation,
Python’s lists are really variable-length arrays, not Lisp-style linked lists.
正如其他人在上面所说的那样,列表(当相当大时)是通过分配固定数量的空间来实现的,如果该空间应该填满,则分配更多的空间并复制元素。
为了理解为什么该方法是 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 倍)进行表收缩
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
,但我们的主列表已更改。那意味着的列表没有分配为副本列表分配为其参考。
在 CPython 中,列表是作为动态数组实现的,因此当我们追加时,不仅添加了一个宏,而且分配了更多空间,因此每次都不应添加新空间。