Introduction:

In part 1 we talked about the basics and terminologies of cache and we have also shown replacement policies , in part 2 we implemented some of these famous replacement polices and now in this part we will continue talking about the implementation of two famous algorithms which are LFU and LRU. Again, the implementation in this article is for sake of demonstration and in order to use it (we just concentrate over the replacement algorithm and we will skip other things like loading data and so on), you will have to do some extra work but you can base your implementation over it.

Meet LFU Cache Implementation:

public synchronized Object getElement(Object key) {

Object obj;

obj = table.get(key);

if (obj != null) {
CacheElement element = (CacheElement) obj;
element.setHitCount(element.getHitCount() + 1);
return element.getObjectValue();
}
return null;

}

public final synchronized void addElement(Object key, Object value) {

Object obj;

obj = table.get(key);

if (obj != null) {
CacheElement element;

// Just replace the value.
element = (CacheElement) obj;
element.setObjectValue(value);
element.setObjectKey(key);

return;
}

if (!isFull()) {

index = numEntries;
++numEntries;
} else {
CacheElement element = removeLfuElement();
index = element.getIndex();
table.remove(element.getObjectKey());

}

cache[index].setObjectValue(value);
cache[index].setObjectKey(key);
cache[index].setIndex(index);
table.put(key, cache[index]);
}

public CacheElement removeLfuElement() {

CacheElement[] elements = getElementsFromTable();
CacheElement leastElement = leastHit(elements);
return leastElement;
}

public static CacheElement leastHit(CacheElement[] elements) {

CacheElement lowestElement = null;
for (int i = 0; i < elements.length; i++) {
CacheElement element = elements[i];
if (lowestElement == null) {
lowestElement = element;

} else {
if (element.getHitCount() < lowestElement.getHitCount()) {
lowestElement = element;
}
}
}
return lowestElement;
}
Analyzing LFU Cache Code (Talk Show):


Presenter: it is getting hotter and hotter now, our next contestant is LFU cache, please make some noise for it.

Audience began to scream for LFU which made LFU hesitated.

Hello, I am LFU, when the cache client want to add a new element and cache is full (no enough room for the new entry) I will have to kick out the least frequently used entry, by using the help of the removelfuElement method which will allow me to get the least frequently used element, after I get it, I will remove this entry and place the new entry

else {
CacheElement element = removeLfuElement();
index = element.getIndex();
table.remove(element.getObjectKey());

}

If we dived into this method…, I am saying if we dived into this method (still nothing happened)
LFU tried pressing the next button on the presentation remote control (to get the next presentation slide) but I didn’t work.

Ahh now we are talking, ok if we dived into this method we will see that the method is just getting the whole elements in cache by calling getElementsFromTable method and then returns the element with the least hit.

public CacheElement removeLfuElement() {

CacheElement[] elements = getElementsFromTable();
CacheElement leastElement = leastHit(elements);
return leastElement;
}
}

By calling leastHit method which loops over the cache elements and check if the current element has the least hit, if so, I will make it my lowestElement which I am going replace the new entry with.

public static CacheElement leastHit(CacheElement[] elements) {

CacheElement lowestElement = null;
for (int i = 0; i <>
CacheElement element = elements[i];
if (lowestElement == null)
{ lowestElement = element; }
else {

if (element.getHitCount() <>
{ lowestElement = element; }
}
}
return lowestElement;
}

LFU stopped talking and waited for any action from the audience and the only action it get was scratching heads (audience didn’t get some stuff).

One of the production team whispered to LFU cache and said: you didn’t mention how the lowest element will be distinguished from another element?

Then LFU cache started talking gain and said: By default when you add the element to the cache its hitCoint will be the same as the previous element so how do we handle the hit count thing?

Every time I encounter a cache hit I will increment the hit count of the entry and then return the entry the cache client asked for which would be something like that

public synchronized Object getElement(Object key) {

Object obj;

obj = table.get(key);

if (obj != null) {
CacheElement element = (CacheElement) obj;
element.setHitCount(element.getHitCount() + 1);
return element.getObjectValue();
}
return null;

}

Magnifying the Code:

Did anyone say magnification?