为什么复制打乱的列表要慢得多？

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))

- Stefan Pochmann

---

为什么对数组进行排序可以加快 Python 循环速度？在 Python 中，循环一个列表或数组的元素是一种常见的操作。但是，如果你需要在循环中查找某些值，并且你知道这些值已经按顺序排列，那么对数组进行排序可能会增加循环速度。这是因为 Python 列表和数组的实现方式不同。Python 列表是一个包含指向对象的指针的数组，而这些对象可以是任何类型。这意味着在遍历一个 Python 列表时，每次访问都需要执行额外的操作来寻找该对象的类型以及它所占用的内存位置。相比之下，NumPy 和 array.array 都是专门为数值计算而设计的数组类型，它们只包含一个数据类型的元素。由于这种数组的元素类型是固定的，因此循环速度更快，因为 Python 不必在每次迭代时检查每个元素的类型。但是，当你需要在 NumPy 或 array.array 中查找特定的值时，这种优势就不存在了。如果你已经知道要查找的值的范围，并且你已经按照这个范围对数组进行了排序，那么你可以使用二分查找算法（binary search），这样就可以快速定位要查找的值。因此，当你需要对一个已排序的数组执行重复查找时，对数组进行排序可能会加速循环。 - vaultah

请不要对我喊叫，我试图帮助你！改变顺序后，每个测试迭代中我获得了大约0.25的结果。因此，在我的平台上，顺序确实很重要。 - barak manos

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Stefan Pochmann

有一个完整的答案链接由@vaultah提供（我看到你现在略微不同意）。但无论如何，我仍然认为我们不应该使用Python进行低级功能，并因此感到担忧。但是那个话题还是很有趣的，谢谢。 - Nikolay Prokopyev

@NikolayProkopyev 是的，我不担心这个问题，只是在做其他事情时注意到了它，无法解释，并且变得好奇。我很高兴自己问了出来并得到了答案 :-) - Stefan Pochmann

Answer 1

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

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_INCREF in list_slice)，因此Python确实需要去到对象所在的位置。它不能只是复制引用。

所以当你复制列表时，你获得该列表的每个项目，并将其“原样”放入新列表中。当你的下一个项目在当前项目之后不久创建时，有很大的机会（没有保证！）它保存在堆上的旁边。

假设每当计算机加载缓存中的一个项目时，它也会加载内存中的下一个项目（缓存局部性）。然后，您的计算机可以对相同缓存上的x+1个项目执行引用计数增量！在混乱的顺序中，它仍然加载下一个内存中的项目，但这些不是下一个列表中的项目。因此，它不能执行引用计数增量，而不“真正”查找下一个项目。

简而言之：实际速度取决于复制之前发生了什么：这些项目是按什么顺序创建的，以及这些项目在列表中的顺序如何。

---

您可以通过查看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 指出这一点。

- MSeifert

---

@augurar 复制一个引用意味着增加对象中的引用计数器（因此不可避免地访问对象）。 - Leon

我只是在想为什么我在64位计算机上使用Python 64位时得到了32位整数。但实际上这对于缓存也很好 :-) 即使[0,1,2,3]*((10**6) // 4)与a = [0] * 10**6一样快。然而，对于0-255的整数，还有另一个事实：它们被内部化了，因此它们的创建顺序（在脚本内部）不再重要 - 因为它们在启动Python时就已经被创建了。 - MSeifert

请注意，目前存在的四个可用于生产的Python实现中，只有一个使用引用计数。因此，这个分析只适用于单一实现。 - Jörg W Mittag

很好的答案，如果可以的话，请再加上一个“重要提示”，强调这种行为是特定于 CPython 的。 - Dimitris Fasarakis Hilliard

也许值得注意的是，deepcopy 会产生同样的结果。我试图通过 a = deepcopy(a) 来改变 a = list(a)，但问题仍然存在，因为 deepcopy 似乎忽略了数值类型（保留原始内存位置）。做一些像 a = map(lambda x: (x - 1) + 1, a) 这样的操作可以使时间差异消失（因为它有效地重新生成了对象并放置在新的位置）。 - MariusSiuram

Answer 2

当你打乱列表项时，它们的引用局部性会变差，导致缓存性能变差。

你可能会认为复制列表只会复制引用，而不是对象，因此它们在堆上的位置并不重要。 然而，复制仍然需要访问每个对象以修改refcount。

- augurar

---

这可能是更好的答案针对我（至少如果它有像MSeifert一样的“证据”链接），因为这就是我所缺少的，而且非常简洁明了，但我认为我会坚持MSeifert的答案，因为我觉得它可能对其他人来说更好。不过，我也投了赞成票，谢谢。 - Stefan Pochmann

还要补充的是，奔腾、酷睿等处理器内部有神秘的逻辑可以检测地址模式，并在检测到模式时开始预取数据。在这种情况下，当数字按顺序排列时，它们可能会启动数据预取（减少缓存未命中）。当然，这种效果还加之于由局部性所增加的命中率百分比。 - greggo

Answer 3

正如其他人所解释的那样，这不仅涉及复制引用，还增加了对象内部的引用计数，因此对象被访问并且缓存起到了作用。

在这里，我只想添加更多实验。并不是关于洗牌与未洗牌（其中访问一个元素可能会错过缓存，但获取后续元素进入缓存，因此它们会被命中）。而是关于重复元素，后续访问同一元素可能会命中缓存，因为该元素仍在缓存中。

测试正常范围：

>>> from timeit import timeit
>>> a = range(10**7)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[5.1915339142808925, 5.1436351868889645, 5.18055115701749]

如果一个列表的大小相同，但只有一个元素反复重复出现，则速度更快，因为它会一直命中缓存：

>>> a = [0] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.125743135926939, 4.128927210087596, 4.0941229388550795]

