首页 > 试题广场 >

LFU缓存结构设计

[编程题]LFU缓存结构设计
  • 热度指数：577 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
一个缓存结构需要实现如下功能。
  • set(key, value)：将记录(key, value)插入该结构
  • get(key)：返回key对应的value值
但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；
如果调用次数最少的key有多个，上次调用发生最早的key被删除
    这就是LFU缓存替换算法。实现这个结构，K作为参数给出
[要求]
set和get方法的时间复杂度为O(1)

输入描述:
第一行两个个整数N, K，表示操作数量以及缓存结构大小
接下来N行，第一行一个整数opt表示操作类型。
若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1


输出描述:
对于每个操作2，输出一个答案
示例1

输入

8 3
1 1 1
1 2 2
1 3 2
1 2 4
1 3 5
2 2
1 4 4
2 1

输出

4
-1

说明

在执行"1 2 4"后，"1 1 1"被删除。因此第二次询问的答案为-1

备注:
算法知识视频讲解
添加回答
Java
pein531头像 pein531
用一个结构体记录所有信息：键值对，键最近操作时间，键操作次数。维护一个按照操作次数和最近操作时间二次排序的有序表来保证可以快速获得用得最少且操作距今最久的key，之后的设计与LRU缓存结构差不多。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.TreeSet;
import java.util.Comparator;

class Node {
    public int key;           // 键
    public int value;         // 值
    public int timePoint;     // 加入时间点
    public int optNums;       // 操作次数
    public Node(int x, int y) {
        key = x;
        value = y;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
        HashMap<Integer, Node> map = new HashMap<>();
        // 有序表按照操作次数和插入时间二次排序
        TreeSet<Node> orderedSet = new TreeSet<>(new Comparator<Node>() {
            @Override
            public int compare(Node node1, Node node2) {
                return node1.optNums != node2.optNums? node1.optNums - node2.optNums: node1.timePoint - node2.timePoint;
            }
        });
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            int opt = Integer.parseInt(params[0]);
            int x = Integer.parseInt(params[1]);
            if(opt == 1){
                int y = Integer.parseInt(params[2]);
                if(map.containsKey(x)){
                    // 有x直接修改节点信息
                    Node node = map.get(x);
                    orderedSet.remove(node);
                    node.optNums ++;
                    node.value = y;
                    node.timePoint = i;
                    orderedSet.add(node);
                }else{
                    // 新建节点插
                    Node node = new Node(x, y);
                    node.timePoint = i;
                    node.optNums = 1;
                    // 容量满了要先把有序表的第一个节点删了再插入
                    if(map.size() == k){
                        Node firstNode = orderedSet.first();
                        int firstKey = firstNode.key;
                        orderedSet.remove(firstNode);
                        map.remove(firstKey);
                    }
                    map.put(x, node);
                    orderedSet.add(node);
                }
            }else{
                if(!map.containsKey(x)){
                    sb.append(-1 + "\n");
                }else{
                    Node node = map.get(x);
                    orderedSet.remove(node);
                    node.optNums ++;           // get使操作数+1
                    node.timePoint = i;        // 更新调用时间
                    orderedSet.add(node);
                    sb.append(node.value + "\n");
                }
            }
        }
        System.out.println(sb.toString().trim());
    }
}

发表于 2021-11-22 10:35:36 回复(0)
呃嗯头像 呃嗯 
#include <bits/stdc++.h>
using namespace std;
class LFUCache {
public:
    unordered_map<int,pair<int,int> > m;
    unordered_map<int,list<int> >fres;
    unordered_map<int,list<int>::iterator >iters;
    int cap,minc;
    LFUCache(int capacity) {
        cap=capacity;
        minc=0;
    }
    
    int get(int key) {
        if(m.find(key)==m.end()) return -1;
        fres[m[key].second].erase(iters[key]);
        ++m[key].second;
        fres[m[key].second].push_back(key);
        iters[key]=--fres[m[key].second].end();
        while(fres[minc].size()==0) minc++;
        return m[key].first;
    }
    
    void put(int key, int value) {
        if(cap<=0) return;
        if(get(key)!=-1){
            m[key].first=value;
            return ;
        }
        if(m.size()>=cap){
            m.erase(fres[minc].front());
            iters.erase(fres[minc].front());
            fres[minc].pop_front();
        }
        m[key]={value,1};
        minc=1;
        fres[minc].push_back(key);
        iters[key]=--fres[minc].end();
    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

int main(){
    int n,k;
    while(cin>>n>>k){
        LFUCache lfu(k);
        for(int i=0;i<n;i++){
            int op;
            cin>>op;
            if(op==1){
                int a,b;
                cin>>a>>b;
                lfu.put(a,b);
            }else{
                int a;
                cin>>a;
                cout<<lfu.get(a)<<endl;
            }
        }
    }
}

发表于 2019-08-18 16:43:42 回复(0)
Java
绚都头像 绚都
一道题玩一下午。。 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String[] s = sc.nextLine().trim().split(" ");
            int n = Integer.parseInt(s[0]);
            int k = Integer.parseInt(s[1]);
            List<int[]> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                String[] s1 = sc.nextLine().trim().split(" ");
                int[] arr = new int[s1.length];
                for (int j = 0; j < arr.length; j++) {
                    arr[j] = Integer.parseInt(s1[j]);
                }
                list.add(arr);
            }
            List<Integer> res = new Solution().getRes(list, k);
            for (int i = 0; i < res.size(); i++) {
                System.out.println(res.get(i));
            }
        }
    }
}

