为什么复制经过改组的列表要慢得多？

为什么复制经过改组的列表要慢得多？

有趣的一点是，它取决于 首次 创建整数的顺序。例如，而不是使用

shuffle

创建随机序列

random.randint

：

from timeit import timeitimport randoma = [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

内存中的项目（缓存位置）。然后，您的计算机可以

x+1

对同一缓存中的项目执行引用计数递增！

通过改组序列，它仍会加载内存中的下一个项目，但这些不是列表中的下一个项目。因此，如果没有“真正”寻找下一项，它就无法执行参考计数递增。

TL; DR： 实际速度取决于复制之前发生的情况：这些项目以什么顺序创建以及列表中的顺序是什么。

---

您可以通过查看来验证这一点

id

：

CPython实现细节：这是对象在内存中的地址。

a = list(range(10**6, 10**6+100))for item in a:    print(id(item))

仅显示一个简短的摘录：

14964899958881496489995920  # +321496489995952  # +321496489995984  # +321496489996016  # +321496489996048  # +321496489996080  # +3214964899961121496489996144149648999617614964899962081496489996240149650729784014965072978721496507297904149650729793614965072979681496507298000149650729803214965072980641496507298096149650729812814965072981601496507298192

因此，这些对象实际上“在堆上彼此相邻”。与

shuffle

他们不是：

import randoma = list(range(10**6, 100+10**6))random.shuffle(a)last = Nonefor item in a:    if last is not None:        print('diff', id(item) - id(last))    last = item

这表明这些在内存中并不是真正相邻的：

diff 736diff -64diff -17291008diff -128diff 288diff -224diff 17292032diff -1312diff 1088diff -17292384diff 17291072diff 608diff -17290848diff 17289856diff 928diff -672diff 864diff -17290816diff -128diff -96diff 17291552diff -192diff 96diff -17291904diff 17291680diff -1152diff 896diff -17290528diff 17290816diff -992diff 448

---

重要的提示：

我自己还没有想到这一点。大多数信息可以在Ricky
Stewart
的博客中找到。

该答案基于Python的“官方”
CPython实现。其他实现（Jython，PyPy，IronPython等）的细节可能有所不同。感谢@JörgWMittag指出这一点。