Stream Sampling: 从未知长度的有限流中随机抽样

问题描述：

有一个长度 n 未知的整数流, 我们需要从中随机抽出 k 个整数。假设： n >= k, n 可能非常大

解决方案 1：Algorithm R

(*
  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]

维护一个大小为 k 的数组 R[]。首先利用流的前 k 个元素填充数组。S[i] 表示流中的第 i 个元素。

对于 S[k+1]，我们以 k/(k+1) 的概率保留它，用它随机替换数组中的元素。那么当处理 S[k+1] 后， S[k+1] 被放在数组 R 中某个特定的位置 j 上的概率是 k/(k+1) * 1/k = 1/(k+1)。而原来的 R[j] 被保留的概率是 1 - 1/(k+1) = k/(k+1)。

对于 S[i] (i > k), 我们以 k/i 的概率保留它, 并用它随机替换 R 中的元素。在处理 S[i] 之前，流中前 i-1 个元素每个元素被保留的概率是 k/(i-1)。 S[i] 被放在数组 R 中某个特定的位置 j 上的概率是 k/i * 1/k = 1/i。处理 S[i] 后，原来已在数组 R 中的每一个元素被保留的概率为 1 - 1/i = (i-1)/i。总的来说，此时流中的每个元素被保留的概率是 k/(i-1) * (i-1)/i = k/i。

当处理完所有流中元素时，我们得到了 k 个元素，流中每个元素被保留的在数组 R 中的概率为 k/n。

解决方案 2：Fisher-Yates Shuffle

假设有 n 张纸牌，要从其中随机地抽出 k 张。为了达到目的，我们可以先洗牌，然后取最上面的 k 张。洗牌过程实际上是生成 n 张纸牌的一个随机排列。

Fisher-Yates Shuffle 算法是一个经典的随机排列生成算法。

   R[0] ← S[0] 
   for i from 1 to n - 1 do 
       r ← random (0 .. i) 
       R[i] ← R[r] 
       R[r] ← S[i]

我们需要在未知长度有限流中随机抽样，数据是陆续到达的，我们无法在不存储整个序列的情况下生成这个序列的一个随机排列。事实上，我们只需要随机排列的前 k 个元素，所以我们只需要在 Shuffle 的过程中记录 Shuffle 结果的前 k 个元素就可以了，于是有如下算法：

   R[0] ← S[0] 
   for i from 1 to k - 1 do 
       r ← random (0 .. i) 
       R[i] ← R[r] 
       R[r] ← S[i]  
   for i from k to n - 1 do 
       r ← random (0 .. i) 
       if (r < k) then R[r] ← S[i]

参考：

Wikipedia: Reservior Sampling