## 随机问题 > **问题描述** > > 对于给定的数组 $Q$ ，将其每个元素随机分布在数组中，并且使得之后每个元素被取到的概率相等？ ### Shuffle 算法 #### Code ```java public static void shuffle(int[] q) { for (int i = q.length - 1; i >= 0; i--) swap(q, i, (int) (Math.random() * (i + 1))); } ``` #### 随机性证明 设整个数组长度为 $length$，当前元素下标为 $i\in[0,length-1]$ ，每次从 $[0,i]$ 中选择一个元素进行交换。 在第一次交换中，各个元素被选中的概率为 $\frac{1}{i+1}$ 第二次交换中，任一元素被选中的概率为 $\frac{i}{i+1}*\frac{1}{i}=\frac{1}{i+1}$ 以此类推，各个元素被选中的概率都为 $\frac{1}{i+1}$ ，可得出概率相等 --- > **问题描述** > > 那么现在问题升级了，由于数据集比较大并且在不断增加，我们无法将所有数据全部都放到内存中 > > 那么是否有办法在这个数据流（可设其总数为 $I$ ）中选出一个元素，使得在时间复杂度 $O(N)$ 的情况下，该元素被选中的概率为与其他元素被选中的概率相等？ ### 蓄水池抽样算法 #### Code ```java public class RandomSelect { public static int sampling(int[] q) { int t = 0; for (int i = 1; i <= q.length; i++) { if (Math.random() < 1 / i) t = q[i - 1]; } return t; } } ``` #### 随机性证明 设整个数组元素个数为 $length$，当前元素下标为 $i\in[1,length]$ 。 - 当 $i=1$ 时，必然选择第一个元素。 - 当 $i=2$ 时，选择第一个元素的条件为上次筛选被选中，且本次筛选没有被排除，则有 $1*\frac{1}{2}=\frac{1}{2}$ ， - 当 $i=3$ 时，任然选择第一个元素的概率为 $\frac{1}{2}*(1-\frac{1}{3})=\frac{1}{2}*\frac{2}{3}=\frac{1}{3}$ ， 依此类推，可得选择任一元素（设其下标为 $j$ ）的概率为 $\frac{1}{j}*(1-\frac{1}{j+1})*...*(1-\frac{1}{i-1})*(1-\frac{1}{i})=\frac{1}{i}$ 故该算法可以确保选择出的元素的随机性。 #### 升级 ##### 数组抽样问题 > **问题描述** > > 那么如果要选择出 $K$ 个元素，使得选出的元素在整个数据集（可设其总数为 $I$ ）中出现的概率相等 ###### Code ```java public class RandomSelect { private static final int N = 5; private static final int[] q = new int[N]; private static int ptr = 0; public static int[] sampling(int[] txt, int k) { for (int i = 1; i <= txt.length; i++) { if (i <= k) q[idx++] = txt[i - 1]; else { int j = (int) (Math.random() * i) + 1; if (j < k) q[j - 1] = txt[i - 1]; } } return q; } } ``` ###### 随机性证明 设整个数组非空长度为 $N$，当前元素下标为 $i\in[1,length]$ ，要选择的元素个数为 $K$ ，随机数的值为 $R$ - **当 $i\le K$ 时**，每个元素被选中进入数组的概率为 $1$ 。 - **当 $i>K$ 时** 1. 当 $i=K+1$ 时，第 $i$ 个元素被选中进入数组的前提为**随机数的值** $R\in[0,K]$ ，则概率为 $\frac{K}{K+1}*\frac{1}{K}=\frac{1}{K+1}$ ，不进入数组的概率则为 $1-\frac{1}{K+1}=\frac{K}{K+1}$ 2. 由此可得，当 $i=N$ 时，第 $i$ 个元素进入数组的概率为 $\frac{K}{N}*\frac{1}{K}=\frac{1}{N}$，同时不进入数组的概率为 $\frac{N-1}{N}$ 故数组中的每个元素数据不被替换的概率为 $\frac{K}{K+1}*\frac{K+1}{K+2}*...*\frac{N-1}{N}=\frac{K}{N}$ ##### 分布式抽样问题 > **问题描述** > > 当数据量规模十分巨大时，单机的内存访问，磁盘 I/O，CPU 频率就会成为数据吞吐量的瓶颈，此时常常采用分布式的结构来分担数据压力，提高吞吐量。 > > 那么如果使用分布式的方式，又要如何保证均匀的取样呢？ ###### 算法过程 > 设分布式架构下有 $N$ 台机器，处理的总数据量为 $S$，取样值为 $M$ 1. 将整个数据流分为 $N$ 个子流，分布到所有机器上，处理的数据量记为 $N_{1},N_{2},N_{3},...,N_{N}$（同时记 $N_0=0$），同时每台机器都运行一个蓄水池抽样模型，取得 $M$ 个数据 2. 生成一个随机数 $R\in[1, S]$，如果 $R\in[\sum{N_0+N_1+...+N_{i-1}},\sum{N_0+N_1+...+N_{i-1}}+N_i]$，则从 $N_i$ 的取样中再次取样加入到最终取样中 3. 循环第 2 步 $M$ 次 ###### 随机性证明 1. 在第 $K$ 台机器上取样值的概率为 $\frac{M}{N_K}$ 2. 随机数取值在第 $K$ 个区间的概率为 $\frac{N_K}{S}$ 3. 在第 $K$ 个取样值中随机取样取到任意元素的概率为 $\frac{1}{M}$，循环取值 $M$ 次 故最后的取样值 $M$ 相对于总数据流数量 $S$ 的概率为 $\frac{M}{N_K}*\frac{N_K}{S}*\frac{1}{M}*M=\frac{M}{S}$，故可以确保随机取样。 ### RandN 生成 RandM > **问题描述** > > 现在提供一个函数 $RandN$ ，它可以提供 $1\sim N$ 的随机数生成，那么如何使用其生成函数 $RandM$，定义同上 #### Code ```java // API randN() is already defined. public class Solution { // If N is greater than M. public int randM() { int res = randN(); while (res > N) res = randM(); return res; } // If N is less than M, and N is odd. public void randM() { int a = randN(), b = randN(); while (a == N) a = randN(); while (b > (M - N + 1)) b = randN(); return ((a & 1) == 0 ? 0 : N - 1) + b; } // If N is less than M, and M is less than N^2. public void randM() { int res = randN() * N + randN() - (N + 1); while (res > (N * N) / M * M) res = randN() * N + randN() - (N + 1); // goto 6: return res % M + 1; } } ``` #### 随机性证明 - 当 $M$ 小于 $N$ 时 - 已知 $randN$ 可以生成 $1\sim N$，如果舍弃大于 M 的部分，则对于 $1\sim M$ 来说必然也是等概率的 - 当 $M$ 大于 $N$ 时 - 若 $N$ 为奇数，则取 $a = 1\sim (N - 1)$ 的部分，数量和为偶数，故 $a$ 获得奇数偶数的概率相等，则将奇数与偶数之一映射为 $0 \space or\space (N - 1)$。(其实映射成多少都没问题，只要等概率，同时和为 $M$) 取 $b = 1\sim (M - (N - 1))=1\sim(M - N + 1)$，此时要求 $M - N + 1 \le N$，则 $b+a=(0\space or\space (N - 1))+(1\sim (M-N+1))=1\sim M$ - 通法。 生成 $0\sim N^2-1$ 之间的随机数，再舍去大于 $\frac{N^{2}}{M}*M$ 的部分并取余，即可将 $0\sim \frac{N^{2}}{M}*M$ 映射为 $0\sim M - 1$，再对其进行 $+1$ 操作即可 ## Top K 问题 > **问题描述** > > 在一个数据集中，选择出第 $K$ 大的元素 ### 快速排序 可以将所有数据读取到内存中排序并取下标取值 #### Code ```java public class TopK { public static int get(int[] q, int k) { sort(q, 0, q.length - 1); retunr q[k - 1]; } private static void sort(int[] q, int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1, k = q[l + r >> 1]; while (i < j) { do i++; while (q[i] < k); do j--; while (q[j] > k); if (i < j) swap(q, i, j); } sort(q, l, j); sort(q, j + 1, r); } } ``` #### 时间复杂度 由于每一次调用函数都遍历了整个数组，同时每一次递归调用都会将数组二分，直到区间中只有一个元素 故时间复杂度为 $O(N*logN)$ 即 $O(NlogN)$ ### 堆排序 将所有数据依次读取到堆中，同时维持堆大小为 $K$ #### Code ```java public class TopK { private static final PriorityQueue<Integer> que = new PriorityQueue<>(); public static void get(int[] q, int k) { for (var i : q) { if (que.size() < k) que.add(i); else if (que.peek() < i) { que.poll(); que.add(i); } } return que.peek(); } } ``` #### 时间复杂度分析 首先需要遍历整个数据集，同时堆进行大小为 $K$ 排序（底层为树的排序，故时间复杂度 $logK$），故时间复杂度为 $O(NlogK)$ ### 快速选择算法 快排思想 + 二分思想，每次选取一半的区间（注意：在使用时需要将 t 的值赋 成 t - 1） #### Code ```java public class TopK { public static int quickSelect(int[] q, int l, int r, int t) { if (l == r) return q[k]; int i = l - 1, j = r + 1, k = q[l + r >> 1]; while (i < r) { do i++; while (q[i] < k); do j--; while (q[j] > k); if (i < j) swap(q, i, j); } if (k <= j) return quickSelect(q, l, j, k); else return quickSelect(q, j + 1, r, k); } } ``` #### 时间复杂度分析 第一次遍历整个数组 $N$ ，第二次遍历选择出的数组的一半，期望值为 $O(\frac{N}{2})$ ··· 由极限收敛可得，时间复杂度为 $O(\sum{N +\frac{N}{2}+\frac{N}{4}+...})=O(N *\sum{1+\frac{1}{2}+\frac{1}{4}+...})=O(2N)=O(N)$ ## 参考 - [蓄水池抽样算法（Reservoir Sampling）](https://www.jianshu.com/p/7a9ea6ece2af) - [【经典算法题】蓄水池抽样算法](https://www.bilibili.com/video/BV17i4y1j7wE)