Least Recently Used Cache
My next blog post will go through an application of the data structures I have discussed in my previous blog posts. This is the LRU Cache which stands for “Least Recently Used”. The cache has a specified capacity and we want to be able to look up values from the cache. If the capacity is reached, we need to get rid of the least recently used value to make room for the valueadded to the cache. If the key is already defined, we update the value associated with the key. The problem comes from Leetcode which can be accessed here => https://leetcode.com/problems/lru-cache/.
Lets get started. So, I saw this as an opportunity to practice my test driven development skills. We can set up unit testing using Mocha. In the project directory, we initial the npm package manager. We then install mocha locally.
npm init
npm install mocha -DSo, how do we implement the LRU cache? We can create a class for the LRU cache. What do we need to define in this class? We can define the cache as an object to take in key-value pairs and a capacity specified on instantiation. How do we keep track of which key-value pair is the least recently used? This is a good job for the queue data structure! We can define a queue to keep track of the least recently used key. In the index.js file, we define and export the LRUCache class as follows.
class LRUCache {
constructor() {
this.lruQueue = [];
this.lruCache = {};
this.capacity = capacity;
this.cacheLen = 0;
}
}module.exports = {
LRUCache
}
Lets set up the unit tests in the test/index.spec.js file. We can import the LRUCache class from the index.js file. As an initial test, let’s check if upon initialization the capacity of the cache is the capacity we specify.
const assert = require('assert');
const { LRUCache } = require('../index');describe('LRUCache capacity', () => {
it('initializing cache with capacity 2 should set cache capacity to 2', () => {
let cache = new LRUCache(2);
assert.equal(cache.capacity, 2);
})
})
Ok so we have a cache and a queue to manipulate so how are we going to approach this problem. We are going to define a put method that adds the key-value pair to the cache or updates the value in the cache. Also, a get method needs to be defined to pull the value from the cache for a given key. We would also need to define a function that updates the queue when the put or get method is called.
Lets look at the example given by Leetcode. A cache of capacity of 2 is initialized and we call the put method twice.
let cache = new LRUCache(2)
cache.put(1, 1);
cache.put(2, 2);The cache then becomes,
{ "1": 1, "2": 2 }If we call cache.get(1), we get the value of 1. The least recently used key becomes “2”. If we call cache.put(3, 3), the key “2” is evicted and the cache becomes,
{ "1": 1, "3": 3 }If we call cache.get(2), we get a value of -1 indicating that the key was not found. Hmmm. Let’s tackle the helper function first to update the queue. We need the function to add keys to the queue. If the key is already in the queue, the key needs to be moved to the back of the queue since it becomes the most recently used key. If the queue reaches capacity, we need to remove the most the least recently used key value. Let’s write appropriate tests for these cases.
describe('LRUQueue - update queue', () => {
it('adds the key to the empty queue', () => {
let cache = new LRUCache(2);
cache.updateQueue(1);
let result = [1];
assert.deepEqual(cache.lruQueue, result);
}) it('moves the existing key to the back of the queue', () => {
let cache = new LRUCache(2);
cache.updateQueue(1);
cache.updateQueue(2);
cache.updateQueue(1);
let result = [2, 1];
assert.deepEqual(cache.lruQueue, result);
} it('when at capacity, removes the least recently used key from the front of the queue', () => {
let cache = new LRUCache(2);
cache.updateQueue(1);
cache.updateQueue(2);
cache.updateQueue(3);
let result = [2, 3];
assert.deepEqual(cache.lruQueue, result);
}
});
How are going to approach the update function for the queue? When the queue contains the key, we will remove the key from the queue and add the key to the back of the queue. When the queue is at capacity, we remove the least recently used key from the front of the queue and add the key to the back of the queue. The implementation of the update queue function is as follows.
class LRUQueue { ... updateQueue = function(key) {
//if queue contains the key
if(this.lruQueue.includes(key)) {
//remove the key from the queue
let idx = this.lruQueue.indexOf(key);
this.lruQueue.splice(idx, 1);
}
//if queue is at capacity
if(this.lruQueue.length === this.capacity) {
//remove the least recently used key from the front
of the queue
this.lruQueue.shift();
} //add key to the back of the queue
this.lruQueue.psuh(key);
}
}
We implement this function in our index.js file and the tests we wrote all pass!
Let’s tackle the put method next. So, the put method will take in the key and the value. First, if the cache is at capacity and the key is not in the cache, we remove the least recently used key from the cache. Then, we update the value for the key or add the key-value pair to the cache. We then update the queue appropriately. Let’s write some tests for this.
describe('LRUCache - put function tests', () => {
it('adds the key-value to the empty cache', () => {
let cache = new LRUCache(2);
cache.put(1, 1);
let result = {"1": 1};
assert.deepEqual(cache.lruCache, result);
}); it('updates the value for existing key', () => {
let cache = new LRUCache(2);
cache.put(1, 1);
cache.put(1, 2);
let result = {"1": 2};
assert.deepEqual(cache.lruCache, result);
}); it('when the cache is at capacity, removes least recently used key and adds new key-value pair', () => {
let cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
let result = {"2": 2, "3": 3};
assert.deepEqual(cache.lruCache, result);
});
}
How are we going to approach the put function? Well, we can first check if the cache is at capacity. If the cache is at capacity and the key is not in the cache, we pull the least recently used key from the queue and delete the key-value pair from the cache. We then add the new key-value pair to the cache and update the cache with the new key. The update queue function abstracts away all the work of updating the key.
class LRUQueue {
... put = function(key, value) {
//if cache is at capacity and the key is not in the cache
if(this.lruQueue.length === this.capacity && !this.lruCache[key]) {
//remove the least recently used key from the cache
let lruKey = this.lruQueue[0];
delete this.lruCache[lruKey];
}
//update the key value pair
this.lruCache[key] = value;
//update the queue
this.updateQueue(key);
}
}
We implement this and all the tests pass! Moving forward.
Lets tackle the get function. So, the get function will take in the key and return the corresponding value. If the key does not exist in the cache, we return -1. If the key does exist, we update the queue accordingly. Let’s write some tests.
describe('LRUCache - get function tests', () => {
it('returns the value from the corresponding key', () => {
let cache = new LRUCache(2);
cache.put(1, 1);
let result = 1;
assert.deepEqual(cache.get(1), result);
}); it('returns -1 if the key does not exist in the cache', () => {
let cache = new LRUCache(2);
cache.put(1, 1);
let result = -1;
assert.deepEqual(cache.get(2), result);
}); it('returns the value from the corresponding key', () => {
let cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);
let result = [2, 1];
assert.deepEqual(cache.lruQueue, result);
});
});
The implementation of the get function is as follows. We first check if the key exists in the cache. If it does, we update the queue and return the key value.
class LRUQueue {
...
get = function(key, value) {
//if the key does not exist in the cache
if(!this.lruCache[key]) {
return -1;
}
this.updateQueue(key);
return this.lruCache[key];
}
}There you have it. My solution process for the least recently used cache problem using mocha unit testing. This solution is not the most performant solution, but it works. This shows a practical application of queues when storing values in a cache.
