采样问题经常会被遇到，比如：
从 100000 份调查报告中抽取 1000 份进行统计。从一本很厚的电话簿中抽取 1000 人进行姓氏统计。从 Google 搜索 “Ken Thompson”，从中抽取 100 个结果查看哪些是今年的。 这些都是很基本的采用问题。既然说到采样问题，最重要的就是做到公平，也就是保证每个元素被采样到的概率是相同的。所以可以想到要想实现这样的算法，就需要掷骰子，也就是随机数算法。（这里就不具体讨论随机数算法了，假定我们有了一套很成熟的随机数算法了）
对于第一个问题，还是比较简单，通过算法生成 [0,100000−1) 间的随机数 1000 个，并且保证不重复即可。再取出对应的元素即可。
但是对于第二和第三个问题，就有些不同了，我们不知道数据的整体规模有多大。可能有人会想到，我可以先对数据进行一次遍历，计算出数据的数量 N，然后再按照上述的方法进行采样即可。这当然可以，但是并不好，毕竟这可能需要花上很多时间。也可以尝试估算数据的规模，但是这样得到的采样数据分布可能并不平均。
终于要讲到蓄水池采样算法（Reservoir Sampling）了。先说一下算法的过程：
假设数据序列的规模为 n，需要采样的数量的为 k。
首先构建一个可容纳 k 个元素的数组，将序列的前 k 个元素放入数组中。
然后从第 k+1 个元素开始，以 n k \frac{n}{k} kn 的概率来决定该元素是否被替换到数组中（数组中的元素被替换的概率是相同的）。 当遍历完所有元素之后，数组中剩下的元素即为所需采取的样本。
对于第 i 个数（i≤k）。在 k 步之前，被选中的概率为 1。当走到第 k+1 步时，被 k+1 个元素替换的概率 = k+1 个元素被选中的概率 * i 被选中替换的概率，即为 k k + 1 \frac{k}{k+1} k+1k× 1 k \frac{1}{k} k1= 1 k + 1 \frac{1}{k+1} k+11。则被保留的概率为 1− 1 k + 1 \frac{1}{k+1} k+11= k k + 1 \frac{k}{k+1} k+1k。依次类推，不被 k+2 个元素替换的概率为 1− k k + 2 \frac{k}{k+2} k+2k× 1 k \frac{1}{k} k1 = k + 1 k + 2 \frac{k+1}{k+2} k+2k+1 。则运行到第 n 步时，被保留的概率 = 被选中的概率 * 不被替换的概率，即：
1 × k k + 1 × k + 1 k + 2 × k + 2 k + 3 × … × n − 1 n = k n 1×\frac{k}{k+1}× \frac{k+1}{k+2}× \frac{k+2}{k+3}×…× \frac{n-1}{n}=\frac{k}{n} 1×k+1k×k+2k+1×k+3k+2×…×nn−1=nk
对于第 j 个数（j>k）。在第 j 步被选中的概率为 k j \frac{k}{j} jk。不被 j+1 个元素替换的概率为 1− k j + 1 \frac{k}{j+1} j+1k × 1 k \frac{1}{k} k1= j j + 1 \frac{j}{j+1} j+1j。则运行到第 n 步时，被保留的概率 = 被选中的概率 * 不被替换的概率，即： k j × j j + 1 × j + 1 j + 2 × j + 2 j + 3 × . . . × n − 1 n = n k \frac{k}{j} × \frac{j}{j+1}×\frac{j+1}{j+2}×\frac{j+2}{j+3}×...×\frac{n-1}{n}= \frac{n}{k} jk×j+1j×j+2j+1×j+3j+2×...×nn−1=kn 所以对于其中每个元素，被保留的概率都为 n k \frac{n}{k} kn .
贴出测试用的示例代码（Java 实现）：
public class ReservoirSamplingTest { private int[] pool; // 所有数据 private final int N = 100000; // 数据规模 private Random random = new Random(); @Before public void setUp() throws Exception { // 初始化 pool = new int[N]; for (int i = 0; i < N; i++) { pool[i] = i; } } private int[] sampling(int K) { int[] result = new int[K]; for (int i = 0; i < K; i++) { // 前 K 个元素直接放入数组中 result[i] = pool[i]; } for (int i = K; i < N; i++) { // K + 1 个元素开始进行概率采样 int r = random.nextInt(i + 1); if (r < K) { result[r] = pool[i]; } } return result; } @Test public void test() throws Exception { for (int i : sampling(100)) { System.out.println(i); } } }结果就不贴出来了，毕竟每次运行结果都不一样。
蓄水池算法适用于对一个不清楚规模的数据集进行采样。以前在某个地方看到过一个面试题，说是从一个字符流中进行采样，最后保留 10 个字符，而并不知道这个流什么时候结束，且须保证每个字符被采样到的几率相同。用的就是这个算法。
在高德纳的 TAOCP 中有对于这个算法的描述，可以说这是个很精巧的算法。在看到这个算法实现前，很难想到可以通过这样的一种方式进行采样。
