蓄水池算法

2014-08-24

蓄水池算法(Reservoir algorithm)的几种描述:

现在有一组数,不知道这组数的总量有多少,请描述一种算法能够在这组数据中随机抽取k个数,使得每个数被取出来的概率相等。

—— 分割线 ——

给出一个数据流,这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次。请写出一个随机选择算法,使得数据流中所有数据被选中的概率相等。

如果蓄水池内只能放一个数据


  • 数据流中的第1个数据出现,只有1个数据则放入蓄水池的概率是1,即直接放入蓄水池。
  • 数据流中的第2个数据出现,现在已经出现2个数据了,每个数据出现在蓄水池的概率是1/2。我们以1/2的概率将这第2个数据保留(即以1/2的概率将第2个数据放入蓄水池),故对于第1个数据而言,其被保留的可能性是:第1个数据被选中用于被替换的概率*第2个数据未被保留的概率,即1*(1-1/2) = 1/2
  • 数据流的第3个数据出现,现在已经出现3个数据了,每个数据出现在蓄水池的概率是1/3。我们以1/3的概率保留第3个数据,蓄水池有1/2的概率存储第1个数据,故蓄水池保留第1个数据的可能性是第1个数据被选中用于被替换的概率*第3个数据未被保留的概率,即1/2*(1 - 1/3) = 1/3。同理,蓄水池保留第2个数据的可能性也是1/3。

按照上面的思路继续下去,若最终数据流中有N个数据,每个数据存放在蓄水池中的可能性必然是1/N。

这里有一个问题是如何以某一概率来保留某个数据。假如概率是1/3,可以这样实现:

# !/usr/bin/env ruby
# coding: UTF-8

num = Random.rand(1..3)  # 生成不小于1,不大于3的随机整数
if num <=1 
    puts '保留该数据'
else
    puts '不保留该数据'
end

如果蓄水池内能存放多个数据


假设蓄水池能够存放8个数据,如果数据流的总的数据个数不大于8,那么直接将这8个数据放进蓄水池即可。如果数据流中数据总数大于8,那么先把数据流的前8个数据放进蓄水池吧,因为此时前8个数据每一个是以8/8的概率放入蓄水池。然后:

  • 数据流中的第9个数据出现。此时要求从这9个数据中随机拿出8个放入蓄水池,即每个数据以8/9的概率出现在蓄水池中。由于前8个数据已经放入蓄水池中,我们以8/9的概率保留第9个数据(即存放到蓄水池)。若确定第9个数据被保留,则随机的去掉蓄水池中的一个数据,将第9个数据添进去即可。
  • 数据流中的第10个数据出现。我们以8/10的概率保留第10个数据。若确定第10个数据被保留,则随机的去掉蓄水池中的一个数据,将第10个数据添进去即可。

具体证明可见蓄水池抽样算法证明

按照上面的思路继续下去,若最终数据流中有N个数据,每个数据存放在蓄水池中的可能性必然是8/N。

取样问题


无论是从数据流还是从具体的N个元素中随机取出不同的m个元素,都可以使用蓄水池算法。

相关


数据工程师必知算法:蓄水池抽样
蓄水池抽样算法证明

( 完 )