蓄水池抽样

从N个元素中随机的等概率的抽取m个元素，其中N无法确定（数据流的形式）。

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

// init for (int i = 0; i < reservoir.length; i++) { reservoir[i] = dataStream[i]; }

for (int i = m; i < dataStream.length; i++) { // 随机获得一个[0, i]内的随机整数 int d = rand.nextInt(i + 1); // 如果随机整数落在[0, m-1]范围内，则替换蓄水池中的元素 if (d < m) { reservoir[d] = dataStream[i]; } } ```

  • 算法思路:
  1. 如果接收的数据量小于m，则依次放入蓄水池。
  2. 当接收到第i个数据时，i >= m，在[0, i]范围内取以随机数d，若d的落在[0, m-1]范围内，则用接收到的第i个数据替换蓄水池中的第d个数据。
  3. 重复步骤2。

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

  • 证明：
  1. 当i <= m时，将其放入蓄水池
  2. 当i>m的时候，从[1, i]中取随机数d，如果d<=m，则用第i个数代替第d个数据
  3. 当i>m的时候，以m+1为例，m+1，会以(m/m+1)的概率进入蓄水池，第m+1次处理替换掉小于等于m的某个数的概率是(m/(m+1)) x (1/m)=(1/(m+1))，不替换小于等于m的某个数的概率是(m/m+1)（即1-1/(m+1) )，第m+2个数不替换掉池中某个数的概率为((m+1)/(m+2))…..第N个数不替换掉池中某个数的概率为（(N-1)/N）
  4. i<=m的这些数一直留在蓄水池的概率是(m/m+1) x (m+1/m+2) … x (N-1/N) = m/N。（即从第m+1个数开始，一直到第N个数，都不替换池中的数）。
  5. 对于i>m的这些数进入蓄水池的概率是m/i，而之后一直留在蓄水池的概率是(m/i) x (i/i+1) … x (N-1/N) = m/N。
    1. 进入蓄水池的概率即随机数d落到小于等于m的区间。一直留在蓄水池的概率即从第i+1个数开始一直到N，都不会替换已经进入池中的i。为什么从第i+1数开始，因为i>m时，后面的数才可能替换i。

image.png