r_tool/cache/
lfu_cache.rs

1use std::collections::{HashMap, LinkedList};
2
3pub struct LFUCache<K:Eq, V> {
4    capacity: usize,
5    cache: HashMap<K, (V, usize, usize)>,
6    order: LinkedList<K>,
7}
8
9impl<K :Eq, V> LFUCache<K, V>
10    where
11        K: Eq + std::hash::Hash + Clone,
12{
13    /// 创建一个新的LFU缓存实例。
14    ///
15    /// # 参数
16    ///
17    /// * `capacity`: usize - 缓存的容量
18    ///
19    /// 返回值：LFUCache<K, V> - 新创建的LFU缓存实例
20    pub fn new(capacity: usize) -> Self {
21        LFUCache {
22            capacity,
23            cache: HashMap::with_capacity(capacity),
24            order: LinkedList::new(),
25        }
26    }
27
28    /// 获取缓存中指定键的值，并将该键的访问频率增加，并将该键标记为最近使用。
29    ///
30    /// # 参数
31    ///
32    /// * `key`: &K - 要获取的键的引用
33    ///
34    /// 返回值：Option<&V> - 如果存在则返回对应值的引用，否则返回None
35    pub fn get(&mut self, key: &K) -> Option<&V> {
36        if let Some((value, frequency, timestamp)) = self.cache.get_mut(key) {
37            // 更新访问频率
38            *frequency += 1;
39            // 更新时间戳
40            *timestamp = self.order.len();
41            // 将键移动到顺序列表的末尾（最近使用）
42            let popped_key = self.order.pop_front().unwrap();
43            self.order.push_back(popped_key);
44            Some(value)
45        } else {
46            None
47        }
48    }
49
50    /// 将键值对插入缓存中，如果缓存已满则淘汰访问频率最低的项。
51    ///
52    /// # 参数
53    ///
54    /// * `key`: K - 要插入的键
55    /// * `value`: V - 要插入的值
56    pub fn put(&mut self, key: K, value: V) {
57        if self.cache.len() >= self.capacity {
58            // 找到访问频率最低的项
59            let min_frequency_key = self
60                .order
61                .iter()
62                .min_by_key(|&k| self.cache.get(k).map_or(usize::MAX, |(_, f, _)| *f))
63                .cloned();
64
65            // 淘汰访问频率最低的项
66            if let Some(oldest_key) = min_frequency_key {
67                self.cache.remove(&oldest_key);
68            }
69        }
70
71        // 插入新项
72        let timestamp = self.order.len();
73        self.cache.insert(key.clone(), (value, 1, timestamp));
74        // 将键移动到顺序列表的末尾（最近使用）
75        self.order.push_back(key);
76    }
77}
78
79#[cfg(test)]
80mod tests {
81    use super::*;
82
83    #[test]
84    fn test_lfu_cache() {
85        let mut lfu_cache = LFUCache::new(3);
86
87        // 插入项
88        lfu_cache.put("one", 1);
89        lfu_cache.put("two", 2);
90        lfu_cache.put("three", 3);
91
92        // 访问一项以使其成为最近使用的项
93        assert_eq!(lfu_cache.get(&"one"), Some(&1));
94
95        // 访问"two"两次，以增加其访问频率
96        assert_eq!(lfu_cache.get(&"two"), Some(&2));
97        assert_eq!(lfu_cache.get(&"two"), Some(&2));
98
99        // 插入新项，淘汰访问频率最低的项（"three"）
100        lfu_cache.put("four", 4);
101
102        // 检查缓存的状态
103        assert_eq!(lfu_cache.cache.len(), 3);
104        assert_eq!(lfu_cache.get(&"one"), Some(&1));
105        assert_eq!(lfu_cache.get(&"two"), Some(&2));
106        assert_eq!(lfu_cache.get(&"three"), None); // "three" 应该被淘汰
107        assert_eq!(lfu_cache.get(&"four"), Some(&4));
108    }
109}
r_tool/cache/lfu_cache.rs

r_tool/cache/
lfu_cache.rs
