蓄水池抽样-reservoir

蓄水池抽样是在O(n)复杂度下随机从海量动态的数据流中取m个数据的一种算法，常在机器学习中使用。

以下是对蓄水池抽样算法的简单图示说明： 蓄水池抽样算法.png

场景模拟代码实现如下：

const reservoir = (data_stream, m) => {
    let n = data_stream.length;
    let reservoir = new Array(m);

    for(let i=0;i<reservoir.length;i++) 
        reservoir[i] = data_stream[i];
    
    for(let i=m;i<n;i++){
        let j = parseInt(Math.random()*(i+1));
        if(j>=0 && j<m) reservoir[j] = data_stream[i];
    }

    return reservoir;
};