App: top-K trên stream bằng heap

Giới thiệu

Bài này xây bảng trending như top hashtag. Dữ liệu chảy tới đâu, bảng xếp hạng cập nhật tới đó.

Kiến thức cần nhớ

Min-heap giữ top-K

• Min-heap cỡ K giữ K item điểm cao nhất.
• Cập nhật tốn $O(log K)$ thay vì sắp hết $O(N log N)$.
• Ví dụ đời thường: giữ khay 10 món bán chạy, món yếu bị đẩy ra.
• Truy vấn mới đồng bộ heap từ bảng đếm.

Cửa sổ trượt theo thời gian

• Chỉ đếm event trong cửa sổ W gần nhất như 1 giờ qua.
• Event già hơn W bị trừ đếm và xóa khỏi hàng đợi.
• Ví dụ đời thường: bảng trending hôm nay bỏ qua tin tuần trước.
• Nhờ đó item hết hot tự rơi khỏi top.

Đếm xấp xỉ khi vượt RAM

• Từ vựng vô hạn thì chuyển sang bộ đếm xác suất.
• RAM cố định, chấp nhận sai số nhỏ có báo cáo.
• Ví dụ đời thường: đếm lượt thả tim bằng máy bấm ước lượng.
• Bảng băm cho đếm $O(1)$, deque cho trục xuất $O(1)$.

# Cập nhật trending mỗi event
def on_event(item, now):
    counts[item] += 1  # tăng đếm
    queue.append((now, item))  # xếp hàng chờ trục xuất
    evict_older_than(now - W)  # bỏ event quá cũ

Ví dụ

• Input: 100 nghìn event cố định, hỏi top-10. Output: khớp 100% với sắp xếp brute-force.
• Giải thích: heap lazy vẫn giữ đúng K item điểm cao nhất.
• Input: hashtag bùng nổ 5 phút rồi im 2 lần W. Output: lọt top-5 rồi tự rơi khỏi top.
• Giải thích: hết cửa sổ thì đếm bị trừ về 0.

💻 Bài tập

Ngôn ngữ: Python 3 (hoặc C++). Dùng heap ngày 26. Nộp vào day-129-topk/.

Bài 1: Top-K chính xác trong cửa sổ thời gian

class TrendingTopK:
    def __init__(self, k: int, window_sec: float): ...
    def add(self, item: str, ts: float): ...           # ts tăng dần
    def top(self, now: float) -> list[tuple[str, int]]: ...

k=2, window=60: a@0, b@10, a@20, c@30, c@40, c@50
top(55) -> [(c,3), (a,2)]
top(75) -> [(c,3), (a,1)]   (a@0 và b@10 đã hết hạn)

Bài 2: Bộ đếm xác suất khi từ vựng vô hạn

1. Cài Count-Min Sketch (width, depth): add(item), estimate(item). Ước lượng không bao giờ thấp hơn thật.
2. Cài Space-Saving (Misra-Gries biến thể) giữ đúng m bộ đếm.
3. Luồng 10^7 hashtag theo Zipf, 10^6 hashtag khác nhau. So top 20 của 2 cách với top 20 chính xác:

phương_pháp        bộ_nhớ     recall@20    sai_số_đếm_trung_bình
chính xác          ...        1.0          0
Count-Min + heap   ...        ...          ...
Space-Saving m=100 ...        ...          ...

Bài 3: Dashboard trending (nâng cao)

1. Đọc luồng từ file log lớn (hoặc sinh bằng asyncio), 10.000 event/giây.
2. Mỗi giây in top 10 trong 5 phút gần nhất (dùng bản xác suất).
3. Phát hiện đột biến: item có đếm trong 1 phút gần nhất gấp 5 lần trung bình 1 phút của 30 phút trước. In cảnh báo.
4. Đo bộ nhớ và CPU khi chạy 10 phút.

✅ Tiêu chí hoàn thành

• Test cửa sổ thời gian pass.
• Count-Min không bao giờ ước lượng thấp (có test).
• Bảng so sánh 3 cách có số thật.
• Dashboard chạy 10 phút, bộ nhớ ổn định.

❓ Câu hỏi ôn tập

• Min-heap giữ top-K rẻ hơn sắp hết ở điểm gì?
• Cửa sổ trượt giúp trending tươi thế nào?
• Khi nào phải chuyển sang đếm xấp xỉ?
• Event tới trễ quá cũ xử lý ra sao?

🌕 Bạn đã hoàn thành ngày 129. Làm hết bài tập phía trên rồi sang ngày tiếp theo.