神奇的R算法

由于疫情原因，软件行业也变得越来越不景气了，找工作的人越来越多。这不老板让告诉小王公司要招5名程序猿，才一上午的工夫就有100多份简历投来。老板告诉小王他只准备看20份简历，望着桌面上的简历和下午还不知道有多少的简历，小王有点头疼。该怎么样才能在保证公平的前提下随机选出20份简历呢？

问题分析

为了更好的帮助小王解决这个难题，我们把这个问题转化成一个数学问题。如何一串长度n未知的数据流中挑选出k个随机样本？这是一道经典的随机算法题。算法不知道总体n的大小，我们也无法回溯先前的数据。设想一下，如果我们知道流的大小n为N，则按照概率抽k/N抽取k个数据即可。那么现在n为止，抽取的概率也未知，该怎么办呢？

Reservoir sampling（R算法）

1. 抽取前K个数据，如果n=K,则结束；

2. 遇到第K+1数据，以的概率与K个数据中的一个替换；

代码的实现

#include <iostream>
#include <random>
#include <vector>
#include <random>
template<class T>
class Selector
{
public:
    Selector(int _k = 0) : k(_k), count(0) {}
    ~ Selector() {}
    void set(int _k) {
        this.k = _k;
    }
    void reset() {
        k = 0;
        count = 0;
        sampVec.clear();
    }
    void put(const T& _t) {
        ++count;
        if (count < k + 1) {
            sampVec.push_back(_t);
        } else {
            int random = rand() % count;
            if (random < k) {
                sampVec[random] = _t;
            }
        }   
    }
    const std::vector<T>& getSample() const{
        return sampVec;
    }
    int getCount() const {
        return count;
    }
    int getK() const {
        return k;
    }
private:
    std::vector<T> sampVec;
    int k;
    int count;
};
int main()
{
    printf("请开始输入数字:\n");
    Selector<int> filter(3);
    int num = 0;
    srand(time(NULL));
    while (scanf("%d", &num) != EOF) {
        filter.put(num);
        printf("总数:%d, 抽取样本数:%d\n", filter.getCount(), filter.getK());
        printf("抽取样本集合[");
        for (const auto& i : filter.getSample()) {
            printf("%d ", i);
        }
        printf("]");
    }
    return 0;
}

运行：输入[100-116], 结果如下：