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 8 phút

t-digest: đo p99/p999 của luồng khổng lồ mà không cần lưu và sắp xếp cả mảng

Bài Debug phần 11 tính percentile bằng cách sort cả mảng — tốn RAM tuyến tính và không mergeable. t-digest gom dữ liệu thành centroid, nén dày ở hai đuôi để p99/p999 sắc nét. Bài này cài t-digest rút gọn bằng Python, chạy thật 2 triệu latency: 171 centroid (~2,7 KB) thay 16 MB mảng, p99 sai chỉ 0,1%, và giải thích vì sao nó bền hơn histogram ô đều khi có outlier.

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

Cuckoo filter: bộ lọc vừa tiết kiệm bộ nhớ vừa xóa được — thứ Bloom không làm

Bloom filter (phần 1 loạt này) kiểm tra tồn tại rất gọn nhưng không xóa được phần tử và tỉ lệ dương tính giả cố định. Cuckoo filter lưu fingerprint vào một trong hai bucket, đá (kick) khi đầy, nên xóa được và thường chính xác hơn Bloom ở cùng bộ nhớ. Bài này tự cài Cuckoo filter bằng Python, chạy thật: 249.036 phần tử ở load 95%, FPP 0,18%, xóa hoạt động — và đo điểm giao FPP Cuckoo vs Bloom.

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

Chọn cấu trúc dữ liệu xác suất nào? Tổng kết 12 phần bằng một bảng đo thật

Khép lại loạt Cấu trúc dữ liệu xác suất: điểm lại 11 cấu trúc đã học, mỗi cái trả lời một câu hỏi khác nhau, rồi chạy thật cả năm trên CÙNG một luồng 2 triệu sự kiện để so bộ nhớ và sai số với cách 'giữ hết + tính chính xác'. Kết quả đo được: 5 sketch cộng lại chỉ 527 KB thay cho 52 MB — nhỏ hơn ~96 lần, đổi lấy sai số 0,08%–4,57%. Kèm cây quyết định và khi nào KHÔNG nên dùng ước lượng.

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

JSON trong Go: tiện đến mức ta quên nó tốn gì — đo thật chi phí reflection

encoding/json của Go tiện kinh khủng: một cặp Marshal/Unmarshal cho mọi struct. Nhưng nó dùng reflection lúc chạy nên có chi phí ẩn. Bài này chạy thật một đơn hàng 5 mặt hàng: đo kích thước JSON (643 byte gọn, 928 byte thụt lề), và benchmark cho thấy Unmarshal chậm ~4 lần Marshal với 27 lần cấp phát bộ nhớ so với 3 — vì giải mã phải dựng lại slice, string, struct con.

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

DEFLATE, gzip và zlib: mổ xẻ thuật toán nén phổ biến nhất thế giới

gzip có mặt ở khắp nơi — HTTP, PNG, file .gz — và bên trong nó là DEFLATE: đúng hai thứ ta vừa học, LZ77 chồng lên Huffman. Bài này mổ header gzip thật byte-by-byte (magic 1f 8b, method 08, CRC32, kích thước gốc), so ba lớp vỏ DEFLATE raw / zlib / gzip khác nhau đúng 6 và 18 byte, và chứng minh sức mạnh nằm ở DEFLATE chứ không phải lớp vỏ: gzip level 0 làm dữ liệu to hơn, level 6 nén 153 lần.