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

Question

使用random.shuffle函数，我发现对于需要打乱的列表list(range(n))，打乱所需的时间比打乱[0] * n的时间多大约25%。以下是在n大小从100万到200万时的时间统计： 为什么打乱list(range(n))会更慢？和排序一个列表（需要查看对象）或复制一个列表（增加了对象内部的引用计数）不同，这里不应该考虑对象。这应该只是重新排列列表内部的指针。

我还尝试了使用numpy.random.shuffle函数，其中打乱list(range(n))比打乱[0] * n慢3倍（！）: 我还尝试了第三种重新排列列表元素的方法，即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)])

- Kelly Bundy

---

也许洗牌是通过交换条目来实现的，代码检查值是否不同，如果相同则不进行交换？您尝试查看random.shuffle的源代码了吗？ - DisappointedByUnaccountableMod

@barny 它不会这样做。但你确实可以在那里找到大约40%的解释。 - Kelly Bundy

好奇在 PyPy3 上的图表长什么样子... - Todd

Answer 1

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

---

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

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

random.shuffle 是用纯Python实现的，并适用于任何可变序列类型--它没有专门为列表进行优化。

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

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

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

重要的是引用计数

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

（这就是我没有时间的地方 - 我可能会进行一些内存故障分析来确认这个假设）

- anthony sottile

---

我现在添加了自己的答案，但我仍然对你提到的内存故障分析很感兴趣，如果你能提供它，我将非常乐意接受你的答案。我尝试过了，从Victor Stinner那里学到了perf，但是在我尝试的机器上，它没有提供缓存统计信息 :-( - Kelly Bundy

Answer 2

区别在于list.reverse作为一个list函数，可以访问底层指针数组。因此，它确实可以重新排列指针，而不需要以任何方式查看对象 (来源)：

reverse_slice(PyObject **lo, PyObject **hi)
{
    assert(lo && hi);

    --hi;
    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        ++lo;
        --hi;
    }
}

random.shuffle和numpy.random.shuffle函数只有外部视角并通过列表的接口进行操作，这涉及到短暂地加载对象以进行交换：

random.shuffle:

    def shuffle(self, x, random=None):
        ...
            for i in reversed(range(1, len(x))):
                # pick an element in x[:i+1] with which to exchange x[i]
                j = randbelow(i+1)
                x[i], x[j] = x[j], x[i]

numpy.random.shuffle:

    def shuffle(self, object x, axis=0):
          ...
                for i in reversed(range(1, n)):
                    j = random_interval(&self._bitgen, i)
                    x[i], x[j] = x[j], x[i]

所以至少存在很多缓存未命中的潜在可能性。但是让我们以Python中的reverse为例进行测试：

    def my_reverse(x):
        lo = 0
        hi = len(x) - 1
        while lo < hi:
            x[lo], x[hi] = x[hi], x[lo]
            lo += 1
            hi -= 1

对此进行基准测试：

反转list(range(n))与反转[0]*n一样快，即使加载了对象。原因是Python会按顺序在内存中创建对象。下面是使用一百万个对象进行的测试。几乎所有对象都在前一个对象的16字节之后:

>>> mylist = list(range(10**6))
>>> from collections import Counter
>>> ctr = Counter(id(b) - id(a) for a, b in zip(mylist, mylist[1:]))
>>> for distance, how_often in ctr.most_common():
        print(distance, how_often)

16 996056
48 3933
-1584548240 1
-3024 1
2416 1
-2240 1
2832 1
-304 1
-96 1
-45005904 1
6160432 1
38862896 1

因此，不难理解为什么它很快，因为它非常友好的缓存。

但现在让我们在打乱列表上使用我们的Python翻转（就像在问题中使用list.reverse一样，它没有产生差异）：

有很大的区别，现在my_reverse从随机位置加载对象，这与缓存友好相反。

当然，shuffle函数也是如此。虽然list(range(n))最初是缓存友好的，但洗牌会选择随机索引j进行交换，这非常不缓存友好。而i只是顺序移动，它将遇到许多已经随机交换的对象，所以这也不缓存友好。

- Kelly Bundy