为什么 random.shuffle 比使用 sorted 函数慢这么多？

Question

使用 pythonsrandom.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

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