LRU Algorithm In Java

Question

I currently have an array of a custom class which looks like:

Phy[] memory = new Phy[256];

Within my Phy class I have the following functions:

• Get time stamp (Returns time stamp)
• Update time stamp (Use system time, gets the ms since 1970 and sets it)

When it comes to the LRU part to find the LRU class I do:

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;
}

Which basically looks for the oldest time stamp.

The problem I have just realised is that the processor can do many of these operations in a MS leaving with a useless algorithm.

What can I do to sort this?

Answer 1

You don't need timestamps for this. Just move each item to the head of the list every time it is used. Then the LRU item is at the end of the list, on the average.

There's also a rather good algorithm in Knuth volume 1 that doesn't deliver true LRU but settles down in time to a very good approximation. It just consists of a ring of bits: you set the item's bit on every access, and when looking for a free slot you scan the ring, clearing set bits until you find one already clear. That means it hasn't been used for at least one trip right around the ring. Next time you scan, start from the place where you stopped this time.

Answer 2

Instead of timestamps give each 'phy' object a unique value, that is increased each time it is assigned.

So do something like this:

class phy {
   private static int uniqueIdentifier = 0;

   private int timestamp;

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

Each time you update the 'time'stamp you assign a new (higher/highest) number, which you can use to find the least recent used 'phy'.

Note: If you have multiple threads, you would need some synchronization to prevent access to the uniqueIdentifier at the same time (resulting in non-unique timestamp values).

Answer 3

How about trying to implement it using a LinkedHashMap?

Checkout this and this for examples on how you could implement it