How To Implement Cache LRU With Swift
Algorithms and Data Structures. It’s the basis of computer science and a very huge topic. In this article, we are going to cover only a little piece: Cache LRU.
A cache LRU (Least Recently Used) is similar to a dictionary. It stores data associated to a key. The difference between a dictionary and a Cache is that the latter has a limited capacity. Every time we reach the capacity, the Cache deletes the least recently used element.
In this article, we are going to see how to implement a Cache LRU with Swift.
First of all, we must understand what data structures we should use to implement our Cache LRU. There are different ways to implement it. In this version, we will use:
- Doubly Linked List: This is the core of our implementation. We need this list to store the elements of our cache. We don’t use an Array because it would be slower. The Cache LRU policy is to move the elements recently used in the head very often. If we move an element in the head—at the index
0—in an array, we should perform a shift to right for all the other elements.
Dictionary<Key, ListNode>: The problem of using a doubly linked list is that its lookup complexity is O(n). We can solve this bottleneck using a dictionary—which has a lookup complexity of O(1). We’ll use this dictionary to store the nodes of our list.
In the next section, we are going to see how to implement the doubly linked list. If you already know it, feel free to jump at the section
Doubly Linked List
For this article, we don’t need a complete doubly linked list implementation. For this reason, we’ll implement only the methods used in the Cache.
The first step is to create a new class
DoublyLinkedList which accepts a generic value
T to store inside the nodes:
Then, we must create a class for the nodes:
In this implementation, we use a nested
Node class. If you use a Swift version older than 3.1, you must create this class outside
DoublyLinkedList. Nested classes with generic values are supported from Swift 3.1.
Then, we must provide the information of how many elements are stored in the list:
The operations on a linked list may be sometimes complex to implement. For this reason, we can store the first and last elements to keep our life easier:
Now, we can start implementing the list methods:
We need a method to add a new element in the list. We add it in the head to be compliant with the Cache LRU policy—a new element is the recently used:
The concept of a Cache LRU is keeping the recently element used at the beginning of our list. For this reason, we need a method to move a node at the head:
When our Cache is full, we need a method to remove the last element—which is the least recently used:
- The value of this
tailis not the same of
self.tail. It’s the value of the old
tailwhich comes from the optional binding in the
guardat the beginning of this method.
Finally, we can add a typealias for our
Node type to use in the Cache implementation:
The final version of our list implementation should be like this:
It’s time to implement our Cache. We can start creating a new
The generic value
Key must be
Hashable since it’s the key of the value stored in the doubly linked list.
A Cache stores data associated to keys like a dictionary. Unfortunately, our doubly linked list accepts only a value
payload and not also a key. To solve this problem, we can create a struct which wraps the value and its key. In this way, our list nodes will store the object
CachePayload which contains both value and key:
Then, we should add the two data structures—a doubly linked list and a dictionary:
As we saw in
Introduction, Cache LRU has a limited capacity. We can inject this capacity in the
init method and store it in a private property:
We use the method
max to avoid invalid
capacity values less than zero.
Now, we can implement the two Cache methods to
set the elements:
With the method
set, we can add/update an element for a specific key. The value is always moved at the beginning of the list as recently used element:
- Create a payload object to wrap
valueto be stored in the list.
- If the list already stores an element for that specific key, we update the value and move it at the beginning of the list. Otherwise, we create a new node and add it as head of the list.
- If we exceeded the capacity of the cache adding the new element, we remove the last element of the list.
With the method
get, we can retrieve an element for a specific key. Every time we retrieve an element, it is moved at the beginning of the list as recently used element:
The final version of our Cache implementation should be this:
We can use this cache like this:
You can find a Gist with the Cache LRU implementation here.
That’s all for our Cache LRU.
Nowadays, we have a lot of memory available for our Apps. Despite this, we may need a Cache with a limited capacity to save memory space. For example, when we have to cache objects which are space-consuming like the images.
I’ve figured out that Array is faster than linked list. Since the pure version of Cache LRU uses a doubly linked list, I leave the current implementation. But, keep in mind that with a Swift Array we would have a faster implementation.
You can watch an interesting video about Array and linked list here: