什么是随机生成？

# 什么是随机生成？ 来源：https://alperenkeles.com/posts/what-is-random-generation/ 发布于 2026-05-10 :: 阅读时间 22 分钟 :: 标签：testing (https://alperenkeles.com/tags/testing/) 我本想将这篇文章作为《什么是属性？》(https://alperenkeles.com/posts/what-is-a-property/) 的续作，在其中谈谈基于属性的测试 (Property-Based Testing) 库如何生成随机结构，别担心，我还是会写的！但我意识到，如果不谈论计算机中的随机性，这篇文章就不完整。因此，文章的第一部分将深入探讨我们认为在 PBT 中已经“解决”的核心问题，即设计良好的随机数生成器，而第二部分将讨论如何在此类 RNG 之上实现复杂的随机数据生成器。 ## 计算机中的随机数生成 (https://alperenkeles.com/posts/what-is-random-generation/#random-number-generation-in-computers) 随机性是一个复杂的话题。粗略来说，它意味着不确定性、无序性，或者更正式地说，高熵。当然，在计算机程序中，随机生成是伪造的；我们使用的是 PRNG（伪随机数生成器），这是一种高熵函数，其种子与生成的随机数之间的关系尽可能任意。 PRNG 的一个非常简单示例是线性同余发生器（linear congruential generator, LCG）(https://en.wikipedia.org/wiki/Linear_congruential_generator)： ```javascript function lcg(seed: number): () => number { const a = 1664525; const c = 1013904223; const m = 2 ** 32; let state = seed; return () => { state = (a * state + c) % m; return state; }; } const rand = lcg(42); rand(); // 1083814273 rand(); // 380859148 rand(); // 2338846736 ``` LCG 输出的随机性取决于其参数选择，例如 `a = 1` 和 `c = 1` 会导致结果为模 `m` 的计数器模块。据维基百科称，LCG 的前身似乎是 Lehmer 随机数生成器 (https://en.wikipedia.org/wiki/Lehmer_random_number_generator)，其中 `c = 0`，`m` 要么是素数，要么是素数的幂；初始种子必须是 `m` 的互质数 (https://en.wikipedia.org/wiki/Coprime_integers)，且 `a` 必须是“模 m 下具有高乘法阶的元素”。 正如我所说，我在撰写此帖时也在学习随机数生成的知识，所以我创建了一个可视化展示。这里有一些预设，如果你想尝试其他数字也可以试试。 ### 可视化 LCG 质量 (https://alperenkeles.com/posts/what-is-random-generation/#visualizing-lcg-quality) 选择一个预设或调整参数，观察 `a`、`c` 和 `m` 对输出的影响。左侧面板绘制连续的三元组 `(xn, xn+1, xn+2)`（如果切换视图则为成对 `(xn, xn+1)`）——如果那里出现可见的结构，说明生成器泄露了谱测试会发现的模式。右侧面板是 `[0, 1]` 上的直方图，它可以告诉你输出至少在表面上是否均匀。 acms seedsamples 这里的模式意味着弱随机性——试着在 3D 中运行 RANDU 查看 [0, 1] 上的分布 有一整个序列的随机数生成器，一直到 2023 年都有新的发布 (https://en.wikipedia.org/wiki/List_of_random_number_generators#Pseudorandom_number_generators_(PRNGs))，这是一个活跃的研究领域，我们经常使用其研究成果，许多算法出现在随机生成库以及许多编程语言的标准库中。 当然，如果没有著名的熔岩灯（lava lamps），讨论是不完整的！ **Cloudflare 熔岩灯** 一旦我们有了一个可以从任意种子产生高熵随机数的算法，我们也想要这些种子的高熵源。对于 Cloudflare，显然是他们没有图案的熔岩灯；对于我们许多人来说，它是操作系统的随机源 `/dev/urandom` (https://en.wikipedia.org/wiki//dev/random)，它利用计算机唯一的真实随机源——物理世界来生成种子。 凭借真正的随机性和设计良好的算法，我们可以生成均匀的随机 64 位数字，那么我们就完成了吗？嗯，问题是，我们真的不想生成 64 位数字，对吧？我们想生成布尔值、浮点数、有界数字、集合、复杂结构……。我们也不想要纯粹的均匀随机性，我们需要能够在需要时偏置随机生成器，也许以适应某些其他分布；幸运的是，我们可以从简单的原始 64 位随机数构建所有这些。 ### 生成浮点数 (https://alperenkeles.com/posts/what-is-random-generation/#generating-floats) 随机浮点数通常通过生成区间 (0.0, 1.0) 内的随机浮点数，并根据范围缩放该数字来生成。Nima Badizadegan 有一篇更好的关于随机浮点生成的文章 (https://specbranch.com/posts/fp-rand/)，所以我只在这里提供要点，以下内容来自 Haskell random (https://github.com/haskell/random/blob/master/src/System/Random/Internal.hs#L1443-L1449) 库： ```haskell -- | 在范围 ([0, 1]) 内生成均匀分布的 'Double'。 -- 数字是通过生成均匀的 'Word64' 并除以 (2^{64}) 来生成的。 -- 它用于实现 'Double' 的 'UniformRange' 实例。 -- -- @since 1.2.0 uniformDouble01M :: forall g m. StatefulGen g m => g -> m Double uniformDouble01M g = do w64 <- uniformWord64 g return $ fromIntegral w64 / m where m = fromIntegral (maxBound :: Word64) :: Double ``` 本质上，我们生成一个随机的 64 位整数，将其除以浮点数字域中可能的最大 64 位整数： ```javascript function randomFloat(): number { return rand() / 2 ** 64; } ``` 如果我们有一个不同的范围，我们可以直接将 (0, 1) 缩放到 [a, b)： ```javascript function randomFloatInRange(a: number, b: number): number { return a + (b - a) * randomFloat(); } ``` ### 生成布尔值 (https://alperenkeles.com/posts/what-is-random-generation/#generating-booleans) 生成均匀随机布尔值很容易，`rand` 给我们 64 个随机位，我们可以只检查其中一个； ```javascript function randomBoolean(): boolean { return (rand() & 1) === 0; } ``` 但是你有勇气生成有偏的布尔值吗？这就是我们可以依赖随机浮点生成的地方： ```javascript function randomBiasedBoolean(p: number): boolean { return randomFloat() < p; } ``` ### 生成有界整数 (https://alperenkeles.com/posts/what-is-random-generation/#generating-bounded-integers) 我们可以轻松地将 `randomInt(a, b)` 建模为 `a + randomInt(0, b - a)`，因此我们可以专注于解决 `[0, a)` 的随机生成。一个简单的近似值是 `rand() % a`，但存在一个经典问题：偏差（bias）。当 `a` 不是 2 的幂时，区间的某一部分会被多击中一点，因为桶 (`k % a`) 不会有相同数量的元素，假设我们有 4 位整数，我们的边界是 3，如组件中所示。分布如下： ``` 0: [0, 3, 6, 9, 12, 15] 1: [1, 4, 7, 10, 13] 2: [2, 5, 8, 11, 14] ``` 正如你所见，我们有 6/16 的机会得到 0，但只有 5/16 的机会得到 1 或 2。生成零有 1/16（0.0625）的偏差。当然，随着我们从更大的区间中选择数字，这种偏差会越来越低，因为分母每次都会变大；所以在 64 位时，这种影响可以忽略不计。然而，我们仍然想解决这个问题。怎么做？我们只需不断迭代，直到得到一个我们喜欢的随机数！ source bit widthbound nsamples20000 `rand() mod n` — 粉色条是受偏好的桶 拒绝采样 —— 在蒙特卡洛噪声范围内平坦 “受偏好”数字的工作原理是，对于给定的采样空间 2^N 和边界 `a`，数字 `i < 2^N - k * a`，其中 `k * a` 是小于或等于 `2^N` 的 `a` 的最大倍数。对于 `N=4`，`a=3`，`k` 是 `5` 的简单情况，`i < 2^4 - 5 * 3` 仅给出 `0`。但对于任何 `(N, a)`，这永远不会超过所有输入的 50%。效果在 `2^(N-1) + 1` 处最大，例如 `N=4` 和 `a=9`。在这里，边界内除了 2 以外的所有数字都有偏差，并且随机源内高于边界的所有数字“就是”偏差。即使在这种最坏的情况下，我们击中采样空间有偏部分的概率也略低于 50%。所以，我们可以简单地拒绝任何有偏的采样，并以最小的成本继续采样，这里是 Java 中的一个示例（取自）(https://web.archive.org/web/20200520071940/https://www.pcg-random.org/posts/bounded-rands.html)： ```java static uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t x, r; do { x = rng(); r = x % range; } while (x - r > (-range)); return r; } ``` 现在我们可以随机生成简单类型，让我们看看如何在基于属性的测试中实际使用这些构建块。 ## 为程序测试生成随机数据 (https://alperenkeles.com/posts/what-is-random-generation/#generating-random-data-for-testing-programs) 我们在生成结构时需要的第一件事是能够依赖性地生成多个事物。好吧，从技术上讲我们可以直接写： ```javascript function genNum(): number { let b = randBool(0.5); let c = b ? randBounded(0, 10) : randBounded(10, 20); return c; } ``` 这里有一个小问题，就是 RNG 被隐藏了。理想情况下，我们希望拥有周围的随机性状态，以便我们可以明确地操纵它。这并不难，我们只需将 `rng` 传递给每个使用它的函数： ```javascript function genNum(rng): number { let b = randBool(rng, 0.5); let c = b ? randBounded(rng, 0, 10) : randBounded(rng, 10, 20); return c; } ``` 另一种流行的技术是（我想起源于 QuickCheck）是让生成器返回生成的食谱（`Gen`），而不是期望 `rng` 来计算 `T` 的函数。 ```javascript function getNum(): Gen { bind(randBool(0.5), (b) => bind(c ? randBounded(0, 10) : randBounded(10, 20), (c) => (ret c) )) } ``` 还有一个类型为 `Rng -> Gen -> T` 的另一个函数 `sample`，允许你在生成生成器后干净地提取 `T`，而无需传递 RNG。这种方法的好处是，你的生成器组合现在隐藏在 `bind` 之下，所以你实际上可以做的不仅仅是生成随机结构。例如，你可以在不同的随机源和随机样式之间切换。最简单的是使用就地可变 RNG： ```javascript // c1 改变 rng type Gen = (rng) => T; function bind(c1: Gen, c2: (T1) => Gen) { return (rng) => { const t1 = c1(rng); return c2(t1)(rng); }; } ``` 使用可分裂 RNG (https://wiki.haskell.org/wikiupload/7/74/Hiw2012-michal-palka.pdf) 稍微更安全；它们是纯的且可并行化的，代价是稍慢一些。 ```javascript type Gen = (rng: Rng) => T; function bind(c1: Gen, c2: (T1) => Gen): Gen { return (rng) => { const [r1, r2] = split(rng); return c2(c1(r1))(r2); }; } ``` 最后一种流行的选项是使用选择缓冲区或序列，Hypothesis 风格： ```javascript type Gen = (buf: ChoiceBuffer) => T; function bind(c1: Gen, c2: (T1) => Gen): Gen { return (buf) => { const t1 = c1(buf); return c2(t1)(buf); }; } ``` 在随机缓冲区方法中，每个生成器通过读取若干随机字节沿缓冲区移动光标；由此得出的推论是，你可以获得*内部缩小（internal shrinking）*，并且可以使用现有的模糊测试工具（fuzzer）来驱动你的测试。然而，其中任何一种方法都能给你大致相同的功能：生成某物，更新 RNG 状态，生成下一件事，等等……所以，假设我们要编写一个列表生成器，下面是一个均匀随机列表的样子： ```javascript function genList(rng, g: Gen): T[] { const len = randPositiveInteger(rng); const out = []; for (let i = 0; i < len; i++) { out.push(g(rng)); } return out; } ``` 这里的问题是，尽管理论上合理，但我们*不*希望长度均匀的列表分布在均匀长度上。这里有两种相互竞争的力量，一种是生成和测试短列表要快得多。因此，我们可以在生成和测试长度为 10000 的列表所需的时间内生成为和测试 1000 个长度为 10 的列表。这与“小范围理论（small-scope theory）”相结合，该理论断言我们可以通过大型测试用例发现的许多错误也会在小规模情况下出现，这是使用穷尽搜索空间从小输入到大输入的枚举测试技术的基础。当然，并非所有错误都在小规模出现，而且穷举搜索*非常*昂贵。我们还可以将这个事实与另一个理论结合，该理论指出大输入会表现出你在各种较小测试中观察到的行为，因此生成和测试一个大输入可能比 `N` 个小输入能给你更多关于系统的信息。这两种理论（在不同情况下都可能是正确的）意味着我们需要同时生成小输入和大输入，而且实际上我们可能不想均匀生成，我们想偏向搜索空间的特定部分。例如，Hypothesis 有 `_constant_floats` 和 `_constant_strings`，它们将它们注入到其他非常随机的输入集中。（偷看）： ```python _constant_floats = ( [ ... 3.402823466e38, 9007199254740992.0, 1 - 10e-6, 2 + 10e-6, 1.192092896e-07, 2.2204460492503131e-016, ] + [2.0**-n for n in (24, 14, 149, 126)] # float16,32 的最小 (次) 正规数 + [float_info.min / n for n in (2, 10, 1000, 100_000)] # float64 中的次正规数 ) _constant_strings = { ... # 文本的可读变体 (粗体/斜体/脚本) "The quick brown fox jumps over the lazy dog", "The quick brown fox jumps over the lazy dog", "The quick brown fox jumps over the lazy dog", "The quick brown fox jumps over the lazy dog", "The quick brown fox jumps over the lazy dog", # 倒置文本 "ʇǝɯɐ ʇᴉs ɹolop ɯnsdᴉ ɯǝɹo˥", # Windows 中的保留字符串 "NUL", "COM1", "LPT1", # scunthorpe 问题 "Scunthorpe", # zalgo 文本 "Ṱ̺̺̕o͞ ̷i̲̬͇̪͙n̝̗͕v̟̜̘̦͟o̶̙̰̠kè͚̮̺̪̹̱̤ ̖t̝͕̳̣̻̪͞h̼͓̲̦̳̘̲e͇̣̰̦̬͎ ̢̼̻̱̘h͚͎͙̜̣̲ͅi̦̲̣̰̤v̻͍e̺̭̳̪̰-m̢iͅn̖̺̞̲̯̰d̵̼̟͙̩̼̘̳ ̞̥̱̳̭r̛̗̘e͙p͠r̼̞̻̭̗e̺̠̣͟s̘͇̳͍̝͉e͉̥̯̞̲͚̬͜ǹ̬͎͎̟̖͇̤t͍̬̤͓̼̭͘ͅi̪̱n͠g̴͉ ͏͉ͅc̬̟h͡a̫̻̯͘o̫̟̖͍̙̝͉s̗̦̲.̨̹͈̣", # ... } ``` 另一种典型方法是使用“尺寸（size）”进行偏置。就我所知，Hypothesis 的情况是从少量小输入开始，然后提升为均匀随机性（常量除外）。在 QuickCheck 的情况下，尺寸函数有点奇怪： ```haskell computeSize :: State -> Int computeSize MkState{replayStartSize = Just s,numSuccessTests = 0,numRecentlyDiscardedTests=0} = s -- NOTE: 小心更改这个，因为你也需要更改 `prop_discardCoverage`，因为它目前依赖于 -- 由此函数产生的序列。 computeSize MkState{maxSuccessTests = ms, maxTestSize = mts, maxDiscardedRatio = md,numSuccessTests=n,numRecentlyDiscardedTests=d} -- 例如，带有 maxSuccess = 250, maxSize = 100，如下所示： -- 0, 1, 2, ..., 99, 0, 1, 2, ..., 99, 0, 2, 4, ..., 98. | n `roundTo` mts + mts <= ms || n >= ms || ms `mod` mts == 0 = (n `mod` mts + d `div` dDenom) `min` mts | otherwise = ((n `mod` mts) * mts `div` (ms `mod` mts) + d `div` dDenom) `min` mts where -- 随着丢弃测试的增加率增加尺寸大小的倒数 -- 如果丢弃比率很高，我们可以承担这个较慢，但如果丢弃比率很低，我们风险过早退出 dDenom | md > 0 = (ms * md `div` 3) `clamp` (1, 10) | otherwise = 1 -- 没关系，因为不允许丢弃 n `roundTo` m = (n `div` m) * m ``` 基本上，尺寸是测试数量模最大尺寸的计数器，有一个小的边缘情况是最后一个周期将不完整，所以他们增加步幅使其也完成。在 QuickChick 或我的其他分支中，我通常只是使用 `log2(N)` 带有一些向下偏差以确保我们没有忽视小输入（`log2(16) = 4`，这意味着最多大小 3 的输入仅针对 15 个输入进行测试，不太好）。我不认为 PBT 文献真正就正确的方法达成一致，这也是