問題描述

給出一個數(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ù)學歸納法證明

假設(shè)i=n時，前k個元素都以k/n被選中；
那么當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;
    }