36

Java 有 LinkedHashMap 可以让你 99% 到达 LRU 缓存。

是否有 LRU 缓存的 Javascript 实现，最好来自信誉良好的来源，即：

  1. 可以理解的
  2. 高效（摊销 O(1) 获取/放置/删除）

? 我一直在网上搜索，但找不到；我以为我在Ajax Design Patterns上找到了一个，但它掩盖了该sendToTail()方法并且具有 O(n) 性能（大概是因为队列和关联数组是分开的）。

我想我可以自己写，但我已经学会了为核心算法重新发明轮子可能对一个人的健康有害：/

4

9 回答 9

61

在大多数实现平均情况下，地图应该是 O(1)。由于 Map 保持插入顺序，因此在其周围添加一些代码将为您提供 LRU，并且对于大多数用途而言，这应该非常快。

我需要一个简单的 LRU 缓存来执行少量昂贵的操作（1 秒）。我对复制粘贴一些小代码而不是引入外部代码感觉更好，但由于我没有找到它，所以我写了它：

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) {
        // refresh key
        if (this.cache.has(key)) this.cache.delete(key);
        // evict oldest
        else if (this.cache.size == this.max) 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"
于 2017-09-26T17:02:50.923 回答
9

这个：

https://github.com/monsur/jscache

似乎适合您的情况，尽管setItem（即放置）在最坏的情况下是 O(N)，但如果缓存在插入时被填满，就会发生这种情况。在这种情况下，将搜索缓存以清除过期项目或最近最少使用的项目。getItem是 O(1) 并且过期在getItem操作上处理（即，如果正在获取的项目已过期，则将其删除并返回 null）。

代码足够紧凑，易于理解。

PS 在构造函数中添加指定 的选项可能很有用，该选项fillFactor固定为 0.75（这意味着当缓存被清除时，它的大小至少减少到最大大小的 3/4）

于 2009-06-15T15:04:07.503 回答
7

这值得一提： https ://github.com/rsms/js-lru

核心函数集是 O(1) 并且代码被大量注释（也带有 ASCII 艺术！）

于 2014-11-03T23:11:50.300 回答
4

monsur.com 的实现在插入时是 O(n)，只是因为它的项目实际上在现实世界时间到期。它不是一个简单的 LRU。如果您只关心维护最近使用的项目而不考虑实际时间，则可以在 O(1) 中完成。队列，实现为双向链表，从末尾插入或删除的时间为 O(1)，这就是缓存所需的全部内容。至于查找，一个 javascript 让哈希表变得非常容易的哈希映射应该适用于几乎 O(1) 的查找（假设 javascript 引擎使用一个好的哈希映射，这当然取决于实现）。所以你有一个项目的链接列表，其中包含一个指向项目的哈希映射。根据需要操作链表的两端，将新项目和请求项目放在一端，并从另一端移除旧项目。

于 2010-07-27T19:54:24.567 回答
1

这个库runtime-memcache在 javascript 中实现了 lru 和其他一些缓存方案。

它使用修改后的双向链表来为和实现 O(1 get) 。您可以查看非常简单的实现。setremove

于 2020-01-23T20:58:05.693 回答
0

它不是 LRU 缓存，但我有自己的链接地图实现。由于它使用 JS 对象作为存储，它具有相似的性能特征（包装对象和散列函数会带来性能损失）。

目前，文档基本上不存在，但有一个相关的 SO answer。

该each()方法将传递当前键、当前值和一个布尔值，指示是否有更多元素作为回调函数的参数。

或者，循环可以通过手动完成

for(var i = map.size; i--; map.next()) {
    var currentKey = map.key();
    var currentValue = map.value();
}
于 2009-06-15T15:30:26.520 回答
0

我知道这是一个老问题，但添加了一个链接以供将来参考。查看https://github.com/monmohan/dsjslib。除了一些其他数据结构之外，它还有一个 LRU 缓存实现。这样的缓存（以及这个缓存）以 LRU 顺序维护缓存条目的双向链表，即条目在被访问时移动到头部，并在它们被回收时从尾部移除（比如到期或因为达到大小限制）。它的 O(1) 因为它只涉及恒定数量的指针操作。

于 2013-09-05T08:01:54.170 回答
-1

由于我们需要 O(1) 中的读、写、更新和删除操作，我们使用两种数据结构。

  1. JavaScript 中的对象（或地图）在 O(1) 中提供检索。
  2. 双链表（我们创建的自定义数据结构）在 O(1) 中实现以下功能
    • 将最常用元素的位置更改为顶部
    • 达到缓存限制时从缓存中删除最少使用的元素。

下面给出了双向链表和最近最少使用缓存的自定义实现，并给出了清晰的解释。

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

于 2019-05-24T16:44:27.937 回答
-2

不需要外部包/库，我们可以编写自己的代码在javascript中实现LRU，详情请参考https://dev.to/udayvunnam/implementing-lru-cache-in-javascript-3c8g网站。

于 2020-05-19T16:59:08.247 回答