为什么 random.shuffle 比使用排序函数慢得多？

Question

当使用 pythons 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))

Answer 1

在 CPython 上（参考解释器）random.shuffle 在 Python 中实现（并根据 _randbelow 实现，它本身是一个 Python 包装器围绕 getrandbits，最终实现它的 C 级函数，并且最终被调用的频率几乎是严格必要的两倍，以确保输出无偏差）； sorted（和 random.random）在 C 中实现。在 Python 中执行工作的开销高于在 C 中执行类似工作的开销。

为什么 random.shuffle 比使用排序函数慢得多？

Why is random.shuffle so much slower than using sorted function?

python

performance

random

shuffle