为什么复制混洗列表慢得多?

复制混洗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 

这是我的testing代码:

 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[:]复制,结果是相似的(即速度差很大)

为什么速度差很大? 我知道和理解在着名的速度差异为什么处理sorting的数组比未sorting的数组更快? 例如,但在这里我的处理没有任何决定。 这只是盲目地复制列表中的引用,不是?

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

有趣的是,它取决于整数首先被创build的顺序。 例如,而不是shuffle创build一个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))一样快list(range(10**6)) (首先和快速的例子)。

然而,当你洗牌时,那么你的整数不是按照他们第一次创build的顺序,这就是它的缓慢。

一个快速的intermezzo:

  • 所有的Python对象都在堆上,所以每个对象都是一个指针。
  • 复制一个列表是一个简单的操作。
  • 然而,Python使用引用计数,所以当一个对象被放入一个新的容器时,它的引用计数必须增加( Py_INCREF中的list_slice ),所以Python真的需要到达对象所在的位置。 它不能只复制参考。

所以当你复制你的列表时,你会得到这个列表中的每个项目,并按照原样放在新列表中。 当你的下一个项目在当前的项目创build后不久,就有一个很好的机会(不保证!),它被保存在堆的旁边。

假设只要你的计算机在caching中加载一个项目,它也会加载x下一个内存项目(caching局部性)。 然后您的计算机可以在同一个caching上执行x+1项的引用计数增量!

随着洗牌序列,它仍然加载内存中的下一个项目,但这些不是下一个列表中的项目。 因此,如果没有“真正”寻找下一个项目,就不能执行参考计数增量。

TL; DR:实际速度取决于副本之前发生的事情:这些项目以什么顺序创build,以什么顺序排列在列表中。


你可以通过查看id来validation这一点:

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的博客中find。

这个答案基于Python的“官方”CPython实现。 其他实现(Jython,PyPy,IronPython,…)中的细节可能有所不同。 谢谢@JörgWMittag 指出这一点 。

当您将列表项目洗牌时,它们的参考位置会变差,从而导致caching性能下降。

您可能认为复制列表只是复制引用而不是对象,所以它们在堆上的位置应该没有关系。 但是,复制仍涉及到访问每个对象,以修改refcount。

正如其他人所解释的那样,这不仅仅是复制引用,而且还会增加对象内部的引用计数,从而访问对象,caching起到一定的作用。

在这里,我只是想添加更多的实验。 没有那么多关于洗牌vs非洗牌(访问一个元素可能会错过caching,但获得以下元素到caching中,以便它们被击中)。 但是关于重复的元素,后来对相同元素的访问可能会触发caching,因为元素仍然在caching中。

testing一个正常范围:

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

一个相同大小的列表,但只有一个元素一遍又一遍地重复的速度更快,因为它总是碰到caching:

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

我猜想有些事情不像一个单一的计数器一直在增加。 也许有些pipe道因为每次增加都要等待前一次增加的结果而停止 ,但这是一个疯狂的猜测。

无论如何,尝试更多的重复元素:

 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 

输出(第一列是不同元素的数量,对于每个我testing三次,然后取平均值):

  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秒直到成千上万。 我认为这使用我的二级caching(4×256 KB,我有一个i7-6700 )。

然后在几个步骤,时间上升到3.5秒。 我认为这个使用了我的二级caching和我的三级caching(8 MB)的组合,直到“枯竭”为止。

最后,它停留在3.5秒左右,我想是因为我的caching不再帮助重复的元素了。