背景怎么样选出最受欢迎的水果中最近购买的品种的价格LRU类#include list #include map #include unordered_map templatetypename K, typename V class LRUMap { public: using ListType std::liststd::pairK, V; using CacheMap std::mapK, 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::mapK, 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 LRUMapKey, float { public: LFUCache(int cap) : LRUMapKey, 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_mapstd::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_setstd::string{ iter-first }); else newFreqFindIter-second.insert(iter-first); iter-second.setFreq(newFreq); } private: std::unordered_mapstd::string, LRUCache m_fruitLRUMap; // 每种水果最近出现的品种 std::mapint, std::unordered_setstd::string m_fruitFreqMap; // 经常出现的水果 int m_capacity; };使用示例一// 水果最近有被购买 bool testPriceChange(const Key key, float price) { LRUMapstd::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/创作不易小小的支持一下吧
