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?

user207421 · Accepted Answer · 2013-02-22T00:40:28.047

2

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.

edited Feb 22 '13 at 00:40

answered Feb 21 '13 at 12:29

user207421

305,947
44
307
483

Int he case that the array is big e.g. 256 would just have preformance effect? – Lemex Feb 21 '13 at 12:32
@LmC Of course, but that's just a data structure problem. You can use e.g. a `LinkedHashMap` instead of an array. There are many possibilities. – user207421 Feb 22 '13 at 00:37

score 1 · Answer 2 · answered Feb 21 '13 at 12:32

1

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).

answered Feb 21 '13 at 12:32

Veger

37,240
11
105
116

This sounds dumb... But do remove the least recent used e.g. The higest unqiueIdentifer or the lowest? – Lemex Feb 21 '13 at 12:40
The `uniqueIdentifier` is basically the same as your timestamp, but independent on the accuracy of the measured time (or anything else for that matter). It just increases every time you update a timestamp. Without adding any overhead of moving around the `phy` items in your array. – Veger Feb 21 '13 at 12:47

score 1 · Answer 3 · edited May 23 '17 at 12:13

1

How about trying to implement it using a LinkedHashMap?

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

edited May 23 '17 at 12:13

Community

1
1

answered Feb 21 '13 at 12:33

Sean Landsman

7,033
2
29
33

LRU Algorithm In Java

3 Answers3