python的List是如何实现的?

它是链表还是数组?我四处搜寻，只发现人们在猜测。我的C语言知识还不够好，不能看源代码。

134832 次浏览
小开

这取决于实现，但IIRC:

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

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

小开

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

小开
最佳答案

它是动态数组。实践证明:无论索引如何，索引都需要相同的时间(当然差异非常小(0.0013µs !)):

...>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使用链表，我会感到震惊——它们会破坏许多广泛使用的库的性能，这些库建立在链表是动态数组的假设之上。

小开

实际上，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，而不是逐个__abc3)。

另见Python常见问题解答。

小开

根据文档，

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 = O(2^n) = O(a)总插入次数(即O(1)平摊时间)。另外，应该注意的是，如果表允许删除，那么表收缩必须在不同的因子上进行(例如3x)

小开

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

列表对象C结构

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

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

注意已分配插槽和列表大小之间的区别是很重要的。列表的大小与len(l)相同。已分配插槽的数量是内存中已分配的数量。通常，您会看到allocate可以大于size。这是为了避免每次添加新元素时都需要调用realloc。

.．.

附加

我们将一个整数追加到列表:l.append(1)。会发生什么呢?< br > enter image description here < / p >

我们继续添加一个元素:l.append(2)。list_resize在n+1 = 2时被调用，但因为分配的大小是4，所以不需要分配更多的内存。当我们再加上两个整数:l.append(3)， l.append(4)时，也会发生同样的事情。下面的图表显示了我们目前所拥有的。

enter image description here

.．.

插入

让我们在位置1:l.insert(1,5)插入一个新的整数(5)，看看内部发生了什么。enter image description here

.．.

流行

当你弹出最后一个元素:l.pop()时，listpop()将被调用。list_resize在listpop()内部被调用，如果新大小小于已分配大小的一半，则列表被收缩

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

你可以观察到slot 3和4仍然指向一些整数，但重要的是列表的大小现在是3. __abc0

.．.

<强>删除 __abc . __abc1

小开

Python中的列表类似于数组，可以存储多个值。列表是可变的，这意味着你可以改变它。你应该知道的更重要的事情是，当我们创建一个列表时，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中，list是作为动态数组实现的，因此当我们追加时，不仅添加了一个宏，而且分配了更多的空间，这样每次都不应该添加新的空间。


提交答案