而似乎无论是什么数字都没有关系：

>>> a = [1234567] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.124106479141709, 4.156590225249886, 4.219242600790949]

有趣的是，当我重复相同的两个或四个元素时，速度甚至更快：

>>> a = [0, 1] * (10**7 / 2)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.130586101607932, 3.1001001764957294, 3.1318465707127814]

>>> a = [0, 1, 2, 3] * (10**7 / 4)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.096105435911994, 3.127148431279352, 3.132872673690855]

我猜有些东西不喜欢同一个单一计数器一直增加。也许会出现一些 pipeline stall，因为每次增加都必须等待前一次增加的结果，但这只是一个猜测。

无论如何，即使针对更大量的重复元素尝试此方法：

from timeit import timeit
for e in range(26):
    n = 2**e
    a = range(n) * (2**25 / n)
    times = [timeit(lambda: list(a), number=20) for _ in range(3)]
    print '%8d ' % n, '  '.join('%.3f' % t for t in times), ' => ', sum(times) / 3

输出结果（第一列是不同元素的数量，每个元素测试三次然后求平均值）：

       1  2.871  2.828  2.835  =>  2.84446732686
       2  2.144  2.097  2.157  =>  2.13275338734
       4  2.129  2.297  2.247  =>  2.22436720645
       8  2.151  2.174  2.170  =>  2.16477771575
      16  2.164  2.159  2.167  =>  2.16328197911
      32  2.102  2.117  2.154  =>  2.12437970598
      64  2.145  2.133  2.126  =>  2.13462250728
     128  2.135  2.122  2.137  =>  2.13145065221
     256  2.136  2.124  2.140  =>  2.13336283943
     512  2.140  2.188  2.179  =>  2.1688431668
    1024  2.162  2.158  2.167  =>  2.16208440826
    2048  2.207  2.176  2.213  =>  2.19829998424
    4096  2.180  2.196  2.202  =>  2.19291917834
    8192  2.173  2.215  2.188  =>  2.19207065277
   16384  2.258  2.232  2.249  =>  2.24609975704
   32768  2.262  2.251  2.274  =>  2.26239771771
   65536  2.298  2.264  2.246  =>  2.26917420394
  131072  2.285  2.266  2.313  =>  2.28767871168
  262144  2.351  2.333  2.366  =>  2.35030805124
  524288  2.932  2.816  2.834  =>  2.86047313113
 1048576  3.312  3.343  3.326  =>  3.32721167007
 2097152  3.461  3.451  3.547  =>  3.48622758473
 4194304  3.479  3.503  3.547  =>  3.50964316455
 8388608  3.733  3.496  3.532  =>  3.58716466865
16777216  3.583  3.522  3.569  =>  3.55790996695
33554432  3.550  3.556  3.512  =>  3.53952594744

从单个（重复）元素的约2.8秒，到2、4、8、16...不同元素的约2.2秒，并保持在100,000左右。我认为这使用了我的L2缓存（4×256 KB，我有一个i7-6700）。

然后经过几步，时间增加到3.5秒。我认为这使用了我的L2缓存和L3缓存（8 MB），直到它也被“耗尽”。

最后，它保持在约3.5秒左右，我猜这是因为我的缓存不再对重复元素有帮助。

- Stefan Pochmann

Answer 4

在洗牌之前，当在堆中分配时，相邻索引对象在内存中是相邻的，并且访问时内存命中率很高；在洗牌之后，新列表的相邻索引对象不再相邻，命中率非常低。

- xws