蓄水池抽样

Author Avatar
noir 10月 08, 2020

场景简述

当我们需要对一个非常大的数据集合进行抽样时，我们不可能降数据完全捞取到内存里，这就导致我们需要使用流处理来进行抽样。而一个很长的N的流，在处理完成前都不知道N的大小，那如何在时间复杂度O(N)的情况下进行抽样呢？

算法思路

我们假设先有nums[N], N=3，需要取其中1个值：

  • 假定第一位数被抽中的概率为 1 / 0 + 1, 有 pick = random() % 1 ? nums[0] : pick;，可知此时pick命中nums[0]
  • 第二位数被抽取中的概率为 1 / 1 + 1，有pick = random() % 2 ? nums[1] : pick，此时pick有1/2概率命中nums[1]
  • 第三位数被抽中的概率为 1 / 2 + 1，有pick = random() % 3 ? nums[2] : pick，此时pick有1/3的概率命中nums[2]

通过上述三个步骤后，我们计算下命中第n个数的概率Pn:

  • P1：1 * 1/2 * 2/3 = 1/3
  • P2: 1/2 * 2/3 = 1/3
  • P3: 1/3

其实很简单可以分析出使用此类方式命中Pn有：

1
2
3
  Pn = 1 / n * n / (n + 1) * (n + 1) / (n + 2) ...... * (N - 1) / N

=> Pn = 1 / N

做题

老规矩，做题：