python 中的堆栈/列表 - 它是如何追加的？
Stacks / list in python - how does it append?
如果我有一个列表：
list_1 = ["apples", "apricots", "oranges"]
然后我将一个新项目添加到列表中："berries"
list_1 = ["apples", "apricots", "oranges", "berries"]
在幕后（可以这么说），我想我记得读过 Python 创建另一个列表 (list_2) 并将其指向原始列表 (list_1 ) 以便 list_1 保持静态...如果这是真的，它看起来像这样吗（引擎盖下）？
list_1 = ["apples", "apricots", ["oranges", "berries"]]
这样一来，原来的列表就保持了原来的大小。这是正确的看待方式吗？
不，在幕后，列表由一个（通常）未充分利用的数组支持。
list1 -> [ x | x | ]
| |
| v
| "apricots"
v
"apples"
当您附加到 list1 时，您只需更改第一个未使用的数组槽的值：
list1 -> [ x | x | x ]
| | |
| | v
| | "oranges"
| v
| "apricots"
v
"apples"
在 next 追加时，在添加新元素之前向数组添加更多内存（并且再次超过所需内存）。 [一旦检测到数组已满，就可以分配额外的内存；我不记得具体细节了。]
list1 -> [ x | x | x | | | | ]
| | |
| | v
| | "oranges"
| v
| "apricots"
v
"apples"
list1 -> [ x | x | x | x | | | ]
| | | |
| | | v
| | | "berries"
| | v
| | "oranges"
| v
| "apricots"
v
"apples"
实际分配的数量可能会有所不同，但期望的效果是 appends 的任何 序列 具有 constant-time 操作的外观，即使每个单独的 append 可能是非常小的 constant-time 操作或 linear-time 操作。但是，不变的是你永远不能在对象的生命周期内进行 "too many" linear-time 操作，保留每个对象的 amortized 运行 时间append.
在幕后，Python 列表对象使用更大的 C array 结构；它是 pre-sized。 Python列表的长度只是一个整数值，记录了数组中存储了多少Python个元素。向列表追加一个元素只是使用数组中的下一个空位，并且大小整数递增一个。
当 C 数组中的 space 不再足够时，会分配更多内存来增大数组。如果将元素删除到仅使用数组一半的位置，则会再次释放内存。
您可以在 Objects/listobject.c file in the Python source code. Resizing takes place in the list_resize() function 中看到实现，其中以下代码片段决定新数组的大小，以在内存使用之间取得平衡（数组中的一堆指针未被使用） ) 并避免过于频繁地跨数组复制：
/* 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 添加 到当前分配。因此，当您需要更多 space 时，新大小除以 8，再加上 3 或 6，就决定了要在最小所需大小 之上添加多少额外元素 .将元素附加到大小为 1000 的列表会增加 131 个额外插槽的缓冲区，而将元素附加到大小为 10 的列表只会增加额外的 7 个插槽。
从 Python 代码的角度来看，该列表只是一系列索引，它们会根据需要增长和收缩以适应所有元素。这里没有涉及额外的列表，调整大小时数组的交换从视图中隐藏。
一个 Python 实现可以在幕后做任何事情，只要它有正确的行为。好的实现也至少与 the recommended time complexities.
一样快
一般来说，附加到列表会修改列表（如果可能）。在它的 append implementation, the widely used cpython resizes the list if necessary to 9/8 * old_size + 6 如果没有更多 space。调整大小是通过保留更多内存（如果幸运的话）或分配新内存并复制所有旧元素来完成的。这意味着很少需要调整大小，尤其是当列表很大时。大多数时候，可以使用其中一个备用内存space。
不，当您调用 append 时，Python 不会 创建另一个列表。它改变了现有列表 in-place。您可以很容易地看到这一点：
>>> lst1 = []
>>> lst2 = lst1
>>> lst1.append(0)
>>> lst1
[0]
>>> lst2
[0]
如果您想创建另一个列表，您可以这样做：
>>> lst1 = []
>>> lst2 = lst1
>>> lst1 = lst1 + [0]
>>> lst1
[0]
>>> lst2
[]
那么，in-place 附加是如何工作的？列表不只是引擎盖下的数组吗？对，他们是。 Python 在末尾留下一点 space，但是如果你 append 足够多次，它必须为列表分配一个新数组，移动所有元素，并删除旧的.它仍然是同一个列表对象，但在引擎盖下有一个不同的数组。
增长不只是每次添加一个新槽——这意味着每个 append 都必须重新分配整个列表，因此追加将花费平均线性时间。相反，它会乘以长度。像这样：
new_capacity = max(4, capacity * 8 // 5, new_length)
（可以使用 new_length 以防您一次 extend 列出包含一大堆元素的列表。）
通过几何扩展而不是算术扩展，我们可以保证，虽然少数 appends 确实需要线性时间，但其中足够多的时间是即时的，摊销时间是恒定的。您使用的确切因素是速度（高数字意味着更少的重新分配）和 space（更高的数字意味着最终浪费更多 space）之间的权衡。我不知道 CPython 的作用，但您可以在下面链接的源代码中找到它。大多数系统使用 1.5 和 2.0 之间的值（通常是一小部分小数，因此它们可以进行整数倍和除法）。
如果你真的想了解这一点，并且你可以遵循基本的 C，你可以在 listobject.h and listobject.c 上查看底层。您可能想先阅读 C API 文档，但这是基础知识（在 Python-like 伪代码中，并有意使用不完全真实的函数和字段名称）：
if lst.size + 1 > lst.allocated:
new_capacity = <see above>
lst.array = PyRealloc(<enough memory for new_capacity pointers>)
lst.allocated = new_capacity
incref(new_item)
lst.array[lst.size] = new_item
lst.size += 1
Realloc 函数将成为平台函数的薄包装，它将尝试找到更多空间 in-place，但回退到分配一个全新的指针并遍历所有的内容。
由于您正在使用 Python，您很可能是那种喜欢通过交互式实验来学习的人。如果您不知道 ctypes.pythonapi. you should definitely start playing with it. You can call almost anything from the C API from inside Python. Unfortunately, you can't call #define macros, or dig into the structs without a bit of extra work—but see superhackyinternals 如何做这些额外的工作。 （我不认为我在那里包含了列表的任何内容，但是看看整数是如何工作的，你应该能够从那里得到它——只是不要看字符串，因为它们要复杂得多。）当然，在你的解释器内部玩弄这些东西，你会经常出现段错误，所以不要在你有任何重要历史的会话中这样做。
当然，不能保证每个 Python 实施都是如此。只要实现可以提供文档化的接口和性能特征，它就可以根据需要构建列表。例如，IronPython 可能使用 .NET class 库中的一些矢量 class。当然 class 会在它自己的引擎盖下做类似的 reallocate-and-move，但是 IronPython 不会关心它是如何做到的（你会更不关心）。
如果我有一个列表：
list_1 = ["apples", "apricots", "oranges"]
然后我将一个新项目添加到列表中："berries"
list_1 = ["apples", "apricots", "oranges", "berries"]
在幕后（可以这么说），我想我记得读过 Python 创建另一个列表 (list_2) 并将其指向原始列表 (list_1 ) 以便 list_1 保持静态...如果这是真的，它看起来像这样吗（引擎盖下）？
list_1 = ["apples", "apricots", ["oranges", "berries"]]
这样一来，原来的列表就保持了原来的大小。这是正确的看待方式吗？
不，在幕后，列表由一个（通常）未充分利用的数组支持。
list1 -> [ x | x | ]
| |
| v
| "apricots"
v
"apples"
当您附加到 list1 时，您只需更改第一个未使用的数组槽的值：
list1 -> [ x | x | x ]
| | |
| | v
| | "oranges"
| v
| "apricots"
v
"apples"
在 next 追加时，在添加新元素之前向数组添加更多内存（并且再次超过所需内存）。 [一旦检测到数组已满，就可以分配额外的内存；我不记得具体细节了。]
list1 -> [ x | x | x | | | | ]
| | |
| | v
| | "oranges"
| v
| "apricots"
v
"apples"
list1 -> [ x | x | x | x | | | ]
| | | |
| | | v
| | | "berries"
| | v
| | "oranges"
| v
| "apricots"
v
"apples"
实际分配的数量可能会有所不同，但期望的效果是 appends 的任何 序列 具有 constant-time 操作的外观，即使每个单独的 append 可能是非常小的 constant-time 操作或 linear-time 操作。但是，不变的是你永远不能在对象的生命周期内进行 "too many" linear-time 操作，保留每个对象的 amortized 运行 时间append.
在幕后，Python 列表对象使用更大的 C array 结构；它是 pre-sized。 Python列表的长度只是一个整数值，记录了数组中存储了多少Python个元素。向列表追加一个元素只是使用数组中的下一个空位，并且大小整数递增一个。
当 C 数组中的 space 不再足够时，会分配更多内存来增大数组。如果将元素删除到仅使用数组一半的位置，则会再次释放内存。
您可以在 Objects/listobject.c file in the Python source code. Resizing takes place in the list_resize() function 中看到实现，其中以下代码片段决定新数组的大小，以在内存使用之间取得平衡（数组中的一堆指针未被使用） ) 并避免过于频繁地跨数组复制：
/* 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 添加 到当前分配。因此，当您需要更多 space 时，新大小除以 8，再加上 3 或 6，就决定了要在最小所需大小 之上添加多少额外元素 .将元素附加到大小为 1000 的列表会增加 131 个额外插槽的缓冲区，而将元素附加到大小为 10 的列表只会增加额外的 7 个插槽。
从 Python 代码的角度来看，该列表只是一系列索引，它们会根据需要增长和收缩以适应所有元素。这里没有涉及额外的列表，调整大小时数组的交换从视图中隐藏。
一个 Python 实现可以在幕后做任何事情，只要它有正确的行为。好的实现也至少与 the recommended time complexities.
一样快一般来说，附加到列表会修改列表（如果可能）。在它的 append implementation, the widely used cpython resizes the list if necessary to 9/8 * old_size + 6 如果没有更多 space。调整大小是通过保留更多内存（如果幸运的话）或分配新内存并复制所有旧元素来完成的。这意味着很少需要调整大小，尤其是当列表很大时。大多数时候，可以使用其中一个备用内存space。
不，当您调用 append 时，Python 不会 创建另一个列表。它改变了现有列表 in-place。您可以很容易地看到这一点：
>>> lst1 = []
>>> lst2 = lst1
>>> lst1.append(0)
>>> lst1
[0]
>>> lst2
[0]
如果您想创建另一个列表，您可以这样做：
>>> lst1 = []
>>> lst2 = lst1
>>> lst1 = lst1 + [0]
>>> lst1
[0]
>>> lst2
[]
那么，in-place 附加是如何工作的？列表不只是引擎盖下的数组吗？对，他们是。 Python 在末尾留下一点 space，但是如果你 append 足够多次，它必须为列表分配一个新数组，移动所有元素，并删除旧的.它仍然是同一个列表对象，但在引擎盖下有一个不同的数组。
增长不只是每次添加一个新槽——这意味着每个 append 都必须重新分配整个列表，因此追加将花费平均线性时间。相反，它会乘以长度。像这样：
new_capacity = max(4, capacity * 8 // 5, new_length)
（可以使用 new_length 以防您一次 extend 列出包含一大堆元素的列表。）
通过几何扩展而不是算术扩展，我们可以保证，虽然少数 appends 确实需要线性时间，但其中足够多的时间是即时的，摊销时间是恒定的。您使用的确切因素是速度（高数字意味着更少的重新分配）和 space（更高的数字意味着最终浪费更多 space）之间的权衡。我不知道 CPython 的作用，但您可以在下面链接的源代码中找到它。大多数系统使用 1.5 和 2.0 之间的值（通常是一小部分小数，因此它们可以进行整数倍和除法）。
如果你真的想了解这一点，并且你可以遵循基本的 C，你可以在 listobject.h and listobject.c 上查看底层。您可能想先阅读 C API 文档，但这是基础知识（在 Python-like 伪代码中，并有意使用不完全真实的函数和字段名称）：
if lst.size + 1 > lst.allocated:
new_capacity = <see above>
lst.array = PyRealloc(<enough memory for new_capacity pointers>)
lst.allocated = new_capacity
incref(new_item)
lst.array[lst.size] = new_item
lst.size += 1
Realloc 函数将成为平台函数的薄包装，它将尝试找到更多空间 in-place，但回退到分配一个全新的指针并遍历所有的内容。
由于您正在使用 Python，您很可能是那种喜欢通过交互式实验来学习的人。如果您不知道 ctypes.pythonapi. you should definitely start playing with it. You can call almost anything from the C API from inside Python. Unfortunately, you can't call #define macros, or dig into the structs without a bit of extra work—but see superhackyinternals 如何做这些额外的工作。 （我不认为我在那里包含了列表的任何内容，但是看看整数是如何工作的，你应该能够从那里得到它——只是不要看字符串，因为它们要复杂得多。）当然，在你的解释器内部玩弄这些东西，你会经常出现段错误，所以不要在你有任何重要历史的会话中这样做。
当然，不能保证每个 Python 实施都是如此。只要实现可以提供文档化的接口和性能特征，它就可以根据需要构建列表。例如，IronPython 可能使用 .NET class 库中的一些矢量 class。当然 class 会在它自己的引擎盖下做类似的 reallocate-and-move，但是 IronPython 不会关心它是如何做到的（你会更不关心）。