Quickly i want to tell you about my approach , what DS we can use to implement in most efficient manner .
we can use Combination of Queue + HashMap Data Structure OR
Here algorithmic with explanation of DS
Why combination of two Data Structure ? Let me tell you how LRU works : LRU caches have a maximum number of data items that they will hold and these items are usually arranged in a some data structure (list or queue). When an item is added to the cache, and every time it is accessed after that, it is automatically moved to the head of the list. If the cache is full and a slot is required for a new item, the cache makes room by discarding the entry at the tail of the list - the least-recently used item. So we need to remove the Eldest entry from list/queue in the same in which inserted both queue and list provide this facility to , we need insert element at the head of queue/list and remove the element from tail or queue/ list , since queue itself require list to be implement , we can directly use LinkedList . we can do insert and remove in O(1) .
Now , Before Inserting entry in list or queue , we need to check if that entry alraedy exist in Cache or not , how we will do that , we need some DS again fro the same , HashMap is used for the same , that gurentte , get and set in O(1) .
As you asked in java , Java Provide the DS called LinkedHashMap that has both feature.
An Important feature of LinkedHashMap is that it provides the methodremoveEldestEntry (Map.Entry e) that remove the eldest entry from the cache when it becmoe full and a new entry need to be inserted .
In this section, you will learn about th least-recently- used (LRU) cache in Java. LRU Cache helps you how to use the buffer and how to limit or fixed the size of buffer and how to manage storing and retrieving process of the buffer which size is limited.
In this section, you can create a LRU(least-recently-used) Cache and manage it efficiently. Here the given program takes a in numeric input to fix the size of the LRU Cache. If your entry exceeds the size of the LRU Cache the the eldest element with key is removed. LRU Cache is implemented through
theLinkedHashMap class. LinkedHashMap holds values with unique key. You you store values with a duplicate key then the LinkedHashMap replace the old value of that key with the new value of the key.
theLinkedHashMap class. LinkedHashMap holds values with unique key. You you store values with a duplicate key then the LinkedHashMap replace the old value of that key with the new value of the key.
Code Description:
This program shows the object keys and values by using the LRU cache. Many methods and APIs which have been used in the following program are explained as follows:
LinkedHashMap:This is the class of the java.util.*; package. This class is also used for the implementing
the doubly linked list which tracks either insertion or access order. The put() method is used for the insertion process to the LinkedHashMap with the value and the unique key regarding the value.
put(Object key, Object value):This method has been used to add a value with it's unique key in the LRU Cache. This method of the LinkedHashMap class takes two argument in which first is the key and another is the value for the specified key.
Map.Entry:This interface returns the view of map of collection . The Map.Entry objects are valid only to the duration of the iteration. This is the nested class of the Map class from the java.util.*; package.
e.getKey():Above method of the Map.Entry class which returns the key corresponding to the value. Here 'e' is the instance of the Map.Entry class.
e.getValue():Above written is also a method of the Map.Entry class which returns the value corresponding to the key of the index of the LRU Cache.
Here is the code of program:
2 comments :
An More Illustrative Implementation
public class Cache {
private class CacheVal {
public int rank;
public Val val;
public CacheVal(int rank, Val val) {
this.rank = rank;
this.val = val;
}
}
public Cache(int limit) {
this.limit = limit;
}
public Val get(Key key) {
if (this.cache.containsKey(key)) {
CacheVal cacheVal;
// remove existing entry from ranked list
cacheVal = this.cache.get(key);
Key k = this.rankedList.remove(cacheVal.rank);
// add it to the top of the list
this.rankedList.addFirst(k);
return cacheVal.val;
} else {
return null;
}
}
public void set(Key key, Val val) {
// remove existing entry from ranked
if (this.cache.containsKey(key)) {
CacheVal oldVal;
oldVal = this.cache.get(key);
this.rankedList.remove(oldVal.rank);
}
// check if cache is full
if (this.cache.size() == this.limit) {
// make space in cache
Key toRemove = this.rankedList.removeLast();
this.cache.remove(toRemove);
}
// insert new element in cache and ranked list
CacheVal newVal = new CacheVal(0, val);
this.cache.put(key, newVal);
this.rankedList.addFirst(key);
}
private Map cache = new HashMap();
private LinkedList rankedList = new LinkedList();
private int limit;
}
I have another approach in C.
Please tell me whether it is efficient.
Take a double linked list. The head will always contain the most recently used page & tail will contain the least recently page..
A hash where page number will be used for indexing will be taken. Whenever, a page fault occurs i.e. page is not in the memory[the hash slot will be empty], We will create a new node in DLL, put it in the head & store its pointer in the hash.
At any time, if a page needs to be referenced, it will be searched in the hash. If its there, we need to change at most 6 pointers to attach it at the head of DLL.
reqPage->next->prev=reqPage->prev;
reqPage->prev->next=reqPage->next;
reqPage->next=head;
reqPage->prev=NULL;
head->prev=reqPage;
head=reqPage;
Post a Comment