蓄水池抽样算法(Reservoir Sampling)

Administrator 创建自 2019-08-09 15:52:10 最后修改于 2个月前

问题

给定一个数据流,数据流长度N很大,且N直到处理完所有数据之前都不可知,请问如何在只遍历一遍数据(O(N))的情况下,能够随机选取出m个不重复的数据。

  • 分析

    • 数据流长度N很大且不可知,所以不能一次性存入内存。

    • 时间复杂度为O(N)。

    • 随机选取m个数,每个数被选中的概率为m/N。

算法核心代码 PHP 示例


/**
  * 使用已知长度的数组 $dataStream 来表示未知长度的数据流
  * 
  * $m 为需要选取的样本数量
  * 
  * 每次循环获得样本数据的概率均为 m/N
  */
function reservoirSampling($dataStream, $m)
{
    $reservoir = array_fill(0, $m, null);

    for ($i = 0; $i < count($reservoir); $i++) {
        $reservoir[$i] = $dataStream[$i];
    }

    for ($i = $m; $i < count($dataStream); $i++) {
        $tmp = rand(0, $i);

        if ($tmp < $m) {
            $reservoir[$tmp] = $dataStream[$i];
        }
    }

    return $reservoir;
}


参考