蓄水池抽样：只看一遍，也能公平地抽一个
有些数据不是整整齐齐放在桌上的。比如一条日志流、一个不断刷新的用户列表、一个你根本不知道长度的文件。你不能先数完它有多少项，也不能把它全部塞进内存再慢慢挑。问题来了：如果只能从头到尾看一遍，怎么从里面随机选出一个，并且保证每个元素被选中的机会一样？
蓄水池抽样的想法很硬。看到第 1 个元素时，先选它。看到第 2 个元素时，用 1/2 的概率替换掉当前选择。看到第 3 个元素时，用 1/3 的概率替换。看到第 n 个元素时，就用 1/n 的概率替换。最后留下来的那个，就是公平样本。
这听起来像碰运气，但它不是玄学。第 1 个元素一开始被选中，之后要一路不被第 2、3、4……n 个元素替换掉，概率是 1 × 1/2 × 2/3 × 3/4 × ... × (n-1)/n，最后正好是 1/n。第 k 个元素被选中的概率是 1/k，之后不被替换的概率是 k/(k+1) × ... × (n-1)/n，乘起来也正好是 1/n。
它的好处不是“看起来聪明”，而是现实里真的有用：数据很大、长度未知、只能流式读取时，它用 O(1) 内存解决了公平抽样。没有临时数组，没有回退逻辑，也不需要假装自己能掌控整条数据流。
难点在这里：
#CS
有些数据不是整整齐齐放在桌上的。比如一条日志流、一个不断刷新的用户列表、一个你根本不知道长度的文件。你不能先数完它有多少项，也不能把它全部塞进内存再慢慢挑。问题来了：如果只能从头到尾看一遍，怎么从里面随机选出一个，并且保证每个元素被选中的机会一样？
蓄水池抽样的想法很硬。看到第 1 个元素时，先选它。看到第 2 个元素时，用 1/2 的概率替换掉当前选择。看到第 3 个元素时，用 1/3 的概率替换。看到第 n 个元素时，就用 1/n 的概率替换。最后留下来的那个，就是公平样本。
这听起来像碰运气，但它不是玄学。第 1 个元素一开始被选中，之后要一路不被第 2、3、4……n 个元素替换掉，概率是 1 × 1/2 × 2/3 × 3/4 × ... × (n-1)/n，最后正好是 1/n。第 k 个元素被选中的概率是 1/k，之后不被替换的概率是 k/(k+1) × ... × (n-1)/n，乘起来也正好是 1/n。
它的好处不是“看起来聪明”，而是现实里真的有用：数据很大、长度未知、只能流式读取时，它用 O(1) 内存解决了公平抽样。没有临时数组，没有回退逻辑，也不需要假装自己能掌控整条数据流。
难点在这里：
#CS
