Реализация кэша LRU в Javascript
Java имеет LinkedHashMap, который получает вас на 99% к кешу LRU.
Существует ли реализация Javascript кэша LRU, предпочтительно из уважаемого источника, который:
- понятно
- эффективный (амортизированный O (1) get/put/delete)
? Я искал в Интернете, но не мог найти его; Я думал, что нашел один из Ajax Design Patterns, но он затушевывает метод sendToTail()
и имеет производительность O (n) (предположительно, поскольку очередь и ассоциативный массив разделены).
Я полагаю, что мог бы написать свой собственный, но я усвоил, что изобретать колесо для основных алгоритмов может быть опасно для одного здоровья:/
Ответы
Ответ 1
Это:
https://github.com/monsur/jscache
похоже, подходит вам, хотя setItem
(то есть put) является O (N) в худшем случае, что происходит, если кеш заполняется при вставке. В этом случае поиск кэша выполняется для очистки истекших элементов или наименее недавно используемых элементов. getItem
- это O (1), и истечение выполняется в операции getItem
(т.е. если элемент, который выдается, истек, удаляет его и возвращает null).
Код достаточно компактный, чтобы его было легко понять.
P.S. Возможно, было бы полезно добавить к конструктору опцию для указания fillFactor
, которая зафиксирована на 0,75 (что означает, что при очистке кеша размер уменьшается как минимум до 3/4-го от максимального размера)
Ответ 2
Это не так эффективно, как вы хотите, но оно компенсирует это простотой и удобочитаемостью. И во многих случаях это будет достаточно быстро.
Мне понадобился простой LRU-кеш для небольшого количества дорогостоящих операций (1 секунда). Я чувствовал себя лучше, когда вставлял копию небольшого кода, а не вводил что-то внешнее, но так как не нашел, то написал:
Обновление: теперь это намного более эффективно (и пространство, и время), так как я удалил массив, потому что Map сохраняет порядок вставки.
class LRU {
constructor(max=10) {
this.max = max;
this.cache = new Map();
}
get(key) {
let item = this.cache.get(key);
if (item) // refresh key
{
this.cache.delete(key);
this.cache.set(key, item);
}
return item;
}
set(key, val) {
if (this.cache.has(key)) // refresh key
this.cache.delete(key);
else if (this.cache.size == this.max) // evict oldest
this.cache.delete(this._first());
this.cache.set(key, val);
}
_first(){
return this.cache.keys().next().value;
}
}
Использование:
> let cache = new LRU(3)
> [1, 2, 3, 4, 5].forEach(v => cache.set(v, 'v:'+v))
> cache.get(2)
undefined
> cache.get(3)
"v:3"
> cache.set(6, 6)
> cache.get(4)
undefined
> cache.get(3)
"v:3"
Ответ 3
Об этом стоит упомянуть: https://github.com/rsms/js-lru
Основной набор функций - O (1), и код сильно прокомментирован (с искусством ASCII также!)
Ответ 4
Реализация monsur.com - это O (n) при вставке только потому, что она имеет элементы, которые на самом деле заканчиваются в реальном мире. Это не простой LRU. Если вы только заботитесь о сохранении последних использованных предметов без учета реального времени, это можно сделать в O (1). Очередь, реализованная как дважды связанный список, - это O (1) для вставки или удаления из конца, и это все, что вам нужно для кеша. Что касается поиска, хэш-карта, которая javascript делает патетически легкой, должна быть хорошей для почти O (1) поиска (при условии, что механизм javascript использует хороший хэш файл, и эта реализация зависит, конечно). Таким образом, у вас есть связанный список элементов с картой хэша, указывающей на элементы. Манипулируйте концы связанного списка по мере необходимости, чтобы поместить новые предметы и запрошенные элементы на одном конце и удалить старые элементы с другого конца.
Ответ 5
Это не кеш LRU, но у меня есть моя собственная связанная реализация карты. Поскольку он использует объекты JS как хранилище, он будет иметь схожие характеристики (объекты-обертки и хеш-функция придают производительность).
В настоящее время документация в основном несуществующая, но там связанный ответ SO.
Метод each()
будет передавать текущий ключ, текущее значение и логическое значение, указывающее, есть ли в качестве аргументов функции обратного вызова больше элементов.
В качестве альтернативы, петля может выполняться вручную через
for(var i = map.size; i--; map.next()) {
var currentKey = map.key();
var currentValue = map.value();
}
Ответ 6
Я знаю, что это старый вопрос, но добавление ссылки для будущего refrence.
Проверьте https://github.com/monmohan/dsjslib. В дополнение к некоторым другим структурам данных реализована реализация кэша LRU. Такие кеши (и это тоже) поддерживают двусвязный список записей кэша в порядке LRU, т.е. Записи перемещаются в голову по мере их доступа и удаляются из хвоста, когда они возвращаются (например, по истечении срока действия или из-за ограничения размера). Его O (1), поскольку он включает только постоянное количество манипуляций с указателями.
Ответ 7
Так как нам нужны операции чтения, записи, обновления и удаления в O (1), мы используем две структуры данных.
- Объект (или Карта) в JavaScript обеспечивает поиск в O (1).
- LinkedList (пользовательская структура данных, которую мы создаем) делает ниже функциональности в O (1)
- изменить положение наиболее используемого элемента на вершину
- удалить наименее используемый элемент из кэша при достижении лимита кэша.
Пользовательская реализация LinkedList и наименее недавно использованного кэша с четким объяснением приведена ниже.
https://medium.com/dsinjs/implementing-lru-cache-in-javascript-94ba6755cda9