为什么使用random.shuffle比使用sorted函数慢得多?

Question

为什么使用random.shuffle比使用sorted函数慢得多?

5

当使用Python的random.shuffle函数时，我注意到使用sorted(l, key=lambda _: random.random())比random.shuffle(l)更快。据我所知，两种方法都可以产生完全随机的列表，那么为什么shuffle需要花费更多时间呢？

下面是使用timeit模块计时的结果。

from timeit import timeit
setup = 'import random\nl = list(range(1000))'

# 5.542 seconds
print(timeit('random.shuffle(l)', setup=setup, number=10000))

# 1.878 seconds
print(timeit('sorted(l, key=lambda _: random.random())', setup=setup, number=10000))

- mazore

理想情况下，洗牌函数应该实现Fisher-Yates shuffle，其运行时间复杂度为O(n)，而一般排序的运行时间复杂度为O(n log n)。我怀疑sorted(l, key=lambda _: random.random())不是对数组进行洗牌的正确方法：请参见上述链接。 - Sebastian Simon

2

@user4642212：Python的random.shuffle使用的是Fisher-Yates算法（假设我正确地阅读了维基百科和源代码）。该链接提到，如果排序算法本身随机打破平局（Python不会；它是稳定排序），那么使用sorted与random.random()将是正确的。 - ShadowRanger

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ShadowRanger · Accepted Answer

在CPython（参考解释器）中，random.shuffle 是用 Python 实现的（并且是基于 _randbelow 实现的，它本身是一个 Python 包装器，封装了最终实现它的 C 级函数 getrandbits，为了确保输出是无偏倚的，getrandbits 函数可能会被调用近乎两倍的次数），而 sorted（以及 random.random）则是用 C 实现的。在 Python 中执行工作的开销比在 C 中执行类似的工作要高。