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

Question

使用random.shuffle，我注意到 shufflelist(range(n))比 shuffle 多花费大约 25% 的时间[0] * n。以下是n100 万到 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)])

Answer 1

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

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

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

random.shuffle是用纯 python 实现的，适用于任何可变序列类型——它不是专门用于列表的。

• 这意味着每次交换都涉及__getitem__增加该项目的引用计数，__setitem__减少该项目的引用计数

list.reverse用 C 实现，仅适用于list（使用列表的实现细节）

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

重要的是引用计数

在cpython中，引用计数与对象本身一起存储，几乎所有对象都存储在堆中。为了调整引用计数（即使是暂时的），将结构ob_refcnt中的页面PyObject写入缓存/内存/等。

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