LRU Cache: Understanding & Implementing the Algorithm for Better Website Performance

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

CLR (Cache LR) - циклический буфер - карта на страницах, позволяющая поддерживать часто используемые значения длиной LRU, — алгоритм замещения страниц. Алгоритм используется, например, в планировщике потоков CLR.

Простой способ реализовать LRU Cache - использовать словарь (dictionary) и связанный список (linked list). Словарь хранит значения кэша, а связанный список сохраняет порядок, в котором элементы были доступны. Каждый раз, когда происходит доступ к элементу, мы помещаем его в начало связанного списка. Когда мы должны удалить элемент из кэша, мы просто удаляем последний элемент списка.

Вот пример кода на Python, демонстрирующий реализацию LRU Cache с помощью словаря и связанного списка:

class LRUCache:
    
    def __init__(self, capacity: int):
        self.cache = {}
        self.capacity = capacity
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add(node)
            return node.value
        return -1
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._add(node)
        if len(self.cache) > self.capacity:
            node = self.head.next
            self._remove(node)
            del self.cache[node.key]
    
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _add(self, node):
        node.prev = self.tail.prev
        self.tail.prev = node
        node.prev.next = node
        node.next = self.tail
    
class Node:
    
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

В этом примере мы создаем класс LRUCache, который принимает размер кэша в качестве параметра и имеет два метода - get и put. Мы также создаем класс Node, который представляет каждый элемент в связанном списке.

Метод get проверяет наличие ключа в словаре. Если ключ присутствует, мы извлекаем элемент из списка, перемещаем его в начало и возвращаем значение. Если ключ отсутствует, возвращаем -1.

Метод put добавляет новый элемент в кэш. Если ключ уже присутствует, мы удаляем элемент из списка и добавляем в начало. Если кэш уже достиг своей максимальной емкости, мы удаляем последний элемент из списка и словаря.

Это простой пример, и есть множество других способов реализации LRU Cache в зависимости от языка программирования и требований. Однако, словарь и связанный список являются ключевыми элементами в любой реализации.