class Solution {
    public List<Integer> getRes(List<int[]> list, int k) {
        List<Integer> res=new ArrayList<>();
        HashMap<Integer,Node> map=new HashMap<>();
        HashMap<Integer,DoubleLinkedList> freMap=new HashMap<>();
        int minFre=0;
        int capacity=0;
        for (int i = 0; i < list.size(); i++) {
            //put操作
            if(list.get(i)[0]==1){
                //若map中存在key,将节点移动到新的双向链表，更改节点val值和fre值
                if(map.containsKey(list.get(i)[1])){
                    Node node=map.get(list.get(i)[1]);
                    freMap.get(node.fre).removeNode(node);
                    if(freMap.get(node.fre).isEmpty()) minFre+=1;
                    node.fre+=1;
                    //若freMap中不存在对应频次双向链表初始化一个
                    if(!freMap.containsKey(node.fre)){
                         freMap.put(node.fre,new DoubleLinkedList());
                    }
                    freMap.get(node.fre).addNodeToHead(node);
                    node.val=list.get(i)[2];
                }else{
                    //若map中不存在key,若满了需要在双向链表中删除最低频次的节点，并在map删除对应键值对
                    if(capacity==k){
                        map.remove(freMap.get(minFre).tail.pre.key);
                        freMap.get(minFre).deleteTail();
                        capacity--;
                    }
                    Node node=new Node(list.get(i)[1],list.get(i)[2],1);
                    map.put(list.get(i)[1],node);
                    if(!freMap.containsKey(node.fre)){
                        freMap.put(node.fre,new DoubleLinkedList());
                    }
                    freMap.get(node.fre).addNodeToHead(node);
                    minFre=1;
                    capacity++;
                }
            }else{
                //get操作
                //若map不存在key
                if(!map.containsKey(list.get(i)[1])){
                    res.add(-1);
                }else{
                    //若存在，返回key对应的val并移动节点
                    Node node = map.get(list.get(i)[1]);
                    res.add(node.val);
                    freMap.get(node.fre).removeNode(node);
                    node.fre+=1;
                    if(!freMap.containsKey(node.fre)){
                        freMap.put(node.fre,new DoubleLinkedList());
                    }
                    freMap.get(node.fre).addNodeToHead(node);
                }
            }
        }
        return res;
    }
}

class Node{
    int key;
    int val;
    int fre;
    Node pre;
    Node next;

    public Node(int key, int val, int fre) {
        this.key = key;
        this.val = val;
        this.fre = fre;
    }
}

class DoubleLinkedList{
    Node head;
    Node tail;

    public DoubleLinkedList() {
        this.head = new Node(0,0,0);
        this.tail = new Node(0,0,0);
        head.next=tail;
        head.pre=tail;
        tail.next=head;
        tail.pre=head;
    }

    public void removeNode(Node node){
        node.pre.next= node.next;
        node.next.pre=node.pre;
        node.next=null;
        node.pre=null;
    }

    public void addNodeToHead(Node node){
        node.next=head.next;
        node.pre=head;
        head.next=node;
        node.next.pre=node;
    }

    public void deleteTail(){
        tail.pre=tail.pre.pre;
        tail.pre.next=tail;
    }

    public boolean isEmpty(){
        if(head.next.next==head) return true;
        else return false;
    }
}

发表于 2022-05-19 17:05:05 回复(0)
Java
牛客196305255号头像 牛客196305255号 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Map<Integer,Node>map=new HashMap<>();
	    List<Node> list=new ArrayList<>();
	    Scanner sc=new Scanner(System.in);
	    int n=sc.nextInt();
	    int k=sc.nextInt();
	    for(int i=0;i<n;i++){
	        int op=sc.nextInt();
	        if(op==1){
	            int key=sc.nextInt();
		        int value=sc.nextInt();
		        if(map.containsKey(key)) {
		            Node node=map.get(key);
		            list.remove(node);
		            node.add();
                    node.setValue(value);
		            map.put(key, node);
		            list.add(node);
		        }else {
		            Node node=new Node(key,value);
		            map.put(key,node);
		            list.add(node);
		        }
                if(map.size()>k) {
	            	Collections.sort(list,new Comparator<Node>() {
						@Override
						public int compare(Node o1, Node o2) {
							return o1.getCount()-o2.getCount();
						}
	            	});
	            	Node node=list.remove(0);
	            	map.remove(node.getKey());
	            }
	       }else{
	             int key=sc.nextInt();
	             if(map.containsKey(key)){
                      Node node=map.get(key);
                      list.remove(node);
                      node.add();
                      map.put(key,node);
                      list.add(node);
                     System.out.println(node.getValue());
	 	          }else{
	 	              System.out.println("-1");
	 	         }
	        }
	   }
        sc.close();
    }
}
class Node {
	private int key;
	private int value;
	private int count;
	public Node(int key,int value) {
		this.key=key;
		this.value=value;
		count=1;
	}
	public void add() {
		count++;
	}
	
	public int getKey() {
		return key;
	}
	
	public int getCount() {
		return count;
	}
    public int getValue() {
		return value;
	}
	public void setValue(int value) {
		this.value=value;
	}
}

发表于 2021-02-03 20:58:11 回复(0)
提交观点

问题信息

哈希
上传者：小小
难度：
4条回答 2400浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号