为什么（在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 之后，生成整数的最终方法也是迄今为止最快的。弄乱生成数字的范围大小并没有改变任何东西。

那么，为什么 random 比 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.
  

Answer 1

在我回答你的问题之前（别担心，我确实做到了），请注意常见程序员的习惯用法：

过早的优化是万恶之源。

虽然情况并非总是如此，但除非您需要，否则不要担心微观优化。

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

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

对结构良好、可读的代码进行更改将更容易，并且优化实际瓶颈通常会比大多数微优化提供更好的加速与时间编码比。花在思考两个表达式中哪一个运行得更快上的时间本来可以用来完成其他事情。

作为例外，我想说，了解为什么一个选项比另一个选项更快有时是值得的，因为这样您就可以将更一般的知识融入到您未来的编程中，让您可以更快地进行调用，而不必担心细节。

关于为什么我们不应该浪费时间担心速度已经足够了，让我们来谈谈速度。

看一下模块的源代码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，在调用 之前确保范围的边界（和步长）为整数、范围不为空且步长不为零，getrandbits这是在 C 中实现的。

仅此一点就造成了大部分的randint缓慢。然而，还有一个变数在起作用。

再深入一点，进入内部函数_randbelow，就会发现获取 0 和 之间的随机数的算法n非常简单：它获取 中的位数n，然后重复随机生成那么多位，直到结果为 no比...更棒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 位长度的测试，因为在检查 的 C 源代码时getrandbits，我发现它对这些数字使用了一个单独的、更快的函数。