水塘抽样算法

目的

水塘抽样的目标是从一个很大的或未知大小的数据集中随机选取k个样本。

特点：不要求一次性读取所有数据，也不需要知道数据总量，能保证每个元素被选中的概率相等

算法步骤

1. 初始化样本池：先将流中的前k个元素放入样本池。

2. 迭代处理元素：对于第i个新元素，以k/i的概率决定是否将其替换进样本池。

3. 选择替换的元素：如果新元素需要被替换进样本池，随机选择样本池中的一个元素进行替换。

证明过程

1. 前k个元素被放入样本池

2. 第k+1个元素被选中替换的概率是k / (k + 1)

3. 此时样本池中的1-k个元素保留的概率：(1 - k / (k + 1)) + (k / (k + 1) * (k - 1) / k) = k / (k + 1)，即 没中k+1的概率 + 选中k+1但没被替换的概率

4. 从而到k+1时，所有元素保留在样本池中等概率

代码实现

function getRandomInt(max) {
  return Math.floor(Math.random() * max);
}

function reservoir_sampling(data, k) {
  const reservoir = [];
  for (let i = 0; i < k; i++) {
    reservoir.push(data[i]);
  }

  for (let i = k; i < data.length; i++) {
    const j = getRandomInt(i);
    if (j < k) {
      reservoir[j] = data[i];
    }
  }

  return reservoir;
}