Bộ nhớ cố định
Vì sao điều này quan trọng "Đếm mỗi thứ xảy ra bao nhiêu lần" là một dict, cho tới khi số thứ không có giới hạn còn bộ nhớ thì có. Một số đếm gần đúng với một giới hạn được bảo đảm thường đáng giá hơn nhiều so với một số đếm chính xác bạn không kham nổi.
Một cổng API đánh dấu những người dùng nặng. Nó thấy mọi yêu cầu, có thể có bao nhiêu người dùng cũng được, và mỗi tiến trình cổng được một phần bộ nhớ cố định cho việc này. Dấu đánh chỉ là một lời nhắc để con người xem xét, nên đếm dư một chút thì được; đếm thiếu có thể giấu một người dùng nặng, nên thì không.
Sketch: một bản tóm tắt kích thước cố định của một luồng trả lời câu hỏi gần đúng, với một giới hạn sai số đã biết. Ví dụ một count-min sketch giữ vài hàng bộ đếm và băm mỗi phần tử tới một bộ đếm trên mỗi hàng; bộ đếm nhỏ nhất trong số đó không bao giờ thấp hơn số đếm thật.
import zlib
row_index = zlib.crc32(f"{row}:{item}".encode()) % width # same on every runViết class ApproxCounter với add(item) (các phần tử là chuỗi) và estimate(item) (một số nguyên).
Giới hạn. Sau 30.000 sự kiện từ tối đa 10.000 người dùng khác nhau, bộ đếm được giữ nhiều nhất 3.500 mục (kept() trên bộ đếm). Các ước lượng không bao giờ được thấp hơn số đếm thật, và với ít nhất 95% người dùng (kể cả người dùng chưa từng thấy) phải nhiều nhất bằng số đếm thật cộng 300 (1% số sự kiện). Kết quả phải lặp lại được ở mọi lần chạy và mọi thiết bị: đừng dùng hash() (nó thay đổi mỗi lần chạy) hay số ngẫu nhiên; zlib.crc32 hay hashlib với seed cố định thì được.
Bạn thấy vấn đề gì trong bài học này? Hãy báo cáo nó · Hỏi về bài học này
Bài tập này sẽ sớm mở.
Hoàn thành bài học trước đó để mở khóa bài này. Toàn bộ khóa học là miễn phí, không cần tài khoản, và bạn có thể đọc bài học này ngay bây giờ.
Trình duyệt này đang chặn cookie cho learn.floati.life, nên các bài học bạn đã hoàn thành tại đây không thể mở theo thứ tự. Hãy cho phép cookie cho trang web này và tải lại trang.