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

Question

Java имеет LinkedHashMap, которая возвращает вас на 99% в кэш LRU .

Существует ли реализация Javascript кэша LRU, предпочтительно из авторитетного источника, а именно:

1. понятно
2. эффективный (амортизированный O (1) получить / положить / удалить)

? Я искал в Интернете, но не смог найти; Мне показалось, что я нашел один в Ajax Design Patterns , но он скрывает метод sendToTail() и имеет производительность O (n) (предположительно, поскольку очередь и ассоциативный массив разделены).

Полагаю, я мог бы написать свой собственный, но я усвоил трудный путь, которым изобретать колесо для основных алгоритмов может быть опасно для здоровья: /

Answer 1

Это:

https://github.com/monsur/jscache

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

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

P.S. Возможно, было бы полезно добавить в конструктор опцию для указания fillFactor, которая установлена ​​на 0,75 (это означает, что при очистке кэша его размер уменьшается как минимум до 3/4 от максимального размера)

Answer 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"

Answer 3

Это стоит упомянуть: https://github.com/rsms/js-lru

Базовым набором функций является O (1), а код сильно комментируется (также с ASCII art!)

Answer 4

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

Answer 5

Так как нам нужны операции чтения, записи, обновления и удаления в O (1), мы используем две структуры данных.

1. Объект (или Карта) в JavaScript обеспечивает поиск в O (1).
2. Doubly LinkedList (пользовательская структура данных, которую мы создаем) делает ниже функциональности в O (1)
   • изменить положение наиболее часто используемого элемента на вершину
   • удалить наименее используемый элемент из кэша при достижении лимита кэша.

Пользовательская реализация Doubly LinkedList и Наименее недавно использованный кэш с ясным объяснением приведена ниже.

https://medium.com/dsinjs/implementing-lru-cache-in-javascript-94ba6755cda9

Answer 6

Мне известно, что это старый вопрос, но я добавляю ссылку для дальнейшего использования. Проверьте https://github.com/monmohan/dsjslib. Это имеет реализацию LRU Cache в дополнение к некоторым другим структурам данных. Такие кэши (и этот тоже) поддерживают двусвязный список записей кэша в порядке LRU, то есть записи перемещаются в начало, когда к ним обращаются, и удаляются из хвоста, когда они возвращаются (скажем, по истечении срока действия или потому, что достигнут предел размера). Его O (1), поскольку он включает только постоянное количество манипуляций с указателями.

Answer 7

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

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

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

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

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