65.9K
CodeProject 正在变化。 阅读更多。
Home

涉及随机化最常见的主题

Peter Occil
starIconstarIconstarIconstarIconstarIcon

5.00/5 (3投票s)

2020年6月15日

公共领域

9分钟阅读

viewsIcon

12580

根据问答网站问题分析，一些最常见的随机生成问题。

引言

本页面介绍编程中涉及随机化（包括“随机数生成”）的一些最常见主题，并为希望解决随机化问题的程序员提供指南。

本页面中的主题是根据对 **Stack Overflow** 问题的分析选择的，这些问题最常被标记为其他问题的重复（使用 **Stack Exchange Data Explorer** 查询，名为“按标签列出的最受欢迎重复目标”，标签名为“random”）。

分析显示，以下主题是最常被问到的主题之一：

  • 在给定范围内生成均匀随机整数。
  • 在给定范围内生成均匀随机浮点数。
  • 在给定范围内生成唯一随机整数。
  • 从列表中选择一个随机项目。
  • 从列表中选择几个唯一项目。
  • 以不同概率选择项目。
  • 从数据库中选择随机记录。
  • 洗牌。
  • 生成由受限字符集（例如仅A到Z、a到z、0到9）中的字符组成的随机文本字符串。

并非所有主题都在上面涵盖。值得注意的是，除非底层问题存在于多个API或语言中，否则分析会忽略API特定或编程语言特定的问题。

另一个值得注意的趋势是，这些主题是在缺少方便的API来完成这些任务的编程语言中被提出的。这就是为什么我建议新的编程语言API 在其标准库中提供涵盖上述主题的功能，以减轻使用该语言的程序员的负担。

以下部分将详细介绍上述主题，并提供解决建议。许多链接指向我文章“随机化和采样方法”中的章节。

本文档使用伪代码约定。

本页面中介绍的所有随机化方法都假设我们有一个“真正”随机且无偏的数字源。

目录

范围内的均匀数字

