堆栈溢出的新手,所以请不要介意我以菜鸟的方式问这个问题。我正在尝试使用链表实现 LRU 缓存,我在这里看到了使用 linkedHashMap 和其他数据结构的其他实现,但对于这种情况,我正在尝试使用链表创建最佳优化版本,正如我在技术期间被问到的那样圆形。
我将此处的缓存大小限制为 3
- 有什么方法可以更好地优化这个 LRU 实现吗?
此实现的时间复杂度是多少?如果不考虑只是打印 linkedList 中的值的 for 循环,它的数量级会是 O(N) 吗?
public class LRU { public static void main(String[] args) { LinkedList list = new LinkedList(); int[] feed = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 }; for (int i = 0; i < feed.length - 1; i++) { if (list.size() <= 2) { list.add(feed[i]); System.out.println(); System.out.println("Added " + feed[i]); System.out.println("size of list is " + list.size()); System.out.print("this is list "); for (int k = 0; k < list.size(); k++) { System.out.print(" " + list.get(k)); } } System.out.println(); if (list.size() >= 3) { System.out.println(); System.out.println("feed is *" + feed[i + 1] + "*"); Integer value1 = (Integer) list.get(0); Integer value2 = (Integer) list.get(1); Integer value3 = (Integer) list.get(2); if ((feed[i + 1] != value1) || (feed[i + 1] != value2) || (feed[i + 1] != value3)) { list.removeLast(); list.addLast(feed[i + 1]); list.set(0, value2); list.set(1, value3); list.set(2, feed[i + 1]); } if (feed[i + 1] == value1) { list.removeLast(); list.addLast(value1); list.removeFirst(); list.addFirst(value2); list.set(1, value3); } if (feed[i + 1] == value2) { list.removeLast(); list.addLast(value2); list.set(1, value3); list.removeFirst(); list.addFirst(value1); } if (feed[i + 1] == value3) { list.set(0, value1); list.set(1, value2); } } System.out.println("Current elements in cache at " + i); for (int t = 0; t < list.size(); t++) { System.out.print(" " + list.get(t)); } System.out.println(); } System.out.println(); System.out.println("------------------------------"); System.out.println("current elements in cache "); for (int i = 0; i < list.size(); i++) { System.out.print(" " + list.get(i)); } } }
最佳答案
首先你要定义一个接口(interface)。现在我不知道你应该如何使用你的缓存或者事实上你在做什么。尝试实现以下类:
class LRUCache {
final int size;
Cache(int size){
this.size = size;
}
void put(String key, Integer value){
//
}
Integer get(String key){
//
}
}
编辑(对评论的回复):
无论问题是什么,第一步都是定义接口(interface)(我指的不是 Java 接口(interface),而是传达正在发生的事情的东西)。对于您的情况,请尝试实现此操作。
class MRU {
final int size;
MRU(int size){
this.size = size;
}
void put(Integer value){
//
}
Set<Integer> mostRecentlyUsed(){
//
}
}
关于Java LRU 缓存使用 LinkedList,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25055210/