C++ LFU嵌LRU递进缓存-北京尧图网络

背景怎么样选出最受欢迎的水果中最近购买的品种的价格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/创作不易小小的支持一下吧

C++ LFU嵌LRU递进缓存

相关推荐

HarmonyOS DevEco Studio的使用练习题

JavaScript - 比较运算符：等于与全等的核心区别

FreeToken 快速上手：用 ft serve / ft shell / ft launch 在本地跑起 MoE 大模型服务

更多资讯

微电网中光伏与空调负荷的优化控制策略

ERP库存上下限管理：设置技巧与预警优化

基于MCP协议构建跨平台AI指挥中心的技术实践

C++ STL全排列：next/prev_permutation避坑

档案管理系统设计与实现：从架构到安全

VeRL框架与PPO算法在机器人控制中的应用实践

今日更新

PLFM_RADAR：从被动告警到主动感知的微服务健康监控系统

SPI隔离设计实战：MAX14431BAEE+与STM32F407工业级应用

数字隔离器如何根治SPI通信地环路干扰：MAX14431与TM4C129实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？