蓄水池抽样算法 (reservoir sampling algorithm)-ag真人游戏

蓄水池抽样算法简介

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

array r[k];    // result
integer i, j;
// fill the reservoir array
for each i in 1 to k do
    r[i] := s[i]
done;
// replace elements with gradually decreasing probability
for each i in k 1 to length(s) do
    j := random(1, i);   // important: inclusive range
    if j <= k then
        r[j] := s[i]
    fi
done

算法首先创建一个长度为k的数组（蓄水池）用来存放结果，初始化为s的前k个元素，然后从k 1个元素开始迭代直到数组结束，算法生成一个随机数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. 命题得证。

算法实现

#include
#include
#include
using namespace std;
vector reservoirsampling(vector& v, int n, int k){
    if (k > n || v.size() != n)return vector{};
    vector res(v.begin(), v.begin()   k);
    int i = 0, j = 0;
    for (int i = k; i < n; i  ){
        j = rand() % (i   1);  // inclusive range [0, i]
        if (j < k){
            res[j] = v[i];
        }
    }
    return res;
}
int main()
{
    vector v(10, 0);
    for (int i = 0; i < 10;   i) v[i] = i   1;
    srand((unsigned int)time(null));
    // test algorithm run_count times
    const int run_count = 10000;
    int cnt[11] = { 0 };
    for (int k = 1; k <= run_count;   k)
    {
        cout << "running count " << k << endl;
        vector samples = reservoirsampling(v, 10, 5);
        for (size_t i = 0; i