精华内容
下载资源
问答
  • LFU

    2021-10-19 06:39:54
    LFU(least frequently used (LFU) page-replacement algorithm)。即最不经常使用页置换算法,要求在页置换时置换引用计数最小的页,因为经常使用的页应该有一个较大的引用次数。 unordered_map<int, list<...

    LFU(least frequently used (LFU) page-replacement algorithm)。即最不经常使用页置换算法,要求在页置换时置换引用计数最小的页,因为经常使用的页应该有一个较大的引用次数。

    unordered_map<int, list<node>::iterator> map_key;
    unordered_map<int, list<node>> map_cnt;
    int min_cnt = 0;
    
    int LFUGet(int key)
    {
    	auto findIter = map_key.find(key);
    	if (findIter == map_key.end())
    	{
    		return -1;
    	}
    	else
    	{
    		int cnt = findIter->second->cnt;
    		int val = findIter->second->v;
    		map_cnt[cnt].erase(findIter->second);		//移除当前链表的尾部
    		map_cnt[cnt+1].push_front(node(key, val, cnt + 1));		//添加到新链表的头部
    		map_key[key] = map_cnt[cnt+1].begin();
    		//修改最小调用次数 min_cnt
    		if (min_cnt == cnt && map_cnt[cnt].size() == 0)
    		{
    			min_cnt++;
    		}
    		return val;
    	}
    }
    
    void LFUSet(int key, int val, int k)
    {
    	auto findIter = map_key.find(key);
    
    	//当前数据不存在,需要新插入
    	if (findIter == map_key.end())
    	{
    		//缓存没有剩余的空间
    		if (map_key.size() >= k)
    		{
    			int deleteKey = map_cnt[min_cnt].back().k;
    			map_cnt[min_cnt].pop_back();
    			map_key.erase(deleteKey);
    		}
    		map_cnt[1].push_front(node(key, val, 1));
    		map_key[key] = map_cnt[1].begin();
    		min_cnt = 1;
    	}
    	//当前数据已经存在
    	else
    	{
    		int cnt = findIter->second->cnt;
    		map_cnt[cnt].erase(findIter->second);
    		map_cnt[cnt + 1].push_front(node(key, val, cnt + 1));
    		map_key[key] = map_cnt[cnt + 1].begin();
    		
    		//删除了数据之后需要调整最小调用次数,如果被删除的列表为空,则调整为当前key的次数
    		if (min_cnt == cnt && map_cnt[cnt].size() == 0)
    		{
    			min_cnt++;
    		}
    	}
    }
    
    
    vector<int> LFU(vector<vector<int> >& operators, int k) {
    	vector<int> res;
    	for (auto& it : operators)
    	{
    		if (it[0] == 1)
    		{
    			LFUSet(it[1], it[2], k);
    		}
    		else
    		{
    			res.push_back(LFUGet(it[1]));
    		}
    	}
    	return res;
    
    }
    
    
    展开全文
  • LFU算法LFU算法LFU算法LFU算法

    热门讨论 2009-12-13 01:15:24
    LFU算法LFU算法LFU算法LFU算法LFU算法
  • Window-LFU 实现一个window-LFU缓存(即置换指定时间内,按照LFU规则排序淘汰数量)要求对外提供的接口: 可以指定cache的大小 可以指定时间窗口(windows) 提供get/put/remove数据访问方法 提供缓存命中率hitrate...
  • LFU cache

    2021-08-22 12:05:51
    LFU 请你为 最不经常使用(LFU)缓存算法设计并实现数据结构。它应该支持以下操作:get 和 put。 get(key) - 如果键存在于缓存中,则获取键的值(总是正数),否则返回 -1。 put(key, value) - 如果键不存在,请设置...

    LFU

    请你为 最不经常使用(LFU)缓存算法设计并实现数据结构。它应该支持以下操作:get 和 put。
    get(key) - 如果键存在于缓存中,则获取键的值(总是正数),否则返回 -1put(key, value) - 如果键不存在,请设置或插入值。当缓存达到其容量时,则应该在插入新项之前,使最不经常使用的项无效。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该去除 最近 最少使用的键。
    「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
    
    进阶:
    你是否可以在 O(
    展开全文
  • LFU算法族:window-LFU

    2021-01-27 20:58:47
    1、LFU算法的不足 LFU(LeastFrequentlyUsed)是一种缓存淘汰算法。LFU算法是根据缓存的访问频率,去淘汰访问次数最低的缓存。这样就给LFU带来了两个问题: 不可避免的问题:对于每个缓存项,LFU都需要记录其访问...

    LFU算法族相关文章目录汇总:

    LFU算法

    LFU-Aging算法

    window-LFU算法(本文)

    1、LFU算法的不足

        LFU(Least Frequently Used)是一种缓存淘汰算法。LFU算法是根据缓存的访问频率,去淘汰访问次数最低的缓存。这样就给LFU带来了两个问题:

    1. 不可避免的问题:对于每个缓存项,LFU都需要记录其访问次数,这导致了LFU需要一笔不小的额外内存开销;
    2. 可一定程度避免的问题:对于记录的访问次数,LFU要对其进行排序,用于淘汰访问次数最低的算法。而对大量数据的排序,则会带来一定的处理器开销。当然,这个开销可以通过在每次操作时调整排序顺序,来避免在内存淘汰时一次发生。

        同时,由于LFU记录的是缓存生成以来访问频率,如果一条缓存曾经访问了很多次,但是如果服务的逻辑发生了改变,这条缓存已经很少甚至不再会被访问,这条缓存由于其历史访问次数很高,依然不会被淘汰。这就导致了缓存污染的问题:

    • 缓存污染:系统将不常用的数据存入到缓存,造成常用数据的挤出,降低了缓存效率的现象。

        总结来说,LFU算法有两个不可避免的问题:

    1. 对于每个缓存项,LFU都需要记录其访问次数,需要不小的额外内存开销;
    2. 近期不再访问的历史数据无法清理,导致缓存污染。

    2、window-LFU算法描述

        Window-LFU被用来一定程度上解决LFU上述两步不可避免的问题。

        Window是用来描述算法保存的历史请求数量的窗口大小的。Window-LFU并不记录所有数据的访问历史,而只是记录过去一段时间内的访问历史。即当请求次数达到或超过window的大小后,每次有一条新的请求到来,都会清理掉最旧的一条请求,以保证算法记录的请求次数不超过window的大小。

    2.1 缓存访问记录的维护

        在实现时,Window-LFU一般会维护一个定长队列,或者用数组实现环形缓存区来存储访问历史。

        例如:一个缓存场景,window = 9,现在有9条缓存访问记录,按时间顺序从先到后分别是:A,B,C,D,A,B,C,D,A,即缓存队列

        此时又来了一条新的缓存请求B,这是Window-LFU算法就会把第一条缓存访问记录A删掉,并将B加到队尾:

    2.2 缓存淘汰

        Window-LFU的缓存淘汰方式和LFU是一致的。

        Window-LFU首先会计算window条记录中各条缓存项的访问次数,然后根据访问次数排序,淘汰次数最少的缓存项。当然,计算缓存想访问次数的操作,也可以放到每次缓存访问记录更新的同时,这样就避免了每次缓存操作的耗时长的问题。

        一般来说,Window-LFU会使用哈希结构来存储“缓存项 <---> 访问次数”的映射,因为哈希的时间复杂度低,为o(1)。

    3、Window-LFU的优缺点

    3.1 优点

        由于Window-LFU不存储全部历史数据,所以其额外内存开销要明显低于LFU算法,同时由于数据量明显减少,Window-LFU排序的处理器成本也要低于LFU。

        另外,由于早于前window次的缓存访问记录会被清理掉,所以Window-LFU也可以避免缓存污染的问题,因为过早时间访问的缓存已经被清理掉了。

        在缓存命中率方面,Window-LFU一般会由于LFU,因为Window-LFU一定程度上解决了缓存污染的问题,缓存的有效性更高了。缓存污染问题越严重的场景,Window-LFU的命中率就比LFU高的越多。

       另外,和LFU-Aging相比,Window-LFU对缓存污染问题的解决更彻底一些,所以在缓存使用场景产生改变时,命中率会优于LFU-Aging。

    3.2 缺点

        但是Window-LFU需要维护一个队列去记录历史的访问流,复杂度略高于LFU。

    展开全文
  • LFU算法

    2021-09-11 13:33:11
    * LFU 算法:淘汰访问频次最低的元素,如果访问频次最低的数据有多条,则需要淘汰最旧的数据。 * */ class LFUCache { // 存放 key 到 val 的映射 HashMap<Integer, Integer> keyToVal = new HashMap<>...

    图示

    /*
    * LFU 算法:淘汰访问频次最低的元素,如果访问频次最低的数据有多条,则需要淘汰最旧的数据。
    * */
    class LFUCache {
        // 存放 key 到 val 的映射
        HashMap<Integer, Integer> keyToVal = new HashMap<>();
        // 存放 key 到 使用频次freq 的映射
        HashMap<Integer, Integer> keyToFreq = new HashMap<>();
        // 使用频次freq 到 key 列表的映射。用于删除最久未使用的 key(即链表头的 key)
        HashMap<Integer, LinkedHashSet<Integer>> freqToKeys = new HashMap<>();
        // 记录最小的频次
        int minFreq = 0;
        // 记录 LFU 缓存的最大容量
        int capacity;
        public LFUCache(int capacity){
            this.capacity = capacity;
        }
        public int get(int key){
            // 如果不存在 key
            if(!keyToVal.containsKey(key)){
                return -1;
            }
            // 增加 key 对应的 freq
            increaseFreq(key);
            return keyToVal.get(key);
        }
        public void put(int key, int val){
            if(capacity <= 0){
                return;
            }
            // 如果 key 已经存在,那么修改对应的 value 即可
            if(keyToVal.containsKey(key)){
                keyToVal.put(key, val);
                // key 对应的 freq 加 1
                increaseFreq(key);
                return;
            }
            // 如果 key 不存在,需要插入
            // 容量已满的话需要淘汰一个 freq 最小的 key
            if(capacity == keyToVal.size()){
                removeMinFreqKey();
            }
    
            // 插入 key 和 value,对应的 freq 为 1
            keyToVal.put(key, val);
            keyToFreq.put(key, 1);
            freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
            freqToKeys.get(1).add(key);
            // 插入新的 key 后最小的 freq 肯定是 1
            minFreq = 1;
        }
        // 增加 key 对应的 freq
        public void increaseFreq(int key){
            int freq = keyToFreq.get(key);
            // 更新 keyToFreq 表。使用频次 + 1
            keyToFreq.put(key, freq + 1);
            // 更新 freqToKeys 表。
            // 将 key 从 freq 对应的列表中删除
            freqToKeys.get(freq).remove(key);
            // 将 key 加入 freq+1 对应的列表中
            freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
            freqToKeys.get(freq + 1).add(key);
            // 如果 freq 对应的列表空了,移除这个 freq
            if(freqToKeys.get(freq).isEmpty()){
                freqToKeys.remove(freq);
                // 如果这个 freq 恰好是 minFreq,更新 minFreq
                if(freq == minFreq){
                    minFreq++;
                }
            }
        }
        // 淘汰一个 freq 最小的 key
        public void removeMinFreqKey(){
            // 得到 freq 最小时对应的 key 列表
            LinkedHashSet<Integer> keyList = freqToKeys.get(minFreq);
            // 最先被插入的那个 key(也就是最长时间没有使用过的 key,即链表头部的 key)就是该被淘汰的 key
            int deleteKey = keyList.iterator().next();
            keyList.remove(deleteKey);
            if(keyList.isEmpty()){
                freqToKeys.remove(minFreq);
                freqToKeys.remove(minFreq);
                // 如果freq 对应的 key 列表空了,此时需要移除这个 freq,因为此时的 freq 就是 minFreq,因此 minFreq 需要加 1。
                // 但其实没有下面这行代码也可以。因为只有在 put 方法插入 key 的时候才有可能调用 removeMinFreqKey() 方法,而在 put() 方法
                // 中,插入新的 key 时一定会把 minFreq 更新变成 1,因此说即使这里 minFreq 变了,我们也不需要管它。
                minFreq++;
            }
            keyToVal.remove(deleteKey);
            keyToFreq.remove(deleteKey);
        }
    }
    
    展开全文
  • LFU模拟

    2021-03-06 18:55:09
    请你为 最不经常使用(LFU)缓存算法设计并实现数据结构。 实现 LFUCache 类: LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象 int get(int key) - 如果键存在于缓存中,则获取键的值,否则...
  • LFU算法族:LFU算法

    千次阅读 2021-02-09 11:26:02
    LFU(LeastFrequentlyUsed)算法根据访问缓存的历史频率来淘汰数据,即“如果数据过去被访问的频率很高,那么将来被访问的频率也会很高”。 2、数据结构 一般会维护两个数据结构: 哈希:用来提供对外部的访问,...
  • LFU缓存 介绍 硬件模拟:C++/python实现的LFU缓存模拟 受 leetcode OJ 的启发: 设计和实现最不常用 (LFU) 缓存的数据结构。 它应该支持以下操作:get 和 put。 兼容性 职能: get(key) - 如果键存在于缓存中,则...
  • 大致基于的恒定时间最少使用(LFU)高速缓存的简单实现。 例子 use lfu_cache :: LfuCache; let mut cache = LfuCache :: with_capacity ( 2 ); // Fill up the cache. cache. insert ( "foo" , 3 ); cache. insert ...
  • LFU缓存

    2021-04-30 17:06:49
    LFU算法 最近最少次数访问,缓存满的时候,优先淘汰掉最少访问的数据,若最少访问次数的数据有多个,淘汰掉访问时间与现在相隔最远的数据。 实现 堆 + 版本号 由于涉及到构建堆,所有操作的时间复杂度均为O(logN) ...
  • LFU算法族目录汇总: LFU算法 LFU-Aging算法(本文) window-LFU算法 1、原理 LFUDA(LFU with dynamic aging),是LFU算法对于缓存污染问题的优化算法。它为缓存引用次数增加了“时间因子”的概念,用来适应...
  • LFU Cache

    2018-03-22 19:10:00
    LFU: least frequently used (LFU) page-replacement algorithm https://leetcode.com/problems/lfu-cache/?tab=Description 题目描述 Design and implement a data structure forLeast Frequently Used(LF...
  • What is the difference between LRU and LFU cache implementations?I know that LRU can be implemented using LinkedHashMap.But how to implement LFU cache?解决方案Let's consider a constant stream of cache...
  • LFU-Cache-源码

    2021-03-11 12:29:51
    LFU缓存 基于所述的实施方式 我们实现了(未优化) 描述的两个版本的LFU替换 1.缓存中的LFU “完美的LFU对对象的所有请求进行计数,i。请求计数在替换中持续存在。一方面,这确保了请求计数代表过去的所有请求。另...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,981
精华内容 7,592
关键字:

lfu