我现在正在学习 Python，并试图了解容器在实践中的工作原理。 有一个问题我无法解释。 假设，我创建了一个非常大的列表:
>>> l = [i for i in range(100000000)] # ~3 sec
创建它需要大约 3 秒(我使用升序数字而不是相同的值以避免可能的优化)
我们可以读到here ，删除操作成本O(n)。但是当我从列表中间删除一个元素时，它会立即返回(就像任何其他简单命令一样快，比如元素访问)
>>> del l[50000000] # instantly (< 0.1 sec)
在此之后我可以在删除后不到 3 秒内访问元素 l[25000000] 和 l[75000000]，并且它也立即执行(所以，我无法通过延迟或后台删除来解释这一点)。
有人可以向我解释一下，它是如何在内部完成的吗？该列表实际上是作为某种树实现的吗？这听起来很奇怪，而且它会违反 constant time element access 的要求。 .
它是一种常见的优化，例如 C++ 中的返回值优化，还是一些罕见的、仅特定于我的平台/版本的东西？
我使用 Linux 和 Python 3.4.1(Python 2.7.9 显示相同的结果)。
请您参考如下方法:
我决定将我的一组评论变成正确的答案。
首先，让我们弄清楚当您这样做时发生了什么:
>>> 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]不同，它只需要移动一半的指针(前半部分的指针不需要移动)。 “移动一半的指针”等于“执行一半的操作”，大致意思是“用一半的时间运行”(这并不总是正确的，但时间表明在这种情况下是正确的)。
