蓄水池抽样算法概述(Reservoir Sampling Algorithm)[转载]

面京东被这个问题卡了QAQ,来补补这方面的课。

转自:链接

蓄水池抽样算法随机算法的一种,用来从 N 个样本中随机选择 K 个样本,其中 N 非常大(以至于 N 个样本不能同时放入内存)或者 N 是一个未知数。其时间复杂度为 O(N),包含下列步骤 (假设有一维数组 S, 长度未知,需要从中随机选择 k 个元素, 数组下标从 1 开始), 伪代码如下:

array R[k];    // result
integer i, j;
1// fill the reservoir array
2for each i in 1 to k do
3    R[i] := S[i]
4done;
1// replace elements with gradually decreasing probability
2for each i in k+1 to length(S) do
3    j := random(1, i);   // important: inclusive range
4    if j <= k then
5        R[j] := S[i]
6    fi
7done

算法首先创建一个长度为 k 的数组(蓄水池)用来存放结果,初始化为 S 的前 k 个元素。然后从 k+1 个元素开始迭代直到数组结束,在 S 的第 i 个元素,算法生成一个随机数 j∈[1,i]j∈[1,i], 如果 j <= k, 那么蓄水池的第 j 个元素被替换为 S 的第 i 个元素。

算法的正确性证明

定理:该算法保证每个元素以 k / n 的概率被选入蓄水池数组。

证明:首先,对于任意的 i,第 i 个元素进入蓄水池的概率为 k / i;而在蓄水池内每个元素被替换的概率为 1 / k; 因此在第 i 轮第j个元素被替换的概率为 (k / i ) * (1 / k) = 1 / i。 接下来用数学归纳法来证明,当循环结束时每个元素进入蓄水池的概率为 k / n.

假设在 (i-1) 次迭代后,任意一个元素进入 蓄水池的概率为 k / (i-1)。有上面的结论,在第 i 次迭代时,该元素被替换的概率为 1 / i, 那么其不被替换的概率则为 1 - 1/i = (i-1)/i;在第i 此迭代后,该元素在蓄水池内的概率为 k / (i-1) * (i-1)/i = k / i. 归纳部分结束。

因此当循环结束时,每个元素进入蓄水池的概率为 k / n. 命题得证。

算法的C++实现

实现部分比较简单,关键点也有详细的注释,为了验证算法的正确性,对[1,10]的数组,随机选择前五个进行验证,运行10000次后,每个数字出现的频率应该是基本相等的,算法的运行结果也证实了这一点,如下图所示。

1#include <iostream>
2#include <string>
3#include <vector>
4#include <cassert>
5#include <cstdio>
6#include <cstdlib>
7#include <ctime>
8using namespace std;
 1/** 
 2 * Reservoir Sampling Algorithm
 3 * 
 4 * Description: Randomly choose k elements from n elements ( n usually is large
 5 *              enough so that the full n elements may not fill into main memory)
 6 * Parameters:
 7 *      v - the original array with n elements
 8 *      n - the length of v
 9 *      k - the number of choosen elements
10 * 
11 * Returns:
12 *      An array with k elements choosen from v
13 *
14 * Assert: 
15 *      k <= n
16 *
17 * Author:  python27
18 * Date:    2015/07/14
19 */
20vector<int> ReservoirSampling(vector<int> v, int n, int k)
21{
22    assert(v.size() == n && k <= n);
    // init: fill the first k elems into reservoir
    vector<int> reservoirArray(v.begin(), v.begin() + k);
 1    int i = 0;
 2    int j = 0;
 3    // start from the (k+1)th element to replace
 4    for (i = k; i < n; ++i)
 5    {
 6        j = rand() % (i + 1); // inclusive range [0, i]
 7        if (j < k)
 8        {
 9            reservoirArray[j] = v[i];
10        }
11    }
    return reservoirArray;
}
1int main()
2{
3    vector<int> v(10, 0);
4    for (int i = 0; i < 10; ++i) v[i] = i + 1;
1    srand((unsigned int)time(NULL));
2    // test algorithm RUN_COUNT times
3    const int RUN_COUNT = 10000;
4    int cnt[11] = {0};
5    for (int k = 1; k <= RUN_COUNT; ++k)
6    {
7        cout << "Running Count " << k << endl;
        vector<int> samples = ReservoirSampling(v, 10, 5);
1        for (size_t i = 0; i <samples.size(); ++i)
2        {
3            cout << samples[i] << " ";
4            cnt[samples[i]]++;
5        }
6        cout << endl;
7    }
1    // output frequency stats
2    cout << "*************************" << endl;
3    cout << "Frequency Stats" << endl;
4    for (int num = 1; num < 11; ++num)
5    {
6        cout << num << " : \t" << cnt[num] << endl;
7    }
8    cout << "*************************" << endl;
    return 0;
}

算法的局限性

蓄水池算法的基本假设是总的样本数很多,不能放入内存,暗示了选择的样本数 k 是一个与 n 无关的常数。然而在实际的应用中,k 常常与 n 相关,比如我们想要随机选择1/3 的样本 (k = n / 3),这时候就需要别的算法或者分布式的算法。

 参考文献

【1】 Wikipedia:Reservoir Sampling