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.