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

Question

当使用pythonsrandom.shuffle函数时，我注意到使用sorted(l, key=lambda _: random.random())比使用random.shuffle(l)要快得多。据我了解，这两种方式都会产生完全随机的列表，那么为什么shuffle需要这么长时间呢？

以下是使用timeit模块的时间。

from timeit import timeit
setup = 'import randomnl = 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实现的，它本身就是一个围绕getrandbits的Python包装器，最终实现它的C级函数，最终可以调用几乎是严格必要的两倍，以确保输出是无偏的);sorted(和random.random)是用C语言实现的。在 Python 中执行工作的开销高于在 C 中执行类似工作的开销。