Реализация кэша LRU в JavaScript

Это не кеш LRU, но у меня есть собственная реализация связанной карты . Поскольку он использует объекты JS в качестве хранилища, он будет иметь аналогичные характеристики производительности (объекты-оболочки и хеш-функция ухудшают производительность).

В настоящее время документации в основном не существует , но есть связанный ответ SO .

Метод each () передаст текущий ключ, текущее значение и логическое значение, указывающее, есть ли еще элементы в качестве аргументов функции обратного вызова.

В качестве альтернативы цикл можно выполнить вручную через

for(var i = map.size; i--; map.next()) {
    var currentKey = map.key();
    var currentValue = map.value();
}

Это:

https : //github.com/monsur/jscache

, кажется, подходит вам, хотя setItem (т.е. put) равен O (N) в худшем случае, это происходит, если кеш заполняется при вставке . В этом случае выполняется поиск в кэше для удаления элементов с истекшим сроком действия или элементов, которые использовались недавно. getItem равен O (1), и истечение срока обрабатывается операцией getItem (то есть, если срок действия извлекаемого элемента истек, удаляет его и возвращает null).

Код следующий. достаточно компактный, чтобы его было легко понять.

PS Возможно, было бы полезно добавить в конструктор параметр, указывающий fillFactor , который имеет фиксированное значение 0,75 (что означает, что при очистке кеша он '

Реализация monsur.com не работает при вставке только потому, что у нее есть элементы, срок действия которых истекает в реальном времени. Это не простой LRU. Если вы заботитесь только о последних использованных элементах без учета реального времени, это можно сделать в O (1). Очередь, реализованная как двусвязный список, имеет O (1) для вставки или удаления с конца, и это все, что вам нужно для кеширования. Что касается поиска, то хеш-карта, которую javascript упрощает до некоторой степени, должна подходить для поиска почти O (1) (при условии, что движок javascript использует хорошую хэш-карту, это, конечно, зависит от реализации). Итак, у вас есть связанный список элементов с хеш-картой, указывающей на элементы. При необходимости манипулируйте концами связанного списка, чтобы поместить новые элементы и запрошенные элементы на один конец и удалить старые элементы с другого.