Постановка проблемы
Наименее недавно использовавшиеся (LRU) — это распространенная стратегия кэширования. Он определяет политику удаления элементов из кеша, чтобы освободить место для новых элементов, когда кеш заполнен, что означает, что сначала отбрасываются наименее использованные элементы.
Давайте рассмотрим пример кеша, в котором есть емкость 4 элемента. Кэшируем элементы 1, 2, 3 и 4.
На диаграмме выше представлено состояние кеша после первого доступа ко всем четырем элементам. Теперь нам нужно кэшировать еще один элемент «5».
В кэше LRU мы удаляем наименее использованный элемент (в данном случае «1») на случай, если необходимо кэшировать новый элемент. Теперь «2» следует исключить, если необходимо кэшировать новый элемент. Посмотрим, что произойдет при повторном доступе к «2».
Теперь «3» становится следующей в строке, которая будет удалена из кеша..
Подсказка
- Двусвязный список
- Хеширование
- Подумайте о выселениях
Попробуйте сами
- путь> C ++
- путь> C ++
- путь> C ++
- Java
- Java
- Python
- Python
- JavaScript
- JavaScript
- Ruby
- Ruby
//простой однопоточный класс LRUCacheclass LRUCache {unordered_map кеш; //каждая запись в связанном списке LinkedList cache_val; int емкость; //общая емкость public: LRUCache (int capacity) {this-> capacity = capacity; } ~ LRUCache () {for (auto & t: cache) {удалить t.second; }} int get (int key) {//ЗАДАЧА: Запись - Ваш - Код return -1; } void set (int key, int value) {//TODO: Write - Your - Code} string print () {string result = ""; for (auto & x: cache) {result + = "(" + std :: to_string (x.first) + "," + std :: to_string (x. второй-> значение) + "),"; } вернуть результат; }};
Решение
- C ++
- путь> C ++
- C ++
- Java
- Java
-
Python
- Python
- JavaScript
- JavaScript
- Ruby
- Ruby
//Операции со связанными списками//void add_at_tail (int val) //void delete_node (ListNode * node)//void delete_from_head ()//void delete_from_tail ()//ListNode * get_head ()//void set_head (ListNode * node)//ListNode * get_tail ()//void set_tail (ListNode * node)//простой однопоточный LRUCacheclass LRUCache {unordered_set cache; //каждая запись в связанном списке - это значение элемента LinkedList cache_val; int емкость; //общая емкостьpublic: LRUCache (int capacity) {this-> capacity = capacity; } ~ LRUCache () {cache.clear (); } ListNode * получить (int val) {auto p = cache.find (val); если (p == cache.end ()) {вернуть nullptr; } еще {ListNode * я = cache_valval.get_head (); while (i! = nullptr) {if (i-> value == val) {return i; } я = я-> следующий; }}} void set (int value) {ListNode * check = get (значение); if (check == nullptr) {if (cache.size ()> = емкость) {cache_vals.add_at_tail (значение); int head_val = cache_vals.get_head () -> значение; cache.erase (head_val); cache_valals.delete_from_head (); } еще {cache_vals.add_at_tail (значение); cache.insert (значение); }} else {if (check == cache_vals.get_tail ()) {return; } if (check == cache_vals.get_head ()) {cache_vals.add_at_tail (проверка-> значение); cache_valals.delete_from_head (); возвращаться; } if (check-> prev! = nullptr) {check-> prev-> next = check-> next; } if (check-> next! = nullptr) {check-> next-> prev = check-> prev; } cache_valval.add_at_tail (проверка-> значение); удалить чек; }} void print () {ListNode * i = cache_val. get_head (); в то время как (я! = nullptr) {cout значение следующий; } cout
Объяснение решения
Сложность времени выполнения
get (hashset): O (1) в среднем случае, O (n) в худшем случае
set (hashset): Константа, O (1)
удаление в заголовке при добавлении нового элемента (связанный список): Константа, O (1)
поиск удаление и добавление в хвост (связанный список): O (n)
Сложность: O (n)
Сложность памяти
Линейный , O (n), где n — размер кеша.
Анализ решения
Кэширование — это метод хранения данных в более быстром хранилище ( обычно RAM), чтобы быстрее обслуживать будущие запросы. Ниже приведены некоторые распространенные примеры использования кеша:
- Кэш процессора используется для более быстрого чтения данных из основной памяти (ОЗУ).
- Кэш в ОЗУ может использоваться для хранения части данных на диске в ОЗУ и более быстрого обслуживания будущих запросов.
- Сетевые ответы можно кэшировать в ОЗУ, чтобы избежать слишком большого количества сетевых вызовов.
Однако хранилище кеша обычно недостаточно велико для хранения полного набора данных. Поэтому нам нужно удалять данные из кеша всякий раз, когда он заполняется. Существует ряд алгоритмов кэширования для реализации политики вытеснения кеша. LRU — очень простой и часто используемый алгоритм. Основная концепция алгоритма LRU состоит в том, чтобы удалить самые старые данные из кеша для размещения большего количества данных.
Для реализации кэша LRU мы используем две структуры данных: хэш-карту и двусвязный список. Двусвязный список помогает поддерживать порядок выселения, а хэш-карта помогает выполнять поиск кэшированных ключей O (1). Вот алгоритм для кеширования LRU.
Если элемент существует в hashmap, переместите доступный элемент в конец связанного списка, в противном случае, если требуется выселение, т.е. кеш уже заполнен Удалите заголовок элемент из двусвязного списка и удалить его запись хэш-карты Добавить новый элемент в конец связанного списка и в hashmapGet из кэша и возврата
Обратите внимание, что двусвязный список используется для отслеживания элементов, к которым осуществлялся последний доступ. Элемент в конце двусвязного списка — это элемент, к которому последний раз осуществлялся доступ. Все вновь вставленные элементы (вставленные) идут в конец списка. Точно так же любой элемент, к которому осуществляется доступ (в операции получения), попадает в конец списка.
