作者：marinewu，腾讯PCG客户端开发工程师

| 导语 本文借 2022 年 8 月 Readability Golang 考试代码，讲解在使用随机数的常见陷阱和解决方案。 内容主要以 Go 的标准库进行讲解，但问题与语言无关。

问题

以下是 8 月 Golang 的考试代码片段。该代码在使用随机数时存在哪些问题？

// ShouldTurnOn 被调用时会进行判定，按 Config.EnableProbability% 的概率返回真
func ShouldTurnOn() bool {
	rand.Seed(time.Now().UnixNano())
	randNum := rand.Uint64() % 100
	return randNum <= config.EnableProbability
}

概率非一致分布 Non-Uniform distribution

经典错误：通过取余操作对离散一致分布间做映射时，因为不能除尽导致偏移，不构成一致分布。

业务场景通常需要获取 [0, M) 的一致分布。但大部分随机数生成器都是在 2 的整数次幂上，即 [0, 1 << x) 的一致分布。我们通常希望通过某些简单的算术规则将 [0, 1 << x) 的一致分布映射至 [0, M) 的一致分布。

非常常见的做法是样例中的取余，如 rand() % 100， 获得 [0, 100) 的一致分布。这样非常简单直观，但是，有缺陷。

简单的数论知识告诉我们 2 的幂永远无法被 100 除尽，因此，rand() 的一致分布的所有值无法被均匀分配到 [0, 100) 这 100 个桶中。这使得前几个桶被分配的概率会比后面的桶高。当 rand() 的取值范围很大，如 [0, 1 << 64) 时，影响较小。但是这仍然是一个 bug，尤其在原分布的桶较小时，如原分布是 [0, 32767) 时，影响更大。

因此，当我们希望从 [0, M) 的一致分布生成 [0, N) 的一致分布时，要小心概率偏移。一个正确的处理方案是：

当 M > N 时：

• 截取 [0, M) 中的部分分布 [0, M')，M' 是小于 M 且能被 N 除尽的最大值。它仍然是一个一致分布。
• 就 [0, M') 的生成随机数对 N 取模，即可保证生成 [0, N) 的一致分0905布。
• 当 M 能被 N 整除时，可以直接取余。

伪代码如下：

// randN returns a normally distributed result from [0, N)
// It uses a normally distributed random number generator [0, M)
func randN() int {
  max = M / N * N (
  m = randM()
  if m >= max {
    // If m >= max, the nubmer is out of the distribution [0, max). Just throw away.
    return randN()
  }
  // Otherwise, just return the remainder.
  return m % N
}

这段代码递归深度期望接近 1。具体期望计算与文末的扩展阅读的面试题相关。

当 M < N 时，一个可选的方案是：

• 通过取 t 次 M 值，直到 M ** t > N，以此生成一个 [0, M ** t) 的一致分布
• 以下处理同 M > N

上述方案正是 Go 的 rand 标准库的 rand.Int63n(int) 等提供 Uniform Distribution 方法的实现原理：Go Rand 实现

差一错误 Off-By-One Error

There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors.

--Jeff Atwood

经典错误：边界处理失误，导致实际阈值比预期大 1%

注意返回的一致性分布是 [-0, 100)，也就是 0, 1, 2, ..., 99 的均匀分布。例如，当使用

return randNum <= 80

实际上有 81 个值 (0, 1, ..., 80）会被包含。这使得实际的概率为 81%。

一定要注意 off-by-one error。这种错误在线上难以察觉，但是在统计意义上会对业务造成明显影响。

Off-By-One 是隐蔽又容易出错的问题，在离散分布里，一定要注意区间的开闭。

当需要一个 [a, b] 的离散一致性分布时，其与 [a, b+1) 等价。因此，使用标准库时，应该先获取一个 [0, b - a + 1) 的一致分布，然后映射到 [a, b]。即：

Uniform [a, b] ==
Uniform [a, b + 1) ==
Uniform [0, b + 1 - a) + a

性能、正确、安全

经典错误：频繁 Seed。

我们平时使用的大部分随机数是伪随机数，即算术生成随机数。它的原理是通过算术运算，迭代地生成一系列统计上均匀分布的结果。即， 随机数的序列是：

rand(Seed), rand(rand(Seed)), rand(rand(rand(Seed))), ...

当调用 rand 后，生成的随机数会作为新的种子。因此，正常情况下，不需要每次调用 rand 前都初始化种子。样例的代码使用时间作为初始化种子，这样做会有几个可能的问题：

• time.Now() 并不廉价。频繁获取时间是无谓的性能损耗。
• 重置随机数种子并没有必要。本质上，这相当于不再使用 rand 生成的随机数，而是使用时间作为随机数。如果在同一纳秒内调用这个方法，会产生完全一样的随机数。
• 因此，只要在 main() 或者 在 init() 函数中初始化一次即可。如果不介意每次的随机数序列提确定性的，也可以跳过初始化 Seed。

rand.Seed 和取随机数的方法是线程安全的，但是这可能会导致性能问题。当需要高频大量生成随机数时，可能会造成大量的锁竞争。因此，应该使用新的 Source，如：

rand.New(rand.NewSource(seed)) // Caution: not thread-safe!

但是要注意，NewSource 默认是并发不安全的，因此，不要在协程/线程之间共享 NewSource 所产生的 Source。

另外，注意 rand 包是密码学不安全的。换言之，可能会被攻击者利用，即攻击者可能会根据生成的随机数的特征预测随机数。因此永远不要使用 rand 进行一些敏感随机数的生成。如果需要防攻击的随机数生成器，使用 crypto.rand(rand package - crypto/rand - Go Packages)

改进

经过以上的分析，代码改进如下：

// ShouldTurnOn 被调用时会进行判定，按 Config.EnableProbability% 的概率返回真
func ShouldTurnOn() bool {
	return rand.int(100) < config.EnableProbability
}

进一步阅读

• Rand considered Harmful Talk： https://www.youtube.com/watch?v=LDPMpc-ENqY
• Abseil 关于 Random 的使用 Trips (C++，但道理适用）abseil / The Abseil Random Library
• XKCD 关于随机数的漫画：

221: Random Number - explain xkcd

我用 Google 验证过，确实 4 就是随机的：

扩展：一道有关随机数的面试题

Jane Street 面试题：

给定一个不均匀的硬币，抛出硬币，有 2/3 的概率出现正面， 1/3 的概率出现反面。如何模拟一个普通的公平的硬币？

例如，可以抛两次，如果是 正+反，看作是正面。如果是 反+正，看作是反面。其它情况，重新抛即可。

问 1：能得出结果（正/反），抛这枚不均匀硬币的次数的期望是多少？

问 2：是否有抛硬币次数期望更低的方案？