为什么维基百科中的Reservoir Sampling页面说列表的大小未知，但源代码函数知道大小？

Question

维基百科上的储层采样：https://en.wikipedia.org/wiki/Reservoir_sampling

储库抽样是一系列随机算法，用于从未知大小 n 的总体中选择一个简单的随机样本，无需放回，单次遍历项目。 算法不知道总体 n 的大小，并且通常太大，无法将所有 n 个项目放入主内存中。 随着时间的推移，算法会向算法显示总体，并且算法无法回顾以前的项目。在任何时候，算法的当前状态必须允许提取简单的随机样本，而无需替换迄今为止所看到的总体部分的大小 k。

为什么说算法不知道总体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]
  end

  // replace elements with gradually decreasing probability
  for i := k+1 to n
    (* randomInteger(a, b) generates a uniform integer from the inclusive range {a, ..., b} *)
    j := randomInteger(1, i)
    if j <= k
        R[j] := S[i]
    end
  end
end

Answer 1

您写道：“它实际上将列表长度作为输入”

事实并非如此

在

ReservoirSample(S[1..n], R[1..k])

n 是输出的样本数，k 是前 k 个输入（即不是所有输入）