python 中的堆栈/列表 - 它如何追加？

Question

如果我有一个清单：

list_1 = ["apples", "apricots", "oranges"]

我将一个新项目添加到列表中：“浆果”

list_1 = ["apples", "apricots", "oranges", "berries"]

在幕后（可以这么说），我想我记得读过Python创建了另一个列表（list_2）并将其指向原始列表（list_1），以便list_1保持静态......如果这是真的，它看起来会吗？像这样的东西（在引擎盖下）？

list_1 = ["apples", "apricots", ["oranges", "berries"]]

所以这样一来，原来的列表就保持了原来的大小。这是正确的看待方式吗？

Answer 1

不，当您调用 时，Python 不会创建另一个列表append。它就地改变现有列表。你可以很容易地看到这一点：

\n\n

>>> lst1 = []\n>>> lst2 = lst1\n>>> lst1.append(0)\n>>> lst1\n[0]\n>>> lst2\n[0]\n

\n\n

如果您想创建另一个列表，可以这样做：

\n\n

>>> lst1 = []\n>>> lst2 = lst1\n>>> lst1 = lst1 + [0]\n>>> lst1\n[0]\n>>> lst2\n[]\n

\n\n\n\n

那么，就地附加是如何工作的呢？列表不就是底层的数组吗？是的，他们是。Python 在末尾留了一点空间，但如果append次数足够多，它必须为列表分配一个新数组，移动所有元素，并删除旧元素。它仍然是相同的列表对象，但底层有不同的数组。

\n\n

这种增长并不只是每次添加一个新槽位\xe2\x80\x94，这意味着每个槽位都append必须重新分配整个列表，因此追加将花费平均线性时间。相反，它会增加长度。像这样的东西：

\n\n

new_capacity = max(4, capacity * 8 // 5, new_length)\n

\n\n

（new_length如果您extend同时使用一大堆元素来处理列表，则存在该选项。）

\n\n

通过几何扩展而不是算术扩展，我们可以保证，虽然几个appends 确实需要线性时间，但其中足够的时间是即时的，因此摊余时间是恒定的。确切地说，您使用的因素是速度（高数字意味着更少的重新分配）和空间（更高的数字意味着最后浪费的空间更多）之间的权衡。我不知道 CPython 是做什么的，但你可以在下面链接的源代码中找到它。大多数系统使用 1.5 到 2.0 之间的值（通常是小数的一个很好的分数，以便它们可以进行整数倍和除法）。

\n\n\n\n

如果你真的想理解这一点，并且你可以遵循基本的 C，你可以深入了解listobject.h和listobject.c。您可能想先阅读 C API 文档，但这里是基础知识（使用类似 Python 的伪代码，并且有意使用不完全真实的函数和字段名称）：

\n\n

if lst.size + 1 > lst.allocated:\n    new_capacity = <see above>\n    lst.array = PyRealloc(<enough memory for new_capacity pointers>)\n    lst.allocated = new_capacity\nincref(new_item)\nlst.array[lst.size] = new_item\nlst.size += 1\n

\n\n

该Realloc函数将成为平台函数的薄包装，它将尝试就地找到更多空间，但会回退到分配一个全新的指针并移动所有内容。

\n\n\n\n

既然您使用的是 Python，那么您很可能是那种喜欢通过交互式实验来学习的人。如果您不了解ctypes.pythonapi. 你绝对应该开始玩它。您可以从Python 内部调用C API中的几乎任何内容。不幸的是，您无法调用#define宏，也无法在没有一些额外工作的情况下深入研究结构\xe2\x80\x94，但请了解superhackyinternals如何完成这些额外工作。（我认为我没有在列表中包含任何内容，但是看看整数是如何工作的，你应该能够从那里得到它\xe2\x80\x94，只是不要看字符串，因为它们是复杂得多。）当然，在解释器内部使用这些东西，你会出现很多段错误，所以不要在你有任何重要历史记录的会话中这样做。

\n\n\n\n

当然，并不能保证每个 Python 实现都是如此。只要实现可以提供记录的接口和性能特征，它就可以根据需要构建列表。例如，IronPython 可能使用 .NET 类库中的某些向量类。当然，该类会在自己的引擎盖下执行类似的重新分配和移动操作，但 IronPython 不会关心它是如何做到这一点的（您甚至会更不关心）。

\n

Answer 2

在底层，Python 列表对象使用更大的C数组结构；它是预先确定尺寸的。Python列表的长度只是一个整数值，记录了数组中存储了多少个Python元素。将元素追加到列表中只是使用数组中的下一个空位，并且大小整数递增 1。

当 C 数组中不再有足够的空间时，会分配更多内存来扩展数组。如果删除元素到仅使用数组的一半，则会再次释放内存。

你可以在Python源代码的Objects/listobject.c文件中看到实现。调整大小发生在list_resize()函数中，其中以下代码片段决定新数组应该有多大，以在内存使用（数组中的一堆指针未使用）和避免过于频繁地跨数组复制之间取得平衡：

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

new_allocated被添加到当前分配中。因此，当您需要更多空间时，新大小除以 8，再加上 3 或 6，将决定在所需的最小大小之上添加多少额外元素。将一个元素附加到大小为 1000 的列表会添加 131 个额外槽位的缓冲区，而将一个元素附加到大小为 10 的列表只会添加额外的 7 个槽位。

从 Python 代码的角度来看，列表只是一个索引序列，它会根据需要增长和缩小以适应所有元素。这里不涉及额外的列表，调整大小时数组的交换从视图中隐藏。