LRU Cache Python: реализация и применение

Лучший Python LRU (Least Recently Used) Cache

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

1. Использование OrderedDict:

Мы можем использовать OrderedDict из стандартной библиотеки Python для хранения элементов кеша. OrderedDict - это подкласс словаря, который сохраняет порядок добавления элементов. Мы будем использовать этот факт, чтобы отслеживать, какие элементы были недавно использованы.

2. Создание класса LruCache:

Мы можем создать класс LruCache, который будет содержать OrderedDict и другие методы для работы с кешем. Например, метод get(key) будет проверять наличие элемента в кеше и возвращать его значение, а также обновлять порядок добавления элементов. Метод put(key, value) будет добавлять новый элемент в кеш и удалять наименее недавно использованный элемент, если кеш достиг предела.

3. Пример кода:


from collections import OrderedDict

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

    def get(self, key):
        if key in self.cache:
            value = self.cache[key]
            del self.cache[key]
            self.cache[key] = value
            return value
        return None

    def put(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

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


cache = LruCache(10)

cache.put("key1", "value1")
cache.put("key2", "value2")
cache.put("key3", "value3")

print(cache.get("key1"))  # Выводит "value1"
print(cache.get("key4"))  # Выводит None, так как элемент не существует в кеше

В данном примере мы создаем LRU кеш с емкостью 10 элементов. Затем мы добавляем несколько элементов в кеш с помощью метода put(). Затем мы используем метод get() для получения значения элемента по ключу.