java - Java中的LRU算法

我目前有一个自定义类的数组，看起来像：

Phy[] memory = new Phy[256];

在我的Phy类中，我具有以下功能：


获取时间戳（返回时间戳）
更新时间戳（使用系统时间，从1970年开始获取毫秒并进行设置）


当涉及到LRU部分以查找LRU类时，我要做的是：

public int getLeastRecentlyUsed(){
    long leastUsed = memory[0].getTimeStamp();
    int  leastUsedPosition = 0;
    for(int i = 0; i < memory.length; i++){
        if(memory[i].getTimeStamp() < leastUsed){
            leastUsed = memory[i].getTimeStamp();
            leastUsedPosition = i;
        }
    }
    return leastUsedPosition;
}

基本上是寻找最旧的时间戳。

我刚刚意识到的问题是，处理器可以在MS中完成许多这些操作，而无需使用无用的算法。

我该怎么办？

最佳答案

您不需要为此设置时间戳。每次使用时，只需将其移动到列表的开头即可。然后，平均而言，LRU项在列表的末尾。

Knuth第1卷中还有一个相当不错的算法，它不能提供真正的LRU，但可以及时稳定下来以达到非常好的近似效果。它仅由一圈钻头组成：您在每次访问时都设置项目的钻头，当寻找空闲插槽时，您会扫描钻戒，清除设置的钻头，直到找到已经清除的钻头。这意味着它至少没有在环上至少旅行过一次。下次扫描时，请从这次停止的地方开始。

关于java - Java中的LRU算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15002262/