为什么复制经过改组的列表要慢得多？

Question

复制一份随机播放的range(10**6)列表十次需要我大约0.18秒：（这五次运行）

0.175597017661
0.173731403198
0.178601711594
0.180330912952
0.180811964451

复制未整理的列表十次需要我大约0.05秒：

0.058402235973
0.0505464636856
0.0509734306934
0.0526022752744
0.0513324916184

这是我的测试代码：

from timeit import timeit
import random

a = range(10**6)
random.shuffle(a)    # Remove this for the second test.
a = list(a)          # Just an attempt to "normalize" the list.
for _ in range(5):
    print timeit(lambda: list(a), number=10)

我也尝试使用进行复制a[:]，结果相似（即，速度差异很大）

为什么速度相差很大？我知道并理解著名的速度差异，为什么处理排序数组要比未排序数组快？例如，但是在这里我的处理没有决定。只是盲目地复制列表中的引用，不是吗？

我在Windows 10上使用Python 2.7.12。

编辑： 现在也尝试使用Python 3.5.2，结果几乎相同（在0.17秒左右一致改组，在0.05秒左右一致改组）。这是代码：

a = list(range(10**6))
random.shuffle(a)
a = list(a)
for _ in range(5):
    print(timeit(lambda: list(a), number=10))

Answer 1

有趣的一点是，它取决于 首次 创建整数的顺序。例如，而不是使用shuffle创建随机序列random.randint：

from timeit import timeit
import random

a = [random.randint(0, 10**6) for _ in range(10**6)]
for _ in range(5):
    print(timeit(lambda: list(a), number=10))

这和复制您的速度一样快list(range(10**6))（第一个也是最快速的示例）。

但是，当您随机播放时-整数就不再按照它们最初创建的顺序排列了，这就是使它变慢的原因。

一个快速的间奏：

• 所有Python对象都在堆上，因此每个对象都是一个指针。
• 复制列表是一项浅层操作。
• 但是Python使用引用计数，因此当将对象放入新容器中时，它的引用计数必须增加（Py_INCREFinlist_slice），因此Python确实需要转到对象所在的位置。它不能只是复制参考。

因此，当您复制列表时，将获得该列表的每个项目并将其“按原样”放在新列表中。当下一个项目在当前项目之后不久创建时，很有可能（不保证！）将其保存在堆上。

假设每当您的计算机将一个项目加载到缓存中时，它也会同时加载x内存中的项目（缓存位置）。然后，您的计算机可以x+1对同一缓存中的项目执行引用计数递增！

通过改组序列，它仍会加载内存中的下一个项目，但这些不是列表中的下一个项目。因此，如果没有“真正”寻找下一项，它就无法执行参考计数递增。

TL; DR： 实际速度取决于复制之前发生的情况：这些项目以什么顺序创建以及列表中的顺序是什么。

您可以通过查看来验证这一点id：

CPython实现细节：这是对象在内存中的地址。

a = list(range(10**6, 10**6+100))
for item in a:
    print(id(item))

仅显示一个简短的摘录：

1496489995888
1496489995920  # +32
1496489995952  # +32
1496489995984  # +32
1496489996016  # +32
1496489996048  # +32
1496489996080  # +32
1496489996112
1496489996144
1496489996176
1496489996208
1496489996240
1496507297840
1496507297872
1496507297904
1496507297936
1496507297968
1496507298000
1496507298032
1496507298064
1496507298096
1496507298128
1496507298160
1496507298192

因此，这些对象实际上“在堆上彼此相邻”。与shuffle他们不是：

import random
a = list(range(10**6, 100+10**6))
random.shuffle(a)
last = None
for item in a:
    if last is not None:
        print('diff', id(item) - id(last))
    last = item

这表明这些在内存中并不是真正相邻的：

diff 736
diff -64
diff -17291008
diff -128
diff 288
diff -224
diff 17292032
diff -1312
diff 1088
diff -17292384
diff 17291072
diff 608
diff -17290848
diff 17289856
diff 928
diff -672
diff 864
diff -17290816
diff -128
diff -96
diff 17291552
diff -192
diff 96
diff -17291904
diff 17291680
diff -1152
diff 896
diff -17290528
diff 17290816
diff -992
diff 448

重要的提示：

我自己还没有想到这一点。大多数信息可以在Ricky
Stewart
的博客中找到。

该答案基于Python的“官方”
CPython实现。其他实现（Jython，PyPy，IronPython等）的细节可能有所不同。感谢@JörgWMittag指出这一点。