問題描述
給出一個數(shù)據(jù)流丐膝，這個數(shù)據(jù)流的長度很大或者未知（內(nèi)存無法一次性容納下），并且對該數(shù)據(jù)流中數(shù)據(jù)只能訪問一次钾菊。
簡而言之：要求從N個元素中隨機的抽取k個元素帅矗，其中N的大小未知，k >= 1煞烫。
請寫出一個隨機選擇算法浑此，使得數(shù)據(jù)流中所有數(shù)據(jù)被選中的概率相等。
算法思路
先初始化一個集合滞详，集合中有k個元素凛俱，將此集合作為蓄水池（reservoir）喘落，然后從第k+1個元素開始遍歷，并且按一定的概率替換掉蓄水池里面的元素最冰。
《The Art of Computer Programming》中的偽代碼
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
先將前k個數(shù)取出來放入蓄水池中，然后從第k+1個數(shù)開始遍歷稀火。假設(shè)遍歷到第i個數(shù)暖哨，以k/i的概率替換掉蓄水池中的某個元素即可。
數(shù)學(xué)歸納法證明
假設(shè)i=n時凰狞，前k個元素都以k/n被選中篇裁；
那么當(dāng)i=n+1是，第n+1個元素被選中的概率為k/n+1赡若；
對于前面的n個元素达布，每個元素被選中的情況分為兩種：
1.前面n次已經(jīng)被選中，第n+1次時逾冬，第n+1個元素沒有被選中黍聂；
2.前面n次已經(jīng)被選中，第n+1次時身腻，第n+1個元素被選中但是沒有將其替換掉;
此時的概率為： k/n×(1?k/n+1)+k/n×(k/n+1×(1?1/k))=k/n+1
由此可見产还，第n+1步也滿足假設(shè)條件，問題得到證明嘀趟。
Java代碼實現(xiàn)
public static List<Integer> reservior(int k){
List<Integer> raw = getRandomList(1, 100000);
List<Integer> res = new ArrayList<Integer>(k);
for(int i = 0; i < k; i++){
res.add(raw.get(i));
}
for(int i = k; i < raw.size(); i++){
int m = rand(0,i);
if(m < k){
swap(res.get(m), raw.get(i));
}
}
return res;
}
private static List<Integer> getRandomList(int start, int end) {
List<Integer> res = new ArrayList<Integer>();
for (int i = start; i <= end; i++) {
res.add(i);
}
for (int i = 0; i < lens; i++) {
int t = rand(i, lens);
swap(res.get(i), res.get(t));
}
return res;
}
