Python 如何如此快速地从列表中删除元素？
How does Python remove elements from a list so quickly?
我正在学习 Python，我正在尝试了解容器在实践中的工作原理。
有一个问题我无法解释。
假设，我创建了非常大的列表：
>>> l = [i for i in range(100000000)] # ~3 sec
创建它需要大约 3 秒（我使用升序数字而不是相同的值以避免可能的优化）
如我们所见here，删除操作成本O(n)。但是当我从列表中间删除一个元素时，它会立即 returns（就像任何其他简单命令一样快，比如元素访问）
>>> del l[50000000] # instantly (< 0.1 sec)
之后我可以在删除后不到 3 秒内访问元素 l[25000000] 和 l[75000000]，并且它也会立即执行（因此，我无法通过延迟或后台删除来解释这一点).
有人可以向我解释一下，内部是如何完成的吗？该列表实际上是作为某种树实现的吗？这听起来很奇怪，而且，它会违反 constant time element access.
的要求
它是常见的优化，例如 C++ 中的 return 值优化，还是一些罕见的，仅针对我的 platform/version？
我使用 Linux 和 Python 3.4.1（Python 2.7.9 显示相同的结果）。
我不确定您为什么认为删除单个元素需要 3 秒。
您的初始时间是 100000000 次单独的追加操作。每一个都只需要几分之一秒；您的删除操作需要类似的时间。
无论如何，正如 Bartosz 指出的那样，O(n) 复杂度并不意味着所有操作都需要相同的时间长度，它意味着时间长度与列表的长度成正比。
我决定将我的一组评论变成正确的答案。
首先，让我们弄清楚当您这样做时发生了什么：
>>> l = [i for i in range(100000000)]
这里发生了三件事：
- 100000000
int 个对象正在创建中。在 CPython 中创建对象需要分配内存并将内容放入该内存，这需要时间。
- 您正在 运行循环。这会显着影响性能：
[i for i in range(...)] 比 list(range(...)). 慢得多
- 正在动态创建大列表。
看了你的问题，你好像只考虑了最后一点，忽略了其他的。因此，您的计时不准确：创建一个大列表不需要 3 秒，只需要这 3 秒的一小部分。
这个分数有多大是一个有趣的问题，仅使用 Python 代码很难回答这个问题，但我们仍然可以尝试。具体来说，我会尝试使用以下语句：
>>> [None] * 100000000
这里CPython不用创建大量对象（只有None），不用运行循环，可以为列表分配内存一次（因为它提前知道大小）。
时间是不言自明的：
$ python3 -m timeit "list(range(100000000))"
10 loops, best of 3: 2.26 sec per loop
$ python3 -m timeit "[None] * 100000000"
10 loops, best of 3: 375 msec per loop
现在，回到您的问题：项目删除怎么样？
$ python3 -m timeit --setup "l = [None] * 100000000" "del l[0]"
10 loops, best of 3: 89 msec per loop
$ python3 -m timeit --setup "l = [None] * 100000000" "del l[100000000 // 4]"
10 loops, best of 3: 66.5 msec per loop
$ python3 -m timeit --setup "l = [None] * 100000000" "del l[100000000 // 2]"
10 loops, best of 3: 45.3 msec per loop
这些数字告诉我们一些重要的事情。注意 2 × 45.3 ≈ 89。还有 66.5 × 4 / 3 ≈ 89。
这些数字准确地说明了什么是线性复杂度。如果一个函数的时间复杂度为kn（也就是O(n)），这意味着如果我们将输入加倍，我们的时间就会加倍；如果我们将输入大小增加 4/3，则时间增加 4/3。
这就是这里发生的事情。在 CPython 中，我们的 100000000 项列表是一个连续的内存区域，其中包含指向 Python 个对象的指针：
l = |ptr0|ptr1|ptr2|...|ptr99999999|
当我们 运行 del l[0] 时，我们从右向左移动 ptr1，覆盖 ptr0。其他元素也一样：
l = |ptr0|ptr1|ptr2|...|ptr99999999|
^^^^
` item to delete
l = |ptr1|ptr2|...|ptr99999999|
因此，当我们运行del l[0]时，我们要向左移动99999998个指针。这与del l[100000000 // 2]不同，它只需要移动一半的指针（前半部分的指针不需要移动）。 "Moving half the pointers" 等于 "performing half of the operations"，大致意思是 "running in half the time"（这并不总是正确的，但时间表明在这种情况下是正确的）。
我正在学习 Python，我正在尝试了解容器在实践中的工作原理。 有一个问题我无法解释。 假设，我创建了非常大的列表：
>>> l = [i for i in range(100000000)] # ~3 sec
创建它需要大约 3 秒（我使用升序数字而不是相同的值以避免可能的优化）
如我们所见here，删除操作成本O(n)。但是当我从列表中间删除一个元素时，它会立即 returns（就像任何其他简单命令一样快，比如元素访问）
>>> del l[50000000] # instantly (< 0.1 sec)
之后我可以在删除后不到 3 秒内访问元素 l[25000000] 和 l[75000000]，并且它也会立即执行（因此，我无法通过延迟或后台删除来解释这一点).
有人可以向我解释一下，内部是如何完成的吗？该列表实际上是作为某种树实现的吗？这听起来很奇怪，而且，它会违反 constant time element access.
的要求它是常见的优化，例如 C++ 中的 return 值优化，还是一些罕见的，仅针对我的 platform/version？
我使用 Linux 和 Python 3.4.1（Python 2.7.9 显示相同的结果）。
我不确定您为什么认为删除单个元素需要 3 秒。
您的初始时间是 100000000 次单独的追加操作。每一个都只需要几分之一秒；您的删除操作需要类似的时间。
无论如何，正如 Bartosz 指出的那样，O(n) 复杂度并不意味着所有操作都需要相同的时间长度，它意味着时间长度与列表的长度成正比。
我决定将我的一组评论变成正确的答案。
首先，让我们弄清楚当您这样做时发生了什么：
>>> l = [i for i in range(100000000)]
这里发生了三件事：
- 100000000
int个对象正在创建中。在 CPython 中创建对象需要分配内存并将内容放入该内存，这需要时间。 - 您正在 运行循环。这会显着影响性能：
[i for i in range(...)]比list(range(...)). 慢得多
- 正在动态创建大列表。
看了你的问题，你好像只考虑了最后一点，忽略了其他的。因此，您的计时不准确：创建一个大列表不需要 3 秒，只需要这 3 秒的一小部分。
这个分数有多大是一个有趣的问题，仅使用 Python 代码很难回答这个问题，但我们仍然可以尝试。具体来说，我会尝试使用以下语句：
>>> [None] * 100000000
这里CPython不用创建大量对象（只有None），不用运行循环，可以为列表分配内存一次（因为它提前知道大小）。
时间是不言自明的：
$ python3 -m timeit "list(range(100000000))"
10 loops, best of 3: 2.26 sec per loop
$ python3 -m timeit "[None] * 100000000"
10 loops, best of 3: 375 msec per loop
现在，回到您的问题：项目删除怎么样？
$ python3 -m timeit --setup "l = [None] * 100000000" "del l[0]"
10 loops, best of 3: 89 msec per loop
$ python3 -m timeit --setup "l = [None] * 100000000" "del l[100000000 // 4]"
10 loops, best of 3: 66.5 msec per loop
$ python3 -m timeit --setup "l = [None] * 100000000" "del l[100000000 // 2]"
10 loops, best of 3: 45.3 msec per loop
这些数字告诉我们一些重要的事情。注意 2 × 45.3 ≈ 89。还有 66.5 × 4 / 3 ≈ 89。
这些数字准确地说明了什么是线性复杂度。如果一个函数的时间复杂度为kn（也就是O(n)），这意味着如果我们将输入加倍，我们的时间就会加倍；如果我们将输入大小增加 4/3，则时间增加 4/3。
这就是这里发生的事情。在 CPython 中，我们的 100000000 项列表是一个连续的内存区域，其中包含指向 Python 个对象的指针：
l = |ptr0|ptr1|ptr2|...|ptr99999999|
当我们 运行 del l[0] 时，我们从右向左移动 ptr1，覆盖 ptr0。其他元素也一样：
l = |ptr0|ptr1|ptr2|...|ptr99999999|
^^^^
` item to delete
l = |ptr1|ptr2|...|ptr99999999|
因此，当我们运行del l[0]时，我们要向左移动99999998个指针。这与del l[100000000 // 2]不同，它只需要移动一半的指针（前半部分的指针不需要移动）。 "Moving half the pointers" 等于 "performing half of the operations"，大致意思是 "running in half the time"（这并不总是正确的，但时间表明在这种情况下是正确的）。