蓄水池算法的分析与python实现

Contents
  1. 题目描述
  2. 题目分析
  3. 题目解法
  4. Python实现

题目描述

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

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

题目分析

这个问题的难点就在于你开始不知道有多少的整数,也就是说这个(1/n)不知道n是多少。这里我们要使用蓄水池抽样算法

题目解法

首先我们取到第一个数(暂时取的最后要不要还不一定呢),然后对第二个数以1/2的概率来确定用第二个数来替换他,然后对第二个数以1/3的概率来确定是否用第三个数来替换他。。。。一直这样下去直到第n个数。
经过上面的这个过程我们发现每个数取到的概率都变成了(1/n)。证明如下:

1_to_n

总结起来就是一句话每个数取到的概率等于取到该数且取不到该数后面所有数的概率

现在我们回到较复杂的情况,也就是如何在一个N个数(开始不知道N是几)中随机取M个数。其实思想是一样的,就是先取出前M个,然后对后面的开始每个以(k/i)的概率进行替换,这样我们得到的就是所要的结果,证明如下:

k_to_n

Python实现

下面是蓄水池算法的Python实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import random
import copy
def reservoirSampling(seq, k):
localSeq = copy.deepcopy(seq)
N = len(localSeq)
for i in xrange(k, N):
M = int(random.uniform(0, i))
if M < k:
tmp = copy.deepcopy(localSeq[M])
localSeq[M] = copy.deepcopy(localSeq[i])
localSeq[i] = tmp
return localSeq[0:k]
def main():
a = [4,5,6,3,4,7,7,4,3,3,2,4,5,5,6,9,5,4,3,45,3,23,44,55,33,5,8]
k = 5
print reservoirSampling(a, k)
if __name__ == "__main__":
main()