为什么（在Python中）random.randint比random.random慢得多？

Question

我对一些随机整数生成代码的速度产生了好奇。 我编写了以下代码来进行测试：

from random import random
from random import choice
from random import randint
from math import floor
import time

def main():
    times = 1000000
    
    startTime = time.time()
    for i in range(times):
        randint(0,9)
    print(time.time()-startTime)
    
    startTime = time.time()
    for i in range(times):
        choice([0,1,2,3,4,5,6,7,8,9])
    print(time.time()-startTime)
    
    startTime = time.time()
    for i in range(times):
        floor(10*random())##generates random integers in the same range as randint(0,9)
    print(time.time()-startTime)

main()

该代码的一次试验结果为：

0.9340872764587402

0.6552846431732178

0.23188304901123047

即使执行了乘法和math.floor，最终生成整数的最快方式仍然是随机方式。改变生成数字范围的大小并没有改变任何事情。

那么，为什么随机方式比randint更快呢？除了易于使用、可读性好以及不容易出错等原因外，有没有人喜欢randint而不是random（例如，randint产生更多的伪随机整数）？如果floor（x * random()）感觉不够可读，但你想要更快的代码，你应该选择专门的程序吗？

def myrandint(low,high):   ###still about 1.6 longer than the above, but almost 2.5 times faster than random.randint
    return floor((high-low+1)*random())+low  ##returns a random integer between low and high, inclusive. Results may not be what you expect if int(low) != low, etc. But the numpty who writes 'randint(1.9,3.2)' gets what they deserve.
  

- philosofool

---

在底层，randint 函数使用了 randrange，而它在 Python 中的实现有很多开销：https://github.com/python/cpython/blob/master/Lib/random.py#L211 基本上，在每次调用函数时，它都会进行大量错误检查。 如果你不需要这些检查，当然可以使用一个更简单的实现。 - ayhan

使用 floor(n*random()) 计算 [0, n) 中的整数存在偏差。对于 n=10，这种偏差在统计上是无法检测到的，但对于较大的 n 可能会有问题。请参见 https://bugs.python.org/issue9025 以了解更多讨论。 - Mark Dickinson

Answer 1

在回答你的问题之前（不用担心，我会回答），请注意程序员常用语：

过早优化是万恶之源。

虽然这并非总是如此，但不要担心微小的优化，除非你需要它们。

对于Python来说，情况更是如此：如果你正在编写一些速度至关重要的东西，通常你会想用一种运行速度更快的语言来编写，比如C语言。然后，如果你想在应用程序的非关键部分中使用Python（例如NumPy），你可以为那些C代码编写Python绑定。

与其专注于让代码中的单个表达式或函数尽可能快地运行，不如专注于你使用的算法和代码的整体结构（以及使其可读性高，但你已经意识到了这一点）。然后，当你的应用程序开始运行缓慢时，你可以对其进行剖析以找出哪些部分耗费了最多时间，并仅改进这些部分。

这些更改将更容易应用于结构良好、易读的代码，并优化实际瓶颈通常比大多数微观优化提供更好的加速编码比率。浪费时间思考哪个表达式运行得更快是你本可以用来完成其他事情的时间。

作为一个例外，我会说，学习为什么一个选项比另一个选项更快有时值得花时间，因为这样你可以将那些更一般的知识融入到你未来的编程中，让你做出更快的调用而不必担心细节。

但是关于为什么我们不应该浪费时间担心速度的问题已经足够了，让我们谈谈速度吧。

---

看看random模块的源代码（对于CPython 3.7.4），开头注释的这行话给出了一个简短的答案：

* The random() method is implemented in C, executes in a single Python step,
  and is, therefore, threadsafe.

第一条语句对我们来说最重要。 random是一个C函数的Python绑定，因此其操作的复杂性以机器码的惊人速度运行，而不是相对较慢的Python速度。

另一方面，randint在Python中实现，并因此遭受了显着的速度惩罚。 randint调用randrange，该函数确保范围的边界（和步长）为整数，范围不为空，并且步长不为零，然后调用在C中实现的getrandbits。

这就是randint大部分缓慢的原因。 但是，还有一个变量在起作用。

稍微深入一下内部函数_randbelow，发现获取0到n之间的随机数的算法非常简单：它获取n中的位数，然后重复生成那么多位的随机数，直到所得到的数字不大于n。

平均而言（在所有可能的 n 值上），这对结果影响不大，但是在极端情况下，它是明显的。

我编写了一个函数来测试循环的影响。以下是结果：

bits   2 ** (n - 1)   (2 ** n) - 1   ratio
  64   1.358526759    1.084741422    1.2523968675
 128   1.43073282     1.02119227     1.4010415688
 256   1.600253063    1.271662798    1.2583941793
 512   1.845024581    1.363168823    1.3534820852
1024   2.371779281    1.620392686    1.4637064839
2048   2.98949864     2.01788896     1.48149809

第一列是位数，第二列和第三列是在超过1,000,000次运行中找到具有该位数的随机整数的平均时间（以微秒为单位）。最后一列是第二列和第三列的比率。

您会注意到，具有给定位长度的最大数字的平均运行时间大于具有该位长度的最小数字。这是因为循环的原因：

当寻找小于最大n位数的n位数时，仅在生成最大数字时需要进行第二次尝试，这仅适用于非常小的n。但是要找到比最小值更小的数字（2 ^（n-1）是一个1位后跟n-1个0位），则一半的尝试失败。

---

补充说明：我删除了位长度为1到32的测试，因为在查看getrandbits的C源代码时，发现它使用了一个单独且更快的函数来处理这些数字。

- jirassimok