LRU Cache in Python: Optimizing Your Code with Caching Strategies

LRU кеш (Least Recently Used Cache) - это способ кэширования данных в программе, при котором сохраняется определенное количество наиболее часто используемых элементов. Если в кеше нет места, то будут удалены элементы, которые были наименее использованы. LRU кеш обеспечивает быстрый доступ к данным и ускоряет выполнение программы.

В Python существует несколько библиотек, которые уже содержат реализацию LRU кеша, например, functools.lru_cache.

Однако, если необходимо создать свою реализацию LRU кеша в Python, можно использовать OrderedDict.

Пример реализации LRU кеша на Python с использованием OrderedDict:

python
from collections import OrderedDict
class LRUCache:
    
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity
    
    def get(self, key):
        if key not in self.cache:
            return -1
        value = self.cache.pop(key)
        self.cache[key] = value
        return value
    
    def put(self, key, value):
        if key in self.cache:
            self.cache.pop(key)
        elif len(self.cache) == self.capacity:
            self.cache.popitem(last=False)
        self.cache[key] = value

В данной реализации, при добавлении/обновлении элемента в кеш, если он уже существует, он удаляется. Если размер кеша больше заданной емкости, удаляется элемент, который был добавлен наименее недавно (т.е. самый старый). При каждом обращении к элементу в кеше, он перемещается в конец списка, чтобы мы могли отследить, какие элементы были использованы давно и какие можно удалить при необходимости.

Пример использования:

python
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # вернет 1
cache.put(3, 3)
print(cache.get(2)) # вернет -1, так как элемент с ключом 2 был удален из-за маленькой емкости
cache.put(4, 4)
print(cache.get(1)) # вернет -1, так как элемент с ключом 1 находится в начале списка и был удален при добавлении новых элементов
print(cache.get(3)) # вернет 3
print(cache.get(4)) # вернет 4