蓄水池抽样算法

给定一个数据流，数据流长度N很大，不能一次性保存在内存中，且N直到所有数据处理完都不可知，请问如何能在遍历一遍数据O(N)的情况下，能够随机取出m个不重复的数据
思路：

  1. 当接受的数据量小于m，则依次放入蓄水池当中。
  2. 当接收到第i个数据时，i >= m，在[0, i]范围内取以随机数d，若d的落在[0, m-1]范围内，则用接收到的第i个数据替换蓄水池中的第d个数据。

第i个接收到的数据最后能够留在蓄水池中的概率=第i个数据进入过蓄水池的概率*之后第i个数据不被替换的概率**（第i+1到第N次处理数据都不会被替换）。

  1. i <= m, 进入蓄水池的概率为1，第m+1次操作，替换掉第i个数据的概率为1/(m+1)，不被替换掉第i个数据的概率为m/(m+1)。所以N次处理后第i个数据仍在蓄水池中的概率为=m/(m+1) * (m+1)/(m+2)…(N-1)/N = m/N

  2. i > m, 第i个数据进入蓄水池的概率为m/i，第i个数据不被替换的概率=i/N，所以能留在蓄水池的概率为m/N

    分布式蓄水池抽样

    如果遇到超大的数据量，即使O(N)的时间复杂度，抽样任务也将非常耗时。
    而一块CPU的计算能力再强，内存、IO不给力也会影响到性能。分布式是提高吞吐量的一个有效的方案
    原理：

  3. K台机器，将大数据集分成了K个数据流，每台机器使用蓄水池抽样抽取m个数据。

  4. 取一个随机数，落在那个区间，在对应的机器等概率不放回的选取一个数据(1/m)。m次

m (m/NkNk/N*1/m) = m/N