1

我目前有一个自定义类的数组，如下所示：

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 中执行许多这些操作，而留下无用的算法。

我该怎么做才能对此进行排序？

4

3 回答 3

2

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

Knuth 第 1 卷中还有一个相当不错的算法，它不会提供真正的 LRU，但会及时稳定到一个非常好的近似值。它只是由一个位环组成：您在每次访问时设置项目的位，并且在寻找空闲插槽时扫描环，清除设置位，直到找到一个已经清除的位。这意味着它至少没有在环周围使用过一次。下次扫描时，从这次停止的地方开始。

于 2013-02-21T12:29:31.967 回答
1

而不是时间戳给每个“phy”对象一个唯一的值，每次分配它时都会增加。

所以做这样的事情：

class phy {
   private static int uniqueIdentifier = 0;

   private int timestamp;

   // Or give it a new (proper) name
   void updateTimestamp() {
       timestamp = uniqueIdentifier;
       uniqueIdentifier++;
   }
}

每次更新“时间戳”时，您都会分配一个新的（更高/最高）数字，您可以使用它来查找最近最少使用的“phy”。

注意：如果您有多个线程，则需要一些同步以防止uniqueIdentifier同时访问（导致非唯一timestamp值）。

于 2013-02-21T12:32:24.150 回答
1

尝试使用LinkedHashMap来实现它怎么样？

查看此和此以获取有关如何实现它的示例

于 2013-02-21T12:33:30.700 回答