Làm cách nào để triển khai bộ nhớ cache LFU bằng STL?

Question

Tôi đang cố gắng triển khai bộ nhớ cache LFU (Ít nhất được sử dụng thường xuyên) bằng STL thuần túy (Tôi không muốn sử dụng Boost!).

Yêu cầu là:

• truy cập liên tưởng đến bất kỳ yếu tố sử dụng một Key như với std::map.
• Khả năng phát hành mục ưu tiên thấp nhất (sử dụng thuộc tính UsesCount).
• Khả năng cập nhật mức độ ưu tiên (UsesCount) của bất kỳ mục nào.

Những vấn đề là:

• Nếu tôi sử dụng std::vector như container các mặt hàng (Key, Value, UsesCount), std::map như một container của vòng lặp để vector để truy cập kết hợp và std::make_heap, std::push_heap và std::pop_heap khi thực hiện hàng đợi ưu tiên trong vectơ, các vòng lặp trong bản đồ không hợp lệ sau các hoạt động đống.
• Nếu tôi sử dụng std::list (hoặc std::map) thay vì std::vector trong cấu hình trước, std::make_heap, v.v. không thể được biên dịch vì các trình vòng lặp của chúng không hỗ trợ số học.
• Nếu tôi muốn sử dụng std::priority_queue, tôi không có khả năng cập nhật mức độ ưu tiên của mục.

Các câu hỏi là:

• Tôi có thiếu một cái gì đó rõ ràng như thế nào vấn đề này có thể được giải quyết?
• Bạn có thể chỉ cho tôi một số việc thực thi C++/STL thuần túy của bộ đệm LFU đáp ứng các yêu cầu trước đó làm ví dụ không?

Cảm ơn thông tin chi tiết của bạn.

Answer 1

Triển khai thực hiện của bạn bằng cách sử dụng các chức năng *_heap và vectơ có vẻ phù hợp. mặc dù nó sẽ dẫn đến các bản cập nhật chậm. Vấn đề về việc vô hiệu hóa vòng lặp mà bạn gặp phải là bình thường đối với mỗi vùng chứa bằng cách sử dụng một vectơ làm cấu trúc dữ liệu cơ bản. Đây là cách tiếp cận cũng được thực hiện bởi boost::heap::priority_queue, nhưng nó không cung cấp một giao diện có thể thay đổi được vì lý do được đề cập ở trên. Khác boost::heap data-structures cung cấp khả năng cập nhật heap.

Điều gì đó có vẻ hơi lạ: Ngay cả khi bạn có thể sử dụng std::priority_queue bạn vẫn sẽ gặp phải vấn đề mất hiệu lực của trình vòng lặp.

Để trả lời câu hỏi của bạn trực tiếp: Bạn không bỏ lỡ điều gì hiển nhiên. std::priority_queue không hữu ích như mong muốn. Cách tiếp cận tốt nhất là viết bản triển khai heap của riêng bạn để hỗ trợ cập nhật. Để làm cho nó hoàn toàn tương thích STL (đặc biệt là phân bổ nhận thức) là khá phức tạp và không phải là một nhiệm vụ đơn giản. Ngày đầu đó, thực hiện bộ nhớ cache LFU.

Để biết bước đầu tiên, hãy xem triển khai Boost để có ý tưởng về nỗ lực. Tôi không biết về bất kỳ triển khai tham chiếu nào cho lần thứ hai.

Để làm việc xung quanh việc vô hiệu hóa vòng lặp, bạn luôn có thể chọn hướng dẫn vào vùng chứa khác, mặc dù bạn nên tránh nó vì nó tạo thêm chi phí và có thể khá lộn xộn.

Answer 2

Một cách tiếp cận hơi đơn giản hơn việc giữ cấu trúc hai dữ liệu:

• chỉ cần giữ một bản đồ, bản đồ phím của bạn để cặp giá trị/use-count của họ.
• khi bộ nhớ cache là đầy đủ:
• • tạo một vector của các vòng lặp với các yếu tố bản đồ (O(n))
• • sử dụng std::nth_element để tìm ra tồi tệ nhất 10% (O(n))
• • xóa tất cả chúng khỏi bản đồ (O(n log n))

Vì vậy, thêm một yếu tố mới vào bộ nhớ cache là trường hợp phổ biến O(log n), trường hợp xấu nhất O(n log n), và được phân bổ O(log n).

Xóa 10% tồi tệ nhất có thể hơi khó khăn trong bộ đệm LFU, vì các mục nhập mới phải tạo ra 90% hàng đầu hoặc chúng bị cắt. Sau đó, một lần nữa, nếu bạn chỉ loại bỏ một phần tử thì các mục mới vẫn cần phải thoát khỏi đáy trước mục nhập mới tiếp theo, hoặc chúng bị cắt và chúng có ít thời gian hơn để làm như vậy. Vì vậy, tùy thuộc vào lý do tại sao LFU là chiến lược bộ nhớ đệm phù hợp với bạn, thay đổi của tôi đối với nó có thể là chiến lược sai hoặc có thể vẫn ổn.