Javascript中的LRU缓存实现

Question

Java有LinkedHashMap,它可以让你99%到LRU缓存.

是否存在LRU缓存的Javascript实现,最好是来自信誉良好的源,即:

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

？我一直在网上搜索但找不到一个; 我以为我在Ajax设计模式上找到了一个,但它掩盖了该sendToTail()方法并且具有O(n)性能(可能是因为队列和关联数组被分开).

我想我可以写自己的,但我已经学会了重新发明核心算法的轮子会对一个人的健康造成危害的困难:/

Answer 1

这不如您想要的那么高效,但它在简单性和可读性方面弥补了它.在许多情况下,它会很快.

我需要一个简单的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 2

这个:

https://github.com/monsur/jscache

似乎适合你的情况虽然setItem(即put)在最坏的情况下是O(N),如果在插入时填充缓存就会发生这种情况.在这种情况下,搜索缓存以清除过期的项目或最近最少使用的项目.getItem是O(1)并且在getItem操作上处理到期(即,如果被提取的项目已过期,则将其删除并返回null).

代码非常紧凑,易于理解.

PS向构造函数添加指定的选项可能很有用,该选项fillFactor固定为0.75(意味着当清除缓存时,它的大小至少减少到最大大小的3/4)

Answer 3

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

函数的核心集是O（1），并且代码受到了大量注释（也具有ASCII艺术！）