問題描述：
給你一個(gè)長度為N的鏈表金踪。N很大，但你不知道N有多大。你的任務(wù)是從這N個(gè)元素中隨機(jī)取出k個(gè)元素匿又。你只能遍歷這個(gè)鏈表一次挽唉。你的算法必須保證取出的元素恰好有k個(gè)，且它們是完全隨機(jī)的（出現(xiàn)概率均等）定踱。
該算法是針對從一個(gè)序列中隨機(jī)抽取不重復(fù)的k個(gè)數(shù)棍潘，保證每個(gè)數(shù)被抽取到的概率為k/n這個(gè)問題而構(gòu)建的。做法是：
- 首先構(gòu)建一個(gè)可放k個(gè)元素的蓄水池崖媚，將序列的前k個(gè)元素放入蓄水池中亦歉。
- 然后從第k+1個(gè)元素開始，以k/n的概率來決定該元素是否被替換到池子中至扰。 當(dāng)遍歷完所有元素之后鳍徽，就可以得到隨機(jī)挑選出的k個(gè)元素。復(fù)雜度為O(n).
偽代碼：
Init : a reservoir with the size： k
for i= k+1 to N
M=random(1, i);
if( M < k)
SWAP the Mth value and ith value
end for
證明每個(gè)數(shù)被取到的概率為k/n:
蓄水池算法證明
代碼：
import time
import random
import copy
def reservoirSampling(seq, k):
localSeq = copy.deepcopy(seq)
N = len(localSeq)
for i in range(k, N, 1):
M = int(random.uniform(0, i))
if M < k :
temp = copy.deepcopy(localSeq[M])
localSeq[M] = copy.deepcopy(localSeq[i])
localSeq[i] = temp
return localSeq[0:k]
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)
import random
def sample(iterable, n):
"""
Returns @param n random items from @param iterable.
"""
reservoir = []
for t, item in enumerate(iterable):
if t < n:
reservoir.append(item)
else:
m = random.randint(0,t)
if m < n:
reservoir[m] = item
return reservoir
轉(zhuǎn)自鏈接：http://www.reibang.com/p/858cd54238b2
