Python的列表是如何实现的？
Gre*_*reg 158 python arrays linked-list list python-internals
它是一个链表,一个数组？我四处搜寻,只发现有人在猜测.我的C知识不足以查看源代码.
Fre*_*Foo 211
实际上,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常见问题解答.
- @ Kr0e:如果后续元素实际上是同一个对象,则不是:)但是如果你需要更小/缓存更友好的数据结构,则首选`array`模块或NumPy. (9认同)
- 因此,当迭代python列表时,它与链表一样慢,因为每个条目只是一个指针,因此每个元素最有可能导致缓存未命中. (6认同)
- @Kr0e 我不会说迭代列表与链接列表一样慢，但是迭代链接列表的 __values__ 与链接列表一样慢，并且需要注意 Fred 提到的问题。例如，迭代一个列表以将其复制到另一个列表应该比链接列表更快。 (6认同)
小智 46
这是一个动态阵列.实际证明:无论索引如何,索引都需要(当然,差异极小(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使用链表,我会感到震惊 - 它们会破坏许多广泛使用的库的性能,这些库建立在列表是动态数组的假设之上.
- @delnan:-1你的"实际证明"是一个废话,6个赞成.大约98%的时间用于执行`x = [无]*1000`,使得任何可能的列表访问差异的测量值相当不精确.你需要分离出初始化:`-s"x = [None]*100""x [0]"` (75认同)
- 表明它不是链表的天真实现.没有明确表明它是一个数组. (22认同)
- @Ralf：我知道我的 CPU（大多数其他硬件也是如此）很旧而且很慢 - 从好的方面来说，我可以假设对我来说运行得足够快的代码对所有用户来说都足够快：D (3认同)
- 你可以在这里阅读:http://docs.python.org/2/faq/design.html#how-are-lists-implemented (3认同)
- 结构远远不仅仅是链表和数组,时序在决定它们之间没有实际用途. (3认同)
- @John：啊啊，不错，不错……修复并编辑了它（现在也使用 len-1 (999) 作为第一个索引）。 (2认同)
Nul*_*ion 29
这取决于实现,但IIRC:
- CPython使用指针数组
- Jython使用了
ArrayList - IronPython显然也使用了一个数组.您可以浏览源代码以查找.
因此,他们都有O(1)随机访问.
- @sppe2k:由于Python并没有真正的标准或正式规范(尽管有一些文档说"......保证......"),你不能100%肯定,因为"这个由一些纸张保证".但是因为列表索引的'O(1)`是一个非常常见且有效的假设,所以没有任何实现可以打破它. (6认同)
- 依赖于实现的Python解释器将列表实现为链接列表将是Python语言的有效实现吗？换句话说：不能保证 O(1) 随机访问列表？这是否使得在不依赖实现细节的情况下编写高效的代码变得不可能？ (3认同)
- @sepp我相信Python中的列表只是有序集合; 没有明确说明所述实现的实现和/或性能要求 (2认同)
小智 21
我建议Laurent Luce的文章"Python列表实现".对我来说真的很有用,因为作者解释了如何在CPython中实现列表并为此目的使用优秀的图表.
列出对象C结构
CPython中的列表对象由以下C结构表示.ob_item是列表元素的指针列表.assigned是内存中分配的槽数.
typedef struct {
PyObject_VAR_HEAD
PyObject**ob_item;
Py_ssize_t已分配;
PyListObject;
注意分配的插槽与列表大小之间的区别非常重要.列表的大小与len(l)相同.已分配的插槽数是已在内存中分配的数量.通常,您会看到分配的大小可能大于大小.这是为了避免每次将新元素附加到列表时都需要调用realloc.
...
附加
我们在列表中附加一个整数:l.append(1).怎么了？
我们继续添加一个元素:l.append(2).使用n + 1 = 2调用list_resize,但由于分配的大小为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).
正如其他人在上面所述,列表(当明显很大时)是通过分配固定数量的空间来实现的,如果该空间应该填充,则分配更大的空间并复制元素.
要理解为什么方法是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)完成