时间戳

首页 > 解决方案 > 为什么改组列表（范围（n））比改组[0] * n慢？

python - 为什么改组列表（范围（n））比改组[0] * n慢？

问题描述

使用random.shuffle，我注意到 shufflelist(range(n))比 shuffle 多花费大约 25% 的时间[0] * n。以下是大小n从 100 万到 200 万的时间：

random.shuffle(mylist)

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

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

numpy.random.shuffle(mylist)

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

list.reverse(mylist)

以防洗牌顺序很重要，我也在list.reverse洗牌后尝试过。同样，正如预期的那样，这两个列表花费了同样长的时间，并且在没有事先改组的情况下也同样长：

list.reverse(mylist) 洗牌后

那么有什么区别呢？洗牌和倒车都只需要重新排列列表内的指针，为什么对象对洗牌很重要，但对倒车没有关系？

我的基准代码生成时间：

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)])

标签： pythonperformanceshuffle

解决方案

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

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

在尝试解释之前的一些数据点：

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

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

list.reverse在 C 中实现并且仅适用于list（使用列表的实现细节）

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

重要的一点是参考计数

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

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

推荐阅读