NC设计LFU缓存结构
系列文章目录
文章目录
- 系列文章目录
- 前言
前言
前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这篇文章男女通用，看懂了就去分享给你的码吧。
描述
一个缓存结构需要实现如下功能。
set(key, value)：将记录(key, value)插入该结构
get(key)：返回key对应的value值
但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；
如果调用次数最少的key有多个，上次调用发生最早的key被删除
这就是LFU缓存替换算法。实现这个结构，K作为参数给出
若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，返回一个答案
import java.util.*;
public class Solution {//设置节点结构static class Node{ int freq;int key;int val;//初始化public Node(int freq, int key, int val) {this.freq = freq;this.key = key;this.val = val;}}//频率到双向链表的哈希表private Map<Integer, LinkedList<Node> > freq_mp = new HashMap<>();//key到节点的哈希表private Map<Integer, Node> mp = new HashMap<>();//记录缓存剩余容量private int size = 0; //记录当前最小频次private int min_freq = 0;public int[] LFU (int[][] operators, int k) {//构建初始化连接//链表剩余大小this.size = k;//获取操作数int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count();int[] res = new int[len];//遍历所有操作for(int i = 0, j = 0; i < operators.length; i++){if(operators[i][0] == 1)//set操作set(operators[i][1], operators[i][2]);else//get操作res[j++] = get(operators[i][1]);}return res;}//调用函数时更新频率或者val值private void update(Node node, int key, int value) { //找到频率int freq = node.freq;//原频率中删除该节点freq_mp.get(freq).remove(node); //哈希表中该频率已无节点，直接删除if(freq_mp.get(freq).isEmpty()){ freq_mp.remove(freq);//若当前频率为最小，最小频率加1if(min_freq == freq) min_freq++;}if(!freq_mp.containsKey(freq + 1))freq_mp.put(freq + 1, new LinkedList<Node>());//插入频率加一的双向链表表头，链表中对应：freq key valuefreq_mp.get(freq + 1).addFirst(new Node(freq + 1, key, value)); mp.put(key, freq_mp.get(freq + 1).getFirst());}//set操作函数private void set(int key, int value) {//在哈希表中找到key值if(mp.containsKey(key)) //若是哈希表中有，则更新值与频率update(mp.get(key), key, value);else{ //哈希表中没有，即链表中没有if(size == 0){//满容量取频率最低且最早的删掉int oldkey = freq_mp.get(min_freq).getLast().key; //频率哈希表的链表中删除freq_mp.get(min_freq).removeLast(); if(freq_mp.get(min_freq).isEmpty()) freq_mp.remove(min_freq); //链表哈希表中删除mp.remove(oldkey); }//若有空闲则直接加入，容量减1else size--; //最小频率置为1min_freq = 1; //在频率为1的双向链表表头插入该键if(!freq_mp.containsKey(1))freq_mp.put(1, new LinkedList<Node>());freq_mp.get(1).addFirst(new Node(1, key, value)); //哈希表key值指向链表中该位置mp.put(key, freq_mp.get(1).getFirst()); }}//get操作函数private int get(int key) {int res = -1;//查找哈希表if(mp.containsKey(key)){ Node node = mp.get(key);//根据哈希表直接获取值res = node.val;//更新频率 update(node, key, res); }return res;}
}