Реалізація кешу LRU зазвичай передбачає використання комбінації структур даних. Загальний підхід полягає у використанні подвійного зв’язаного списку для підтримки порядку елементів на основі актуальності доступу та хеш-карти для досягнення постійного доступу до будь-якого елемента в кеші.
Одним із способів реалізації кешу LRU в Python є використовувати комбінацію двозв’язаного списку та хеш-карти. Елемент «голова» подвійно зв’язаного списку вказуватиме на останній використаний запис, а «хвіст» вказуватиме на запис, який використовувався найменше.
Підхід до реалізації LRU дуже простий ми збираємося використовувати двозв’язаний список і хеш-таблицю. Зв’язаний список використовується тут, щоб ми могли легко видалити дані, які використовувалися найменше, і легко додати нові дані до пам’яті, а дані, які найчастіше використовуються, – на початку зв’язаного списку.
Кеш можна додати в пам’ять поряд із сервером додатків. Запит користувача зберігатиметься в цьому кеші, і щоразу, коли той самий запит надходить знову, він повертатиметься з кешу. Для нового запиту дані будуть отримані з диска, а потім повернуті.
Для реалізації кешу LRU ми використовуємо дві структури даних: хеш-карту та подвійний зв’язаний список. Двозв’язаний список допомагає підтримувати порядок виселення, а хеш-карта допомагає з O(1) пошуком кешованих ключів.
Алгоритм ЛРУ Крок 1: визначте розмір таблиці сторінок (кількість сторінок, які можна одночасно зберігати в пам’яті). Крок 2: Ініціалізуйте дві змінні: помилки сторінки та звернення до сторінки, обидві спочатку встановлені на 0. Крок 3: Ініціалізуйте порожній список, щоб утримувати сторінки, які зараз знаходяться в пам’яті. Крок 4: Перейдіть по посилальному рядку.