为什么改组 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 慢三倍（！）：

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

以防万一打乱顺序很重要，我也在打乱列表后尝试了 list.reverse。同样，正如预期的那样，两个列表花费的时间相同，并且与没有事先改组的时间相同：

那有什么区别呢？ shuffle 和 reversing 都只需要重新排列 list 内部的指针，为什么对象对 shuffle 重要而对 reversing 不重要？

我的基准代码产生时间：

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__ 或更改引用计数的情况下发生。列表的内部项目直接后置运行ged

重要的一点是 引用计数

在cpython、the reference count is stored with the object itself中，几乎所有的对象都存储在堆中。为了调整引用计数（即使是暂时的），写入 ob_refcnt 会将 PyObject 结构中的页面分页到 cache/memory/etc.

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

Answer 2

区别在于 list.reverse 作为 list 函数可以访问底层指针数组。所以它确实可以在不以任何方式查看对象的情况下重新排列指针(source):

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

难怪它很快，因为它对缓存非常友好。

但是现在让我们在 shuffled 列表上使用我们的 Python 反转（就像在 list.reverse 的问题中一样，它没有什么不同):

大不同，现在 my_reverse 从各处随机加载对象，这与缓存友好相反。

当然，shuffle 函数也会发生这种情况。虽然 list(range(n)) 最初是缓存友好的，但改组会选择随机索引 j 进行交换，这对缓存非常不友好。虽然 i 只是按顺序移动，但它会遇到很多已经随机交换的对象，所以这也是缓存不友好的。

为什么改组 list(range(n)) 比改组 [0]*n 慢？

Why is shuffling list(range(n)) slower than shuffling [0]*n?

python

performance

shuffle