有关在给定范围内生成均匀随机_整数_的算法，请参见“均匀随机整数”。需要注意的是，大多数常用随机数生成器输出32位或64位非负整数，对于JavaScript，惯用的 `(Math.random() < 0.5 ? 0 : 1)` 在许多实际情况下都可以作为随机位生成器。以下是使用J. Lumbroso（2013）的Fast Dice Roller(1)在区间[**`minInclusive`，`maxExclusive`）中生成随机整数的JavaScript示例：

function randomInt(minInclusive, maxExclusive) {
  var maxInclusive = (maxExclusive - minInclusive) - 1
  if (minInclusive == maxInclusive) return minInclusive
  var x = 1
  var y = 0
  while(true) {
    x = x * 2
    var randomBit = (Math.random() < 0.5 ? 0 : 1)
    y = y * 2 + randomBit
    if(x > maxInclusive) {
      if (y <= maxInclusive) { return y + minInclusive }
      x = x - maxInclusive - 1
      y = y - maxInclusive - 1
    }
  }
}

许多常见编程语言没有方便或正确的方法来生成特定范围内的随机数。例如：

  • Java的 `java.util.Random` 在版本8之前有方法可以生成区间 [0, n) (nextInt) 内的 `int`，但没有该区间内的 `long` 或任意区间 [a, b) 内的整数。后来提供了名为 `longs` 和 `ints` 的附加方法来提供此功能，但即便如此，它们通常不如现有的 `nextInt` 方法方便。
  • JavaScript 直到最近只有一个用于随机数生成的 API，即 `Math.random()`，并且没有用于随机整数生成或洗牌等内置方法。诸如 `Math.floor(Math.random()*x)+y` 之类的简单解决方案不能保证可靠工作，部分原因在于 JavaScript 不要求 `Math.random` 有任何特定的实现。
  • C 语言的 `rand` 函数生成预定范围 ([0, `RAND_MAX`]) 内的随机整数，该范围不受应用程序控制。顺便说一句，这只是 `rand` 函数存在的一系列问题之一（未指定算法，但可以通过“srand”初始化以实现可重复性；非线程安全；未指定分布；历史实现具有较弱的低位；等等）。

有关在给定范围内生成均匀随机_浮点数_的算法，请参见“适用于浮点数格式”。浮点数生成存在许多整数生成所没有的问题。例如，任何计算机都无法从两个数字之间的所有实数中进行选择，因为它们是无限的；此外，简单地将整数乘以或除以一个常数（例如，JavaScript 中的 `Math.random()*x`）必然会遗漏许多可表示的浮点数（详情请参见 Goualard 2020(2)）。

选择随机项目

通常，从列表中选择一个随机项目很简单：在 `[0, n)` 中选择一个随机整数，其中 `n` 是列表的大小，然后选择该位置的项目。上一节已经讨论了如何生成随机整数。

但是，如果项目数量事先未知，则可以使用一种称为_水塘抽样_的技术来随机选择一个或多个项目。以下是水塘抽样的实现方法。

  1. 将 N 设置为 1。
  2. 如果没有剩余的项目，则返回最后选择的项目。否则，选择下一个项目，并以 1/N 的概率选择它。
  3. 将 N 加 1，然后转到步骤 2。

有关水塘抽样算法，请参见“随机抽样的伪代码”。

唯一整数或项目

生成唯一的随机整数或项目也称为_不放回_、_不重复_或_无重复_抽样。

生成唯一项目的方法有很多种，具体取决于要选择的项目的数量、要从中选择的项目的数量等等，它们在时间开销和内存需求方面有不同的权衡。有关建议，请参阅“不放回抽样：选择几个唯一项目”。

某些应用程序需要生成唯一值来标识某些内容，例如数据库记录、用户帐户等。但是，为此目的生成唯一值时需要注意某些事项；有关更多信息，请参见“唯一随机标识符”。

洗牌

在“洗牌”中给出了对列表进行随机化（_洗牌_）顺序的算法。需要注意的是，该算法很容易实现错误。此外，在洗牌时，随机数生成器的选择也很重要；请参阅我的关于洗牌的RNG推荐文档。

来自数据库的随机记录

从数据库中查询随机记录（_行_）通常涉及数据库语言 SQL。然而，SQL 在不同的数据库管理系统（DBMS）中实际实现方式大相径庭，以至于即使是微不足道的 SQL 语句也不能保证在不同的 DBMS 中以相同的方式工作。此外，SQL 没有循环、没有分支，也没有标准的随机数生成方法。因此，从数据库中查询随机记录的正确方法将因 DBMS 而异。

话虽如此，以下特定情况往往会在随机记录查询中出现。

  • 从数据库中查询一条随机记录。
  • 从数据库中查询指定数量的随机记录。
  • 查询一个或多个记录，每个记录的概率与其权重成比例。通常，可以通过向表中添加一列，其中每个条目按如下方式生成：`ln(R) / W`（其中 `W` 是记录的权重，大于 0，本身是它自己的一列，`R` 是每条记录在 (0, 1) 中的均匀随机数）（另请参阅 (Arratia 2002)(3)），然后选择该列值最高的记录，但此技术的效率取决于 DBMS。

随机字符字符串

许多应用程序需要生成一个随机字符串，其字符选自受限字符集。流行的选择包括所谓的_字母数字字符串_，其中受限字符集是A到Z、a到z、0到9。生成随机字符串的算法在“随机字符字符串”中给出。

然而，以下是涉及随机字符串生成的许多考虑因素中的一些：

  • 如果字符串需要由最终用户输入，或者需要易于记忆，那么仔细选择字符集或允许检测输入错误可能很重要。
  • 如果字符串标识某物，应用程序可能要求其生成的字符串是唯一的；请参阅唯一随机标识符以获取注意事项。
  • 如果字符串是任何类型的秘密值，包括密码、持有者凭证、会话标识符、随机数、“确认码”、“验证码”或“忘记密码”码，则必须使用密码学RNG（例如Python中的`secrets`模块或PHP中的`random_bytes`函数）生成该字符串。

以不同概率选择项目

_加权选择_（也称为_分类分布_）是一种随机选择项目的方式，其中每个项目都有一个_权重_，并以与其权重成比例的概率被选中。

有关加权选择的算法，请参见“带放回的加权选择”，其中涵盖了项目被取出并放回的选择。

其中显示的伪代码是实现加权选择的直接方法，但还有其他替代方案（其中许多在Python示例代码中实现）。它们包括拒绝采样、Vose的别名方法版本（`VoseAlias`；有关更多信息，请参阅Keith Schwarz的“飞镖、骰子和硬币：从离散分布中采样”），以及快速加载骰子滚轮（`FastLoadedDiceRoller`）（Saad等人，2020）(4)。

_不放回加权选择_是指每个项目最多只能被选择一次的选择。如果权重具有以下特性：权重较高的项目更有可能首先出现，那么：

然而，这些方法不一定能确保_n_个项目的随机样本将以与该项目权重成比例的概率包含给定项目。这是一个类似的问题，但这些方法无法解决；对于该问题，请参阅“等概率或不等概率抽样算法”。

请注意，以给定概率选择_真_，否则选择_假_，是加权抽样的一种特殊情况，涉及两个项目（也称为_伯努利试验_）。但是，有更简单的方法以这种方式选择_真_或_假_；请参见“布尔（真/假）条件”。也许最实用的是惯用语 `RNDINTEXC(Y) < X`，它以 `X/Y` 的概率选择_真_，否则选择_假_。

其他主题

分析中还出现了其他主题，值得在此提及。这些主题包括：

注释

© . All rights reserved.