为什么复制洗牌列表要慢得多？

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))(第一个和快速的例子)一样快.

然而,当你洗牌时 - 那么你的整数不再是它们最初创建的顺序,这就是它变慢的原因.

一个快速的intermezzo:

• 所有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 指出这一点.

Answer 2

当您对列表项进行随机播放时,它们的引用位置会更差,从而导致缓存性能下降.

您可能认为复制列表只是复制引用而不是对象,因此它们在堆上的位置无关紧要.但是,复制仍然涉及访问每个对象以修改引用计数.

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]

我想有些东西不喜欢同一个单一的计数器一直在增加.也许一些管道失速因为每次增加都要等待前一次增加的结果,但这是一个疯狂的猜测.

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

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秒,并且在大约2.2秒之前保持到大约2.2秒.我认为这使用了我的L2缓存(4×256 KB,我有一个i7-6700).

然后经过几个步骤,时间可达3.5秒.我认为这使用了我的L2缓存和我的L3缓存(8 MB)的混合,直到它"耗尽".

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