Возможно ли сделать эффективный кеш, который будет и иметь операции find(key)

Question

Возможно ли сделать эффективный кеш, который будет и иметь операции find(key)

-> value*
insert(key, value)
и удалять элементы, которыми не пользовались N времени? Это не lru, казалось бы немного другое, но эффективно никак не выходит это сделать

#c++ #embedded #programming #russian

0

08.08.2023

9 ответов

21 просмотр

Aleksander Spichak

Это назвается timed lru или lru with ttl

0

08.08.2023

Dmitriy [Отпуск]

Можно. Классический LRU на хэшмапе + списке/деке/векторе (список удобен для интрузивности) + таймер

0

08.08.2023

Kelbon Автор вопроса

Anatoliy Tomilov [Russia]
очередь на std::list-е + std::unordered_map<typena...

это типичный лру кеш

0

08.08.2023

Kelbon Автор вопроса

Aleksander Spichak
Это назвается timed lru или lru with ttl

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

0

08.08.2023

Anatoliy Tomilov [Russia]

Kelbon
там нет изменения времени, там фиксированный отрез...

несколько раз наблюдал в проде такое решение: заводится 2 контейнера. В первом — элементы со временем жизни от 0 до ttl/2, во втором — от ttl/2 до ttl. Контейнеры свапаются и второй чистится. Время жизни от ttl/2 до ttl. Можно увеличить количество контейнеров и организовать кольцевой список, но find будет работать пропорционально дольше.

0

08.08.2023

Dmitriy [Отпуск]

Kelbon
там нет изменения времени, там фиксированный отрез...

Это и есть разновидность times lru

0

08.08.2023

Dmitriy [Отпуск]

Anatoliy Tomilov [Russia]
несколько раз наблюдал в проде такое решение: заво...

А зачем так сложно?

0

08.08.2023

Anatoliy Tomilov [Russia]

Dmitriy [Отпуск]
А зачем так сложно?

как раз просто.

0

08.08.2023

Anatoliy Tomilov [Russia] · Accepted Answer

очередь на std::list-е + std::unordered_map<typename std::list<T>::iterator, Timestamp, Hash, Equal>, где Hash и Equal — transparent и Equal умеет сравнивать typename std::list<T>::iterator и T как lhs vs rhs и rhs vs lhs. через slice или node в конец листа можно перемещать. Всё везде O(1) в среднем, если запросы приходят равномерно (а они приходят равномерно за большой интервал времени)

170 похожих чатов

Возможно ли сделать эффективный кеш, который будет и иметь операции find(key)

9 ответов

Похожие вопросы