蓄水池抽樣是在O(n)復(fù)雜度下隨機(jī)從海量動(dòng)態(tài)的數(shù)據(jù)流中取m個(gè)數(shù)據(jù)的一種算法,常在機(jī)器學(xué)習(xí)中使用儒恋。
以下是對蓄水池抽樣算法的簡單圖示說明:蓄水池抽樣算法.png
場景模擬代碼實(shí)現(xiàn)如下:
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;
};