go - `rand.Intn` 函数的内部工作原理

问题描述

不知何故，我碰巧查看了 Go 的源代码，了解它在传递一个数组长度时如何实现 Random 函数。

这是调用代码

func randomFormat() string {
    formats := []string{
        "Hi, %v. Welcome!",
        "Great to see you, %v!",
        "Hail, %v! Well met!",
    }
    return formats[rand.Intn(len(formats))]
}

Go 源代码：主要部分

func (r *Rand) Intn(n int) int {
    if n <= 0 {
        panic("invalid argument to Intn")
    }
    if n <= 1<<31-1 {
        return int(r.Int31n(int32(n)))
    }
    return int(r.Int63n(int64(n)))
}

Go 源代码：参考部分 - 大多数开发人员已经在他们的机器上或 go repo 上安装了这个。

// Int31n returns, as an int32, a non-negative pseudo-random number in [0,n).
// It panics if n <= 0.
func (r *Rand) Int31n(n int32) int32 {
    if n <= 0 {
        panic("invalid argument to Int31n")
    }
    if n&(n-1) == 0 { // n is power of two, can mask
        return r.Int31() & (n - 1)
    }
    max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
    v := r.Int31()
    for v > max {
        v = r.Int31()
    }
    return v % n
}
// It panics if n <= 0.
func (r *Rand) Int63n(n int64) int64 {
    if n <= 0 {
        panic("invalid argument to Int63n")
    }
    if n&(n-1) == 0 { // n is power of two, can mask
        return r.Int63() & (n - 1)
    }
    max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
    v := r.Int63()
    for v > max {
        v = r.Int63()
    }
    return v % n
}
func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) }
func (r *Rand) Int63() int64 { return r.src.Int63() }

type Source interface {
    Int63() int64
    Seed(seed int64)
}

我想了解随机函数如何封装所有内部函数。我对代码不知所措，如果有人必须用简单的英语计划步骤，那会是什么？

例如，我不明白做负 1 的逻辑

if n <= 1<<31-1

然后，我没有得到任何头部或脚趾的Int31n功能

  if n&(n-1) == 0 { // n is power of two, can mask
        return r.Int31() & (n - 1)
    }
    max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
    v := r.Int31()
    for v > max {
        v = r.Int31()
    }
    return v % n

标签： gobit-manipulationrandom-seed

解决方案

这更多是关于算法的问题，而不是关于 Go 的问题，但是 Go 有一些部分。无论如何，我将从算法问题开始。

缩小均匀随机数生成器的范围

假设我们有一个均匀分布的随机数生成器，它返回一个介于 0 到 7 之间的数字。也就是说，随着时间的推移，它将返回大约相同数量的 0、1、2、...、7，但它们之间没有明显的模式。

现在，如果我们想要一个在 0 到 7 之间均匀分布的随机数，这个东西就完美了。这就是它返回的内容。我们只是使用它。但是，如果我们想要一个介于 0 和 6 之间的均匀分布的随机数呢？

我们可以写：

func randMod7() int {
    return generate() % 7
}

因此，如果generate()返回 7（它有八分之一的机会这样做），我们将该值转换为零。但是，我们将在 8 次中获得 2 次归零，而不是 8 次中的 1 次。平均而言，我们将在 8 次中得到 1、2、3、4、5 和 6 中的 1 次，在 8 次中得到 2 次归零：每个实际零一次，每 7 次。

那么，我们需要做的是丢弃任何出现的 7：

func randMod7() int {
    for {
        if i := generate() < 7 {
            return i
        }
        // oops, got 7, try again
    }
}

现在，如果我们有一个名为 uniform-random-number-generator generate()，它返回一个介于 0 和（比如说）11 之间的值（12 个可能值），并且我们想要一个介于 0 和 3 之间的值（四个可能值），我们可以使用generate() % 4,因为这 12 个可能的结果会以相同的概率分为 3 组，每组 4 组。如果我们想要一个介于 0 和 5 之间的值，我们可以使用generate() % 6，因为 12 个可能的结果会以相等的概率分为两组，每组 6 个。事实上，我们需要做的就是检查我们的统一数生成器范围的素因数分解，看看什么模有效。12的因数是2、2、3；所以 2、3、4 和 6 都在这里工作。任何其他模数，例如generate() % 10，产生有偏差的结果：0 和 1 出现 12 次中的 2 次，但 2 到 9 出现 12 次中的 1 次。（注意：generate() % 12也有效，但有点毫无意义。）

