Xác suất

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 1)

Xác suất

Reservoir Sampling

Thời gian (Time) O(n)
Không gian (Space) O(k)

Mô tả nguyên lý

Chọn ngẫu nhiên k phần tử từ một luồng dữ liệu (stream) chưa biết trước kích thước.

Cài đặt mẫu (Implementation)

function reservoirSampling($stream, $k) {
    $res = [];
    foreach ($stream as $i => $item) {
        if ($i < $k) $res[] = $item;
        else {
            $j = mt_rand(0, $i);
            if ($j < $k) $res[$j] = $item;
        }
    }
    return $res;
}