Lập trình 22/09/2026 7 phút

Reservoir sampling: lấy mẫu ngẫu nhiên đều từ luồng mà không biết độ dài

Làm sao lấy ngẫu nhiên 1000 dòng từ một log đang chảy, khi bạn không biết nó sẽ dài bao nhiêu và không thể giữ hết trong RAM? Algorithm R làm được với một lượt duyệt và bộ nhớ O(k). Bài này tự cài và đo thật: chạy 200.000 lần, mọi phần tử — đầu hay cuối luồng — đều được chọn với xác suất k/N (lệch tối đa 0.18 điểm phần trăm). Cơ chế, vì sao đều, và ứng dụng.

Lập trình 22/09/2026 6 phút

Sampling: head sampling 1% bỏ sót 99% lỗi, error-biased giữ 4% mà bắt 100% lỗi

Trace và log mỗi request thì đúng nhất, nhưng hàng triệu request/ngày là khối dữ liệu không kham nổi. Sampling giảm khối lượng — nhưng sampling ngẫu nhiên (head) bỏ mù đúng thứ cần thấy: lỗi hiếm. Bài này đo thật trên 100.000 trace: head sampling 1% chỉ bắt 14/1029 lỗi (bỏ sót 99%); error-biased sampling giữ tổng cộng chỉ 4% mà bắt trọn 1029/1029 lỗi. Cùng bàn cái giá của tail sampling và vì sao metric không sample.