implement lru cache in Python

To implement LRU cache in Python, you can use the OrderedDict data structure from the collections module.

Example 1

Here’s an example implementation:

from collections import OrderedDict

class LRUCache:

    # initialising capacity
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    # we return the value of the key
    # that is queried in O(1) and return -1 if we
    # don't find the key in out dict / cache.
    # And also move the key to the end
    # to show that it was recently used.
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        else:
            self.cache.move_to_end(key)
            return self.cache[key]

    # first, we add / update the key by conventional methods.
    # And also move the key to the end to show that it was recently used.
    # But here we will also check whether the length of our
    # ordered dictionary has exceeded our capacity,
    # If so we remove the first key (least recently used)
    def put(self, key: int, value: int) -> None:
        self.cache[key] = value
        self.cache.move_to_end(key)
        if len(self.cache) > self.capacity:
            self.cache.popitem(last = False)

if __name__ == "__main__":
cache = LRUCache(3)
cache.put(1, 1)
print(cache.cache)
cache.put(2, 1)
print(cache.cache)
cache.get(1)
print(cache.cache)
cache.put(3, 3)
print(cache.cache)
cache.get(2)
print(cache.cache)
cache.put(4, 4)
print(cache.cache)
cache.get(1)
print(cache.cache)
cache.get(3)
print(cache.cache)
cache.get(4)
print(cache.cache)

In this implementation, LRUCache is a class that takes a capacity as an argument. The cache attribute is an OrderedDict object that will store the key-value pairs in the cache.

The get method returns the value associated with the given key, and moves the key to the end of the cache dictionary to indicate that it has been accessed recently.

The put method adds a new key-value pair to the cache, and also moves the key to the end of the dictionary. If the cache has exceeded its capacity, the least recently used item is removed from the cache using the popitem method.

Example 2

import collections


class ListNode:

    def __init__(self, key, val):
        self.val = val
        self.key = key
        self.next = None
        self.prev = None


class LinkedList:

    def __init__(self):
        self.head = None
        self.tail = None

    def insert(self, node):
        if self.head is None:
            self.head = node
        else:
            self.tail.next = node
            node.prev = self.tail
        self.tail = node

    def delete(self, node):
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        del node


class LRUCache:

    def __init__(self, capacity):
        self.list = LinkedList()
        self.dict = {}
        self.capacity = capacity

    def _insert(self, key, val):
        node = ListNode(key, val)
        self.list.insert(node)
        self.dict[key] = node

    def get(self, key):
        if key in self.dict:
            val = self.dict[key].val
            self.list.delete(self.dict[key])
            self._insert(key, val)
            return val
        return -1

    def set(self, key, val):
        if key in self.dict:
            self.list.delete(self.dict[key])
        elif len(self.dict) == self.capacity:
            del self.dict[self.list.head.key]
            self.list.delete(self.list.head)
        self._insert(key, val)


class LRUCache2:
    def __init__(self, capacity):
        self.cache = collections.OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        val = self.cache[key]
        del self.cache[key]
        self.cache[key] = val
        return val

    def set(self, key, value):
        if key in self.cache:
            del self.cache[key]
        elif len(self.cache) == self.capacity:
            self.cache.popitem(last=False)
        self.cache[key] = value


if __name__ == "__main__":
    cache = LRUCache(3)
    # cache = LRUCache2(3)
    cache.set(1, 1)
    cache.set(2, 2)
    cache.set(3, 3)
    print(cache.get(1))
    cache.set(4, 4)
    print(cache.get(2))

Small world. Big idea!

• Welcome to visit the knowledge base of SRE and DevOps!
• License under CC BY-NC 4.0
• No personal information is collected
• Made with Material for MkDocs and generative AI tools
• Copyright issue feedback me#imzye.com, replace # with @
• Get latest SRE news and discuss on Discord Channel