在我们的特定情况下，我们有两个不同的统一随机数生成器可用。一, Int31(), 产生介于 0 和 0x7fffffff（十进制 2147483647，或 2 ³¹ - 1，或1<<31 - 1）之间的值。另一个 ,Int63()产生介于 0 和 0x7fffffffffffffff 之间的值（9223372036854775807，或 2 ⁶³ - 1，或1<<63 - 1）。这些范围分别包含 2 ³¹和 2 ^{63 个}值，因此它们的素数分解为 31 2s 或 63 2s。

这意味着我们可以为0 到 31的任何整数计算Int31()mod 2 ，而不会破坏我们的一致性。有了，我们可以做同样的事情，范围一直到 63。^kkInt63()k

介绍电脑

现在，从数学和计算机角度来说，给定[ .. ] 或 [ .. ] 中的任何非负整数n，以及正确范围内的非负整数k（分别不超过 31 或 63），计算integer n mod 2 ^k产生的结果与计算该整数并在设置k位的情况下执行位掩码操作相同。要获得该数量的设置位，我们需要取1 并减去 1。如果是 4，我们得到 1<<4 或 16。减去 1，我们得到 15，或 0xf，其中有四个 1 位。00x7ffffff00x7fffffffffffffff1<<kk

所以：

n % (1 << k)

和：

n & (1<<k - 1)

产生同样的结果。具体来说，当k==4，这是n%16或n&0xf。当k==5这是n%32或n&0x1f。试试k==0和k==63。

介绍 Go-the-language

我们现在准备考虑在 Go 中完成所有这些工作。我们注意到int(plain, unadorned int) 保证能够分别保持 -2147483648 和 +2147483647 (-0x80000000 到 +0x7fffffff) 之间的值。它可能会一直延伸到 -0x8000000000000000 到 +0x7ffffffffffffff。

同时，int32总是处理较小的范围，int64总是处理较大的范围。平原与其他两个int不同的类型，但实现与两者之一相同的范围。我们只是不知道是哪一个。

我们的Int31实现返回范围内均匀分布的随机数0..0x7ffffff。（它通过返回的高 32 位来r.Int63()实现这一点，尽管这是一个实现细节。）我们的Int63实现返回范围内均匀分布的随机数0..0x7ffffffffffffff。

Intn您在此处显示的功能：

func (r *Rand) Intn(n int) int {
    if n <= 0 {
        panic("invalid argument to Intn")
    }
    if n <= 1<<31-1 {
        return int(r.Int31n(int32(n)))
    }
    return int(r.Int63n(int64(n)))
}

只需根据的值选择两个函数之一n：如果小于或等于0x7fffffff( 1<<31 - 1)，则结果适合int32，因此它用于int32(n)转换n为int32、调用r.Int31n并将结果转换回int。否则，n超过的值0x7fffffff，意味着int具有更大的范围，我们必须使用更大范围的生成器，r.Int63n。除了类型之外，其余的都是相同的。

代码可以这样做：

return int(r.Int63n(int64(n)))

每次，但在 32 位机器上，64 位算术可能很慢，这可能很慢。（这里有很多可能和可能，如果你今天自己写这个，你应该从分析/基准测试代码开始。Go 作者确实这样做了，尽管这是很多年前的事；当时值得这样做花哨的东西。）

更多位操作

两个函数的内部Int31n都Int63n非常相似；主要区别在于所涉及的类型，然后在一些地方是最大值。同样，其原因至少部分是历史性的：在某些（现在大多是旧的）计算机上，Int63n变体比Int32n变体慢得多。（在一些非 Go 语言中，我们可能将它们编写为泛型，然后让编译器自动生成特定于类型的版本。）所以让我们看看Int63变体：

func (r *Rand) Int63n(n int64) int64 {
    if n <= 0 {
        panic("invalid argument to Int63n")
    }
    if n&(n-1) == 0 { // n is power of two, can mask
        return r.Int63() & (n - 1)
    }
    max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
    v := r.Int63()
    for v > max {
        v = r.Int63()
    }
    return v % n
}

该参数n具有 type int64，因此它的值不会超过 2 ⁶³ -1 或0x7fffffffffffffff9223372036854775807。但它可能是负数，负值将无法正常工作，所以我们要做的第一件事就是对此进行测试，如果是，则恐慌。如果输入为零，我们也会感到恐慌（这是一种选择，但现在注意它很有用）。

