Python的列表是如何实现的?

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

这是一个数组。 实践certificate:无论索引如何,索引都需要(当然,差异极小(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使用链表,我会感到震惊的 – 它们会毁掉许多被广泛使用的库的性能,这些库被build立在列表是数组的假设上。

C代码其实很简单。 扩展一个macros并修剪一些不相关的注释,基本结构在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包含引用计数和types标识符。 所以,这是一个向量/数组。 当这个数组已满时resize的代码在listobject.c 。 它实际上并不是将数组加倍,而是通过分配来增长

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

newsize是请求的大小(不一定allocated + 1因为你可以extend任意数量的元素,而不是一个接一个地append )。

另请参阅Python FAQ 。

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

这与实施有关,但是IIRC:

  • CPython使用一个指针数组
  • Jython使用一个ArrayList
  • IronPython显然也使用一个数组。 你可以浏览源代码找出来。

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

根据文件 ,

Python的列表实际上是可变长度的数组,而不是Lisp风格的链表。

正如其他人上面所说的那样,通过分配一定数量的空间来实施清单(当相当大时),并且如果该空间应该填满,则分配更大的空间并复制这些内容。

要理解为什么该方法是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 = n)= O(a)总插入(即O(1)摊销时间)。 另外,应该注意的是,如果表允许删除,则表的缩小必须以不同的因子(例如3x)来完成,

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

列出对象C的结构

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

typedef struct {

PyObject_VAR_HEAD

PyObject ** ob_item;

分配了Py_ssize_t;

} 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),看看内部发生了什么。 在这里输入图像描述

stream行的

当你popup最后一个元素时:l.pop(),listpop()被调用。 在listpop()中调用list_resize,如果新的大小小于分配大小的一半,那么这个列表就会被收缩。 在这里输入图像描述

你可以观察到slot 4仍然指向整数,但是重要的是现在的list 4的大小。让我们再popup一个元素。 在list_resize()中,size-1 = 4-1 = 3小于已分配槽的一半,所以列表缩小到6个槽,新的大小现在是3。

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

删除 Python列表对象有一个方法来删除特定的元素:l.remove(5)。 在这里输入图像描述