Xác suất
Reservoir Sampling
ID: #73
Xem trên trang chủ
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;
}