背景
怎么样选出最受欢迎的水果中最近购买的品种的价格？
LRU类
#include <list> #include <map> #include <unordered_map> template<typename K, typename V> class LRUMap { public: using ListType = std::list<std::pair<K, V>>; using CacheMap = std::map<K, typename ListType::iterator>; using CacheMapIter = typename CacheMap::iterator; LRUMap(int cap = 100) : m_capacity(cap) { } virtual ~LRUMap() { } CacheMapIter find(const K& key) { return m_cache.find(key); } bool isValid(const CacheMapIter& iter) const { return iter != m_cache.end(); } V get(const K& key) { return get(find(key)); } /** * @brief 缓存查询 * @param it */ V get(const CacheMapIter& it) { if (it == m_cache.end()) return {}; m_list.splice(m_list.begin(), m_list, it->second); return it->second->second; } /** * @brief 缓存新增 * @param key * @param value */ void put(const K& key, V value) { if (m_list.size() == m_capacity) { // 先删除最后一个 auto last = m_list.end(); --last; m_cache.erase(last->first); m_list.pop_back(); } m_list.emplace_front(key, value); m_cache.try_emplace(key, m_list.begin()); } /** * @brief 热度更新。数据变更 * @param it */ void update(const CacheMapIter& it) { if (it == m_cache.end()) return; if (m_list.size() < 2) return; m_list.splice(m_list.begin(), m_list, it->second); it->second = m_list.begin(); } /** * @brief 热度更新。数据不变 * @param it * @param value */ void update(const CacheMapIter& it, V value) { if (it == m_cache.end()) return; if (m_list.empty()) return; if (m_list.size() < 2) { m_list.begin()->second = value; return; } m_list.splice(m_list.begin(), m_list, it->second); it->second = m_list.begin(); it->second->second = value; } private: int m_capacity; ListType m_list; std::map<K, typename ListType::iterator> m_cache; };LRU键类
class Key { public: Key(std::string type, std::string color):m_type(type), m_color(color){} std::string type() const { return m_type; } std::string color() const { return m_color; } private: bool operator<(const Key& other) const { return if(m_type == other.type()) return m_color < other.color(); return m_type < other.type();} bool operator==(const Key& other) const { return m_type == other.type() && m_color == other.color(); } private: std::string m_type; std::string m_color; };LRU扩展类
class LRUCache : public LRUMap<Key, float> { public: LFUCache(int cap) : LRUMap<Key, float>(cap) , m_freq(0) { } int freq() const { return m_freq; } void setFreq(int freq) { m_freq = freq; } private: int m_freq; };LFU类
// LRU最近使用缓存，例如青苹果和红苹果都是苹果，最近出现的颜色被缓存。 // LFU出现最多缓存，例如香蕉和苹果都是水果，应该被分类，出现次数多的水果被缓存。 // LFU嵌LRU类 class LFUCache { public: using Iter = std::unordered_map<std::string, LRUCache>::iterator; LFUCache(int cap) : m_capacity(cap) { } LRUCache& insert(const std::string& content) { auto findIter = m_fruitLRUMap.find(content); if (findIter == m_fruitLRUMap.end()) { if (m_fruitLRUMap.size() >= m_capacity) shrink_to_fit_one(); findIter = m_fruitLRUMap.try_emplace(content, 12).first; } updateFreq(findIter); return findIter->second; } private: /* * * 删除一个低频次的LRU缓存 */ void shrink_to_fit_one() { if (m_fruitFreqMap.empty()) return; auto lowFreqIter = m_fruitFreqMap.begin(); if (lowFreqIter->second.empty()) return; auto removeIter = lowFreqIter->second.begin(); m_fruitLRUMap.erase(*removeIter); // 更新LRU缓存 if (lowFreqIter->second.size() < 2) { m_fruitFreqMap.erase(lowFreqIter); return; } lowFreqIter->second.erase(removeIter); // 删除低频次的一个 } void updateFreq(Iter iter) { // 从旧的频次中删除 auto oldFreq = iter->second.freq(); auto oldFreqFindIter = m_fruitFreqMap.find(oldFreq); if (oldFreqFindIter != m_fruitFreqMap.end()) { if (oldFreqFindIter->second.size() < 2) m_fruitFreqMap.erase(oldFreq); // 只剩一个，整体删除 else oldFreqFindIter->second.erase(iter->first); // 局部删除 } // 新的频次添加 auto newFreq = oldFreq + 1; auto newFreqFindIter = m_fruitFreqMap.find(newFreq); if (newFreqFindIter == m_fruitFreqMap.end()) m_fruitFreqMap.try_emplace(newFreq, std::unordered_set<std::string>{ iter->first }); else newFreqFindIter->second.insert(iter->first); iter->second.setFreq(newFreq); } private: std::unordered_map<std::string, LRUCache> m_fruitLRUMap; // 每种水果最近出现的品种 std::map<int, std::unordered_set<std::string>> m_fruitFreqMap; // 经常出现的水果 int m_capacity; };使用示例一
// 水果最近有被购买 bool testPriceChange(const Key& key, float price) { LRUMap<std::string, Key> lastFruitMap; auto findCacheIter = lastFruitMap.find(key.type()); if (!lastFruitMap.isValid(findCacheIter)) return true; if (findCacheIter->second->second != price) return true; return false; } Key key("苹果"，"红色"); float price = 10.f; auto isChange = testPriceChange(key, price); std::cout << "Price is change " << isChange << std::endl;使用示例二
// 统计经常被购买水果价格 float testPrice(const Key& key) { LFUCache fruitCache; auto& lruCache = fruitCache.insert(key.type()); auto cacheIter = lruCache.find(key); bool hasCache = lruCache.isValid(cacheIter); float price; if (hasCache) { // 最近有被购买 price = cacheIter->second->second; lruCache.update(cacheIter); } else { price = 10; // 请输入价格 lruCache.put(key, price); } return price; } Key key("苹果"，"红色"); auto price = testPrice(key); std::cout << "Price is " << price << std::endl;参考
https://www.geeksforgeeks.org/lru-cache-implementation/
https://leetcode.cn/problems/lru-cache/
https://www.geeksforgeeks.org/least-frequently-used-lfu-cache-implementation/
https://leetcode.cn/problems/lfu-cache/
