lfu-cache

基于 Shah, Mitra 和 Matani 的论文的近似实现，提供了一个常时 Least Frequently Used (LFU) 缓存。

示例

use lfu_cache::LfuCache;
let mut cache = LfuCache::with_capacity(2);

// Fill up the cache.
cache.insert("foo", 3);
cache.insert("bar", 4);

// Insert returns the evicted value, if a value was evicted, in case additional
// bookkeeping is necessary for the value to be dropped.
let maybe_evicted = cache.insert("baz", 5);

// In the case of a tie, the most recently added value is evicted.
assert!(cache.get(&"bar").is_none());
assert_eq!(maybe_evicted, Some(4));

cache.get(&"baz");
// Otherwise, the least frequently value is evicted.
assert_eq!(cache.pop_lfu(), Some(3));

使用此实现的原因

• 零依赖。
• 小型依赖，仅提供必要的功能。
• 全面文档和全面测试（包括 miri）。
• 遵循 Rust API 指南：尽可能实现容器 API。
• 性能：每秒插入约 1000 万次（使用 i32 作为元素；见 benches.rs 以获取基准测试实现）。

不使用此实现的原因

• 由于与原始指针一起工作，该代码库内部使用 unsafe。
• 这可以被视为微库，如果依赖项数量是一个问题，可能不受欢迎。

替代方案

• 考虑仅使用安全 Rust 编写的 lfu crate。
• 考虑 matthusifer/lfu_rs 中的相同论文的另一个实现。

与论文的差异

此实现非常遵循论文，但有一个修改以确保正确性。每个节点在 节点列表 中都包含一个包含其存储键的 Rc，而查找表则按 Rc<Key> 进行索引。这是为了确保在弹出最少使用项时可以移除查找表中的正确键值。