为什么复制打乱的列表要慢得多？
Why is copying a shuffled list much slower?
复制打乱的 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)
我也试过用[=15=复制]，结果也差不多（就是速度差别很大）
为什么速度差别这么大？我知道并理解著名的 Why is it faster to process a sorted array than an unsorted array? 示例中的速度差异，但在这里我的处理没有决定。就是盲目复制列表里面的引用，不是吗？
我在 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))
有趣的一点是它取决于首先创建整数的顺序。例如，用 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 确实需要去哪里对象是。它不能只复制引用。
因此，当您复制列表时，您会获得该列表的每个项目并将其放入新列表中 "as is"。当你的下一个项目在当前项目之后不久被创建时，很有可能（不保证！）它被保存在堆上的旁边。
让我们假设每当您的计算机加载缓存中的项目时，它也会加载 x next-in-memory 项（缓存位置）。然后您的计算机可以对同一缓存中的 x+1 项执行引用计数增量！
经过打乱顺序后，它仍会加载 next-in-memory 个项目，但这些不是 next-in-list 个项目。因此，如果不 "really" 查找下一项，它就无法执行 reference-count 增量。
TL;DR: 实际速度取决于复制之前发生的情况：这些项目的创建顺序以及列表中的顺序。
您可以通过查看 id:
来验证这一点
CPython implementation detail: This is the address of the object in memory.
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
所以这些对象真的是 "next to each other on the heap"。 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
重要提示：
我自己还没有想到这一点。大多数信息都可以在 blogpost of Ricky Stewart.
中找到
此答案基于 "official" CPython 实现 Python。其他实现（Jython、PyPy、IronPython、...）中的细节可能不同。谢谢@JörgWMittag .
当您打乱列表项时，它们的引用位置更差，导致缓存性能更差。
您可能认为复制列表只是复制引用，而不是对象，因此它们在堆上的位置无关紧要。但是，复制仍然涉及访问每个对象以修改引用计数。
正如其他人所解释的那样，它不仅复制了引用，还增加了对象内部的引用计数，因此对象 被 访问，缓存发挥作用。
在这里我只想添加更多的实验。洗牌与未洗牌的关系不大（访问一个元素可能会错过缓存，但将以下元素放入缓存以便它们被命中）。但是关于重复元素，以后对同一元素的访问可能会命中缓存，因为该元素仍在缓存中。
测试正常范围：
>>> 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
输出（第一列是不同元素的个数，每个我测试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 秒，并保持在大约 2.2 秒，直到十万个。我认为这使用了我的 L2 缓存（4 × 256 KB，我有一个 i7-6700）。
然后经过几步，时间增加到 3.5 秒。我认为这混合使用了我的 L2 缓存和 L3 缓存 (8 MB)，直到那也是 "exhausted"。
最后它保持在 3.5 秒左右，我猜是因为我的缓存不再帮助处理重复的元素。
shuffle之前，在堆中分配时，相邻的索引对象在内存中相邻，访问时内存命中率高； shuffle 后，新列表的相邻索引的对象不在内存中。相邻，命中率很差
复制打乱的 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)
我也试过用[=15=复制]，结果也差不多（就是速度差别很大）
为什么速度差别这么大？我知道并理解著名的 Why is it faster to process a sorted array than an unsorted array? 示例中的速度差异，但在这里我的处理没有决定。就是盲目复制列表里面的引用，不是吗？
我在 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))
有趣的一点是它取决于首先创建整数的顺序。例如，用 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_INCREFinlist_slice)，所以 Python 确实需要去哪里对象是。它不能只复制引用。
因此，当您复制列表时，您会获得该列表的每个项目并将其放入新列表中 "as is"。当你的下一个项目在当前项目之后不久被创建时，很有可能（不保证！）它被保存在堆上的旁边。
让我们假设每当您的计算机加载缓存中的项目时，它也会加载 x next-in-memory 项（缓存位置）。然后您的计算机可以对同一缓存中的 x+1 项执行引用计数增量！
经过打乱顺序后，它仍会加载 next-in-memory 个项目，但这些不是 next-in-list 个项目。因此，如果不 "really" 查找下一项，它就无法执行 reference-count 增量。
TL;DR: 实际速度取决于复制之前发生的情况：这些项目的创建顺序以及列表中的顺序。
您可以通过查看 id:
CPython implementation detail: This is the address of the object in memory.
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
所以这些对象真的是 "next to each other on the heap"。 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
重要提示：
我自己还没有想到这一点。大多数信息都可以在 blogpost of Ricky Stewart.
中找到此答案基于 "official" CPython 实现 Python。其他实现（Jython、PyPy、IronPython、...）中的细节可能不同。谢谢@JörgWMittag
当您打乱列表项时，它们的引用位置更差，导致缓存性能更差。
您可能认为复制列表只是复制引用，而不是对象，因此它们在堆上的位置无关紧要。但是，复制仍然涉及访问每个对象以修改引用计数。
正如其他人所解释的那样，它不仅复制了引用，还增加了对象内部的引用计数，因此对象 被 访问，缓存发挥作用。
在这里我只想添加更多的实验。洗牌与未洗牌的关系不大（访问一个元素可能会错过缓存，但将以下元素放入缓存以便它们被命中）。但是关于重复元素，以后对同一元素的访问可能会命中缓存，因为该元素仍在缓存中。
测试正常范围：
>>> 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
输出（第一列是不同元素的个数，每个我测试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 秒，并保持在大约 2.2 秒，直到十万个。我认为这使用了我的 L2 缓存（4 × 256 KB，我有一个 i7-6700）。
然后经过几步，时间增加到 3.5 秒。我认为这混合使用了我的 L2 缓存和 L3 缓存 (8 MB)，直到那也是 "exhausted"。
最后它保持在 3.5 秒左右，我猜是因为我的缓存不再帮助处理重复的元素。
shuffle之前，在堆中分配时，相邻的索引对象在内存中相邻，访问时内存命中率高； shuffle 后，新列表的相邻索引的对象不在内存中。相邻，命中率很差