Understanding LRU Algorithm

Question

I am trying to understand LRU and its making no sense to me. If I understand it then it will be easier for me to code. Can someone walk me through the steps? Like,

1. If the reference string you are currently at is in the array then do you increment to the next space?
2. When you check to see if somethings in the buffer then do we need to scan where we are at or the whole array?

I just cant seem to follow along. How is it keeping track of least recently used? Shouldnt the least recently used be the one after the index your at?

Answer 1

An LRU is typically put in a list. When an item is accessed, remove it from the list (if it's there), and push it to the back. The back of the list is the Most Recently Used. Because you're continually moving used items to the back of the list, the least used ones end up naturally at the front of the list. When there's not enough room, you pop from the front.

Answer 2

Store two items for each "item". The value (of course) and the "time" which is an ever-increasing integer.

So, using your data, assuming that 1 through 4 were accessed in order:

(1, 1), (2, 2), (3, 3), (4, 4)

access "1" (sorted by time for clarity, time = 5)

(2, 2), (3, 3), (4, 4), (1, 5)

access "2" (sorted by time for clarity, time = 6)

(3, 3), (4, 4), (1, 5), (2, 6)

access "5" which will not be found, causing a cache miss. To find the "space" to store the "5", we need to flush the Least Recently Used (LRU). This means dropping "3". Note that time = 7.

(4, 4), (1, 5), (2, 6), (5, 7)

access "1" (sorted by time for clarity, time = 8)

(4, 4), (2, 6), (5, 7), (1, 8)

access "2" (sorted by time for clarity, time = 9)

(4, 4), (5, 7), (1, 8), (2, 9)

access "3" which will not be found, causing a cache miss. To find the "space" to store the "3", we need to flush the Least Recently Used (LRU). This means dropping "4". Note that time = 10.

(5, 7), (1, 8), (2, 9), (3, 10)

access "4" which will not be found, causing a cache miss. To find the "space" to store the "4", we need to flush the Least Recently Used (LRU). This means dropping "5". Note that time = 11.

(1, 8), (2, 9), (3, 10), (4, 11)

access "5" which will not be found, causing a cache miss. To find the "space" to store the "5", we need to flush the Least Recently Used (LRU). This means dropping "1". Note that time = 12.

(2, 9), (3, 10), (4, 11), (5, 12)

Now that you know how the item to be flushed was selected, and have a working example, the flushing of the item without moving it around in the array is up to you to implement.

--- Edited With additional explanation ---

Ok, the idea of showing stuff in list form seems to have raised a few questions, so I'll show it in array form

Access 1, cache miss, empty slot available, store in first available slot

Value   Age
1       1
---     ---
---     ---
---     ---

Access 2, cache miss, empty slot available, store in first available slot

Value   Age
1       1
2       2
---     ---
---     ---

Access 3, cache miss, empty slot available, store in first available slot

Value   Age
1       1
2       2
3       3
---     ---

Access 4, cache miss, empty slot available, store in first available slot

Value   Age
1       1
2       2
3       3
4       4

Access 1, cache hit, update access time

Value   Age
1       5
2       2
3       3
4       4

Access 2, cache hit, update access time

Value   Age
1       5
2       6
3       3
4       4

Access 5, cache miss, no available empties, discard and replace "least recently used"

Value   Age
1       5
2       6
5       7
4       4

Access 1, cache hit, update access time

Value   Age
1       8
2       6
5       7
4       4

Access 2, cache hit, update access time

Value   Age
1       8
2       9
5       7
4       4

Access 3, cache miss, no available empties, discard and replace "least recently used"

Value   Age
1       8
2       9
5       7
3       10

Access 4, cache miss, no available empties, discard and replace "least recently used"

Value   Age
1       8
2       9
4       11
3       10

Access 5, cache miss, no available empties, discard and replace "least recently used"

Value   Age
5       12
2       9
4       11
3       10

Answer 3

This is my simple sample c++ implementation for LRU cache, with the combination of hash(unordered_map), and list. Items on list have key to access map, and items on map have iterator of list to access list. So, every method calling is complexity O(1).

#include <list>
#include <unordered_map>
#include <assert.h>

using namespace std;

template <class KEY_T, class VAL_T> class LRUCache{
private:
        list< pair<KEY_T,VAL_T> > item_list;
        unordered_map<KEY_T, decltype(item_list.begin()) > item_map;
        size_t cache_size;
private:
        void clean(void){
                while(item_map.size()>cache_size){
                        auto last_it = item_list.end(); last_it --;
                        item_map.erase(last_it->first);
                        item_list.pop_back();
                }
        };
public:
        LRUCache(int cache_size_):cache_size(cache_size_){
                ;
        };

        void put(const KEY_T &key, const VAL_T &val){
                auto it = item_map.find(key);
                if(it != item_map.end()){
                        item_list.erase(it->second);
                        item_map.erase(it);
                }
                item_list.push_front(make_pair(key,val));
                item_map.insert(make_pair(key, item_list.begin()));
                clean();
        };
        bool exist(const KEY_T &key){
                return (item_map.count(key)>0);
        };
        VAL_T get(const KEY_T &key){
                assert(exist(key));
                auto it = item_map.find(key);
                item_list.splice(item_list.begin(), item_list, it->second);
                return it->second->second;
        };

};