复制一个无序的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[:]
复制,结果是相似的(即速度差异很大)
为什么速度差这么大?我知道并理解著名的Why is it faster to process a sorted array than an unsorted array?示例中的速度差,但这里我的处理没有任何决定。只是在盲目地复制名单里的推荐信,不是吗?
我在Windows10上使用Python2.7.12。
编辑:也尝试了Python3.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))
正如其他人所解释的,这不仅是复制引用,而且还增加了对象内部的引用计数,因此对象被访问,缓存发挥了作用。
在这里我只想增加更多的实验。与其说是shuffled,不如说是unshuffled(访问一个元素可能会错过缓存,但会将以下元素放入缓存,这样它们就会被命中)。但关于重复元素,同一元素的后续访问可能会命中缓存,因为该元素仍在缓存中。
测试正常范围:
相同大小但只有一个元素反复出现的列表速度更快,因为它总是命中缓存:
不管是什么数字:
有趣的是,当我重复同样的两个或四个元素时,它会变得更快:
我想有些东西不喜欢同一个计数器一直增加。可能是一些pipeline stall,因为每次增加都要等待上一次增加的结果,但这是一个疯狂的猜测。
不管怎样,对更多的重复元素尝试这个方法:
输出(第一列是不同元素的数量,对于每个I测试三次,然后取平均值):
所以从单个元素的2.8秒下降到2.2秒,2,4,8,16。。。不同的元素和停留在大约2.2秒,直到数十万。我认为这使用了我的二级缓存(4×256kb,我有一个i7-6700)。
再过几步,时间就增加到3.5秒。我认为这将使用我的二级缓存和三级缓存(8MB)的混合,直到“耗尽”为止。
最后它会停留在3.5秒左右,我想是因为我的缓存不再有助于处理重复的元素。
当您洗牌列表项时,它们的引用区域性变差,导致缓存性能变差。
您可能认为复制列表只是复制引用,而不是对象,因此它们在堆中的位置不重要。但是,复制仍然需要访问每个对象以修改refcount。
有趣的是,它取决于整数的创建顺序。例如,使用
random.randint
而不是shuffle
创建一个随机序列:这与复制
list(range(10**6))
(第一个快速示例)一样快。然而,当你洗牌-然后你的整数不再是他们最初创建的顺序,这就是为什么它慢。
快速的间奏曲:
因此,当你复制你的列表时,你会得到列表中的每一项,并将其“原样”放入新列表中。当你的下一个项目在当前项目之后不久创建时,很有可能(不保证!)它被保存在堆的旁边。
假设当您的计算机在缓存中加载一个项时,它也会加载下一个内存项(缓存位置)。然后,您的计算机可以对同一缓存中的
x+1
项执行引用计数递增!对于无序序列,它仍然加载下一个内存项,但这些不是列表中的下一个。因此,如果不“真正”查找下一项,它就无法执行引用计数增量。
TL;DR:实际速度取决于复制之前发生的事情:这些项是按什么顺序创建的,列表中的项是按什么顺序创建的。
您可以通过查看^{} 来验证这一点:
只是为了展示一个简短的摘录:
所以这些对象实际上是“堆上的相邻对象”。使用
shuffle
它们不是:这表明它们在记忆中并不是真的相邻的:
重要提示:
我自己也没想过。大多数信息可以在blogpost of Ricky Stewart中找到。
这个答案基于Python的“官方”CPython实现。其他实现(Jython、PyPy、IronPython,…)中的细节可能不同。谢谢@JórgWMittagfor pointing this out。
相关问题 更多 >
编程相关推荐