【算法】概率问题

发表于2021-12-15更新于2021-12-20字数统计1.6k阅读时长9分阅读次数

概率问题常见题目

蓄水池抽样算法（Reservoir Sampling）

https://www.jianshu.com/p/7a9ea6ece2af

给定一个数据流，数据流长度 N 很大，且 N 直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出 m 个不重复的数据。

这个场景强调了3件事：

  1. 数据流长度N很大且不可知，所以不能一次性存入内存。
  2. 时间复杂度为 O(N)。
  3. 随机选取 m 个数，每个数被选中的概率为 m/N。

第 1 点限制了不能直接取 N 内的 m 个随机数，然后按索引取出数据。第 2 点限制了不能先遍历一遍，然后分块存储数据，再随机选取。第 3 点是数据选取绝对随机的保证。

算法思路：

  1. 如果接收的数据量小于 m，则依次放入蓄水池。
  2. 当接收到第 i 个数据时，i >= m，则使得其以 m / i 的概率进入蓄水池，同时从蓄水池中不放回地随机选出一个元素将其弹出（1 / m 的概率）。具体做法为：在 [0, i] 范围内取随机数 d，若 d 落在 [0, m-1] 范围内，则用接收到的第 i 个数据替换蓄水池中的第 d 个数据。
  3. 重复步骤2。

算法的精妙之处在于：当处理完所有的数据时，蓄水池中的每个数据都是以 m/N 的概率获得的。

应用

蓄水池算法的 O(N) 时间复杂度，O(m) 空间复杂度令其适用于对流数据、大数据集的等概率抽样。比如一个大文本数据，随机输出其中的几行；抽奖系统，等概率抽取每个第一次登录的用户。使用该算法可以以很低的空间复杂度处理随机问题。

分布式蓄水池抽样（Distributed/Parallel Reservoir Sampling）

一块 CPU 的计算能力再强，也总有内存和磁盘 IO 拖他的后腿。因此为提高数据吞吐量，分布式的硬件搭配软件是现在的主流。

如果遇到超大的数据量，即使是 O(N) 的时间复杂度，蓄水池抽样程序完成抽样任务也将耗时很久。因此分布式的蓄水池抽样算法应运而生。运作原理如下：

  1. 假设有 K 台机器，将大数据集分成 K 个数据流，每台机器使用单机版蓄水池抽样处理一个数据流，抽样m个数据，并最后记录处理的数据量为N1, N2, …, Nk, …, NK(假设m < Nk)。N1 + N2 + … + NK = N。
  2. 取 [1, N] 一个随机数 d，若 d < N1，则在第一台机器的蓄水池中等概率不放回地（1 / m）选取一个数据；若 N1 <= d < (N1 + N2)，则在第二台机器的蓄水池中等概率不放回地选取一个数据；一次类推，重复 m 次，则最终从 N 大数据集中选出 m 个数据。

m/N 的概率验证如下：

  1. 第 k 台机器中的蓄水池数据被选取的概率为 m / Nk。
  2. 从第 k 台机器的蓄水池中选取一个数据放进最终蓄水池的概率为 Nk / N。
  3. 第 k 台机器蓄水池的一个数据被选中的概率为 1 / m。（不放回选取时等概率的）
  4. 重复 m 次选取，则每个数据被选中的概率为 m*(m/Nk*Nk/N*1/m)=m/N。

随机数生成器

问题：已知有一个随机数生成器，可以等概率生成 1 - 7 范围的整数。如何在不借助系统随机方法的前提下，将该随机数生成器包装成：等概率生成 20 - 30 范围的整数。

思路：将随机数生成器生成的数字转换成二进制的 0 或 1：

  • 判断随机数生成器生成的数字：
    • 如果处于 [1, 3] 范围，则转换成 0
    • 如果处于 [4, 6] 范围，则转换成 1
    • 如果等于 7，则重新再生成一数直到落在 [0, 6] 范围
  • 将要转换成的数字范围进行标准化：[20, 30] -> [0, 10]，之后只需要做到随即生成 [0, 10] 范围内的数字即可通过 +20 的方式得到目标范围
  • 标准化后要转换成的数字最大为 10，该数字最少可以用 4 位二进制数表示，则进行 4 次上述过程，随机生成四个 0 或 1。将这四个 0 或 1 组成一个数字：
    • 若该数字不在 [0, 10] 内，则重复该过程，重新生成 4 个 0 或 1
    • 若该数字在 [0, 10] 内，则该数字 + 20 就是我们自定义的生成器所返回的数字

使用该机制即可将任意范围的整数转换成另外一个范围的整数。

扩展

如果随机生成器只生成 0 或 1，但是二者的概率不同。以 p 的概率生成 0，以 1 - p 的概率生成 1。则如何将该随机生成器包装成能等概率返回 0 和 1。

思路：调用两次该生成器，生成结果有：

  • 00：概率为 p*p。舍弃不要，重新调用两次
  • 01：概率为 p*(1-p)。返回 0
  • 10：概率为 (1-p)*p。返回 1
  • 11：概率为 (1-p)*(1-p)。舍弃不要，重新调用两次

只在返回 01 和 10 时生成出 0 和 1，即可做到等概率生成 0 和 1。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Rand5ToRand7 {
    public static int rand1To5() {
        // 随机生成 0-4 + 1 = 0-5 的数字
        return (int)(Math.random() * 5) + 1;
    }

    // f() 方法用于随机生成0或1
    public static int f() {
        int num = 0;
        do {
            // 随机生成1-5范围, 如果为3, 重新生成
            num = rand1To5();
        } while (num == 3);
        //
        return num < 3 ? 0 : 1;
    }

    public static int rand1To7() {
        // 先用 f() 随机生成 0-6 范围的数字, 然后加一生成 1-7 范围
        // 随机生成三次0或1, 拼接起来如果大于6则重新生成三次
        int res = 0;
        do {
            res = (f() << 2) + (f() << 1) + f();
        } while (res > 6);
        return res + 1;
    }
}