为什么洗牌 list(range(n)) 比洗牌 [0]*n 慢？

Using random.shuffle，我注意到洗牌list(range(n))比洗牌多花费约 25% 的时间[0] * n。这是尺寸的时间n从 100 万到 200 万：

为什么是洗牌list(range(n))慢点？与对列表进行排序（需要查看对象）或复制列表（增加对象内部的引用计数器）不同，对象在这里不重要。这应该只是重新排列列表内的指针。

我也尝试过numpy.random.shuffle，其中洗牌list(range(n))比洗牌慢三倍（！）[0] * n:

我还尝试了第三种方法来重新排列列表中的元素，即list.reverse。正如预期的那样，两个列表花费的时间相同：

以防万一洗牌顺序很重要，我也尝试过list.reverse重新整理列表后。同样，正如预期的那样，两个列表花费的时间相同，并且与没有事先进行改组的时间相同：

那么有什么区别呢？混排和反转都只需要重新排列列表内的指针，为什么对象对于混排很重要，而对于反转则不重要？

我的基准代码生成时间：

import random
import numpy
from timeit import repeat, timeit
from collections import defaultdict

shufflers = {
    'random.shuffle(mylist)': random.shuffle,
    'numpy.random.shuffle(mylist)': numpy.random.shuffle,
    'list.reverse(mylist)': list.reverse,
    }

creators = {
    'list(range(n))': lambda n: list(range(n)),
    '[0] * n': lambda n: [0] * n,
    }

for shuffler in shufflers:
    print(shuffler)
    for creator in creators:
        print(creator)
        times = defaultdict(list)
        for _ in range(10):
            for i in range(10, 21):
                n = i * 100_000
                mylist = creators[creator](n)
                # Uncomment next line for pre-shuffling
                # numpy.random.shuffle(mylist)
                time = timeit(lambda: shufflers[shuffler](mylist), number=1)
                times[n].append(time)
                s = '%.6f ' * len(times[n])
        # Indent next line further to see intermediate results
        print([round(min(times[n]), 9) for n in sorted(times)])

（注意：我没有时间完成这个答案，所以这是一个开始——这绝对不适合评论，希望它可以帮助其他人完成这个问题！）

这似乎是由于引用的局部性（也许是 cpython 实现细节——例如，我在 pypy 中没有看到相同的结果）

在尝试解释之前先看几个数据点：

random.shuffle https://github.com/python/cpython/blob/61ac612e78e4f2625977406fb6f366e0a644673a/Lib/random.py#L304-L324是用纯 python 实现的，适用于任何可变序列类型——它不是专门用于列表的。

• 这意味着每次交换都涉及__getitem__，增加商品的重新计数，__setitem__，减少项目的重新计数

list.reverse https://github.com/python/cpython/blob/61ac612e78e4f2625977406fb6f366e0a644673a/Objects/listobject.c#L1023-L1037用 C 实现，仅适用于list（使用列表的实现细节）

• 这意味着每次交换都在不调用的情况下发生__getitem__或更改引用计数。列表的内部项目直接重新排列

重要的是引用计数

在 cpython 中，引用计数与对象本身一起存储 https://github.com/python/cpython/blob/61ac612e78e4f2625977406fb6f366e0a644673a/Include/object.h#L105-L109，并且几乎所有对象都存储在堆中。为了调整引用计数（即使是暂时的）写入ob_refcnt将分页在PyObject结构到缓存/内存/等中。

（这是我没时间的地方——我可能会做一些内存故障分析来证实这个假设）