• 从一个很大的源代码中随机选取一行。
• 对一个长度未知的链表随机选取其中的k个节点。

• Keep the first item in memory.
• When the i-th item arrives (for i>1):with probability 1/i, keep the new item (discard the old one)with probability 1-1/i, keep the old item (ignore the new one)

So:

• when there is only one item, it is kept with probability 1;
• when there are 2 items, each of them is kept with probability 1/2;
• when there are 3 items, the third item is kept with probability 1/3, and each of the previous 2 items is also kept with probability (1/2)(1-1/3) = (1/2)(2/3) = 1/3;
• by induction, it is easy to prove that when there are n items, each item is kept with probability 1/n.

/*
S has items to sample, R will contain the result
*/
ReservoirSample(S[1..n], R[1..k])
// fill the reservoir array
for i = 1 to k
R[i] := S[i]

// replace elements with gradually decreasing probability
for i = k+1 to n
j := random(1, i)   // important: inclusive range
if j <= k
R[j] := S[i]