Xác suất & Dữ liệu lớn

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 2)

Xác suất & Dữ liệu lớn

Exponential Decay Reservoir Sampling

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

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.