Xác suất & Dữ liệu lớn
Exponential Decay Reservoir Sampling
ID: #233
Xem trên trang chủ
Thời gian (Time)
O(N log K)
Không gian (Space)
O(K)
Mô tả nguyên lý
Lấy mẫu ngẫu nhiên có trọng số thời gian (ưu tiên các dữ liệu mới xuất hiện gần đây nhất).
Cài đặt mẫu (Implementation)
// Gán trọng số điểm ưu tiên giảm dần theo hàm mũ thời gian cho các phần tử trong bình chứa mẫu.
Xác suất & Dữ liệu lớn
HyperLogLog Cardinality Estimation
ID: #180
Xem trên trang chủ
Thời gian (Time)
O(N)
Không gian (Space)
O(Memory nhỏ)
Mô tả nguyên lý
Ước tính số lượng phần tử phân biệt (distinct count) với mức tiêu thụ bộ nhớ cực kỳ nhỏ (vài KB).
Cài đặt mẫu (Implementation)
// Dựa trên xác suất số lượng bit 0 liên tiếp lớn nhất trong giá trị băm.