Đo độ tương đồng hai tập lớn (Jaccard) cần giao chúng — tốn khi có triệu tập. MinHash rút mỗi tập thành một chữ ký vài trăm số, và một sự thật đẹp: xác suất min-hash của hai tập trùng nhau đúng bằng Jaccard similarity. Bài này tự cài và đo thật: MinHash ước lượng Jaccard bám sát giá trị thật, sai số giảm theo 1/√k, và mỗi tập chỉ tốn 1KB thay vì 250KB. Nền của phát hiện trùng lặp và gợ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.
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.
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.
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.
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.