接下来我们进行n&(n-1) == 0测试。这是对 2 的幂的测试，有一个小缺陷，它适用于多种语言（具有位掩码的语言）：

在数字的二进制表示中，2 的幂始终表示为单个设置位。例如，2 本身是 00000001 ₂，4 是 00000010 ₂，8 是 00000100 ₂，依此类推，直到 128 是 10000000 ₂。（因为我只“画”了 8 位，所以这个系列的最大值为 128。）
从该数字中减去 1 会导致借位：该位变为零，并且所有较小的位都变为 1。例如， 10000000 ₂ - 1 是 01111111 ₂。
如果最初只设置了单个位，则将这两者加在一起会产生零。如果不是——例如，如果我们最初有值 130 或 10000010 ₂，减 1 会产生 10000001 _2——最高位没有借位，所以最高位在两个输入中都设置，因此在与运算中设置结果。

轻微的缺陷是，如果初始值为零，那么我们有0-1，这会产生全 1；0&0xffffffffffffffff也是零，但零不是二的整数幂。（2 ⁰是 1，而不是 0。）这个小缺陷对于我们在这里的目的来说并不重要，因为我们已经确保对这种情况感到恐慌：它只是不会发生。

现在我们有了最复杂的一行：

    max := int64((1 << 63) - 1 - (1<<63)%uint64(n))

这里重复出现63的 s 是因为我们有一个从零到 2 ⁶³ -1 的值范围。 1<<63 - 1是（仍然，再次，总是）9223372036854775807 或0x7fffffffffffffff. 同时，1<<63不减去 1 是 9223372036854775808 或0x8000000000000000。 此值不适合int64但确实适合uint64. 因此，如果我们n变成 a uint64，我们可以计算uint64(9223372036854775808) % uint64(n)，这就是%表达式所做的。通过使用uint64这个计算，我们确保它不会溢出。

但是：这个计算是怎么回事？好吧，回到我们的示例，其中 agenerate()产生 [0..7] 中的值。当我们想要 [0..5] 中的数字时，我们必须丢弃6 和 7。这就是我们要在这里做的事情：我们想要找到应该丢弃值的值。

如果我们取 8%6，我们会得到 2。8 比 3 位generate()生成的最大值大一。8%6 == 2 是我们必须丢弃的“高值”的数量：8-2 = 6 我们想要丢弃 6 或更多的值。从中减去 1，我们得到 7-2 = 5；我们可以接受这个输入范围内的数字，从 0 到 5（包括 0 到 5）。

所以，这个有点花哨的设置计算max只是找出我们喜欢的最大值是多少的一种方法。大于需要丢弃的值。max

即使n比我们的生成器返回的要少得多，这个特定的计算也能很好地工作。例如，假设我们有一个四位生成器，返回 [0..15] 范围内的值，我们想要 [0..2] 范围内的数字。因此，我们n是 3（表示我们想要中的数字[0..2]）。我们计算 16%3 得到 1。然后我们取 15（比我们的最大输出值小一） - 1 得到 14 作为我们可接受的最大值。也就是说，我们将允许 [0..14] 中的数字，但排除15。

使用 63 位生成器在 [0..9223372036854775807] 中返回值，并且 n==3，我们将 max 设置为 9223372036854775805。这就是我们想要的：它会抛出两个偏置值，9223372036854775806 和 9223372036854775807。

代码的其余部分只是这样做：

    v := r.Int63()
    for v > max {
        v = r.Int63()
    }
    return v % n

我们选择一个Int63范围的数字。如果超过max，我们选择另一个并再次检查，直到我们选择在 [0..max] 范围内的一个，包括max。

一旦我们得到一个在范围内的数字，我们就会% n根据需要缩小范围。例如，如果范围是 [0..2]，我们使用v % 3. 如果 v 是（比如说）14，14%3 是 2。我们的实际最大值再次是 9223372036854775805，无论 v 是什么，介于 0 和那个之间，v%3 都在 0 和 2 之间，并且保持均匀分布，没有轻微的偏差到 0 和 1（9223372036854775806 会给我们额外的一个0，而 9223372036854775807 会给我们额外的一个1）。

（现在对函数重复上面的int32and32和1<<32, Int31。）