Javascript:有效地将项目移入和移出固定大小的数组

Question

如果我想要一个固定大小为N的数组,以便缓存最近的N个项目,那么一旦达到限制N,我将不得不在添加最新项目时删除最旧的项目.

注意:我不关心最新项目是否在数组的开头或结尾,只要项目按添加顺序删除即可.

显而易见的方法是:

• push()和shift()(所以cache[0]包含最旧的项目),或
• unshift()和pop()(所以cache[0]包含最新的项目)

基本理念:

var cache = [], limit = 10000;

function cacheItem( item ) {

    // In case we want to do anything with the oldest item
    // before it's gone forever.
    var oldest = [];

    cache.push( item );

    // Use WHILE and >= instead of just IF in case the cache
    // was altered by more than one item at some point.
    while ( cache.length >= limit ) {
        oldest.push( cache.shift() );
    }

    return oldest;
}

但是,我读过有关内存的问题shift和unshift因为他们改变了数组的开头和其他移动周围的一切,但不幸的是,一个这些方法已被用来做这种方式!

QS:

1. 还有其他方法可以做到更好的性能吗？
2. 如果我已经提到的两种方式是最好的,我需要注意哪些特定的优点/缺点？

结论

在对数据结构做了一些更多的研究之后(我从来没有在其他语言中编程,所以如果它不是Javascript的原生,我可能还没有听说过!)并在多个浏览器中进行大量基准测试,包括小型和大型数组以及大量的读/写,这是我发现的:

• Bergi提出的"循环缓冲"方法是最好的表现(由于答案和评论中解释的原因),因此它已被接受作为答案.但是,它并不直观,并且很难编写自己的"额外"功能(因为您总是需要offset考虑).如果您打算使用此方法,我建议在GitHub上使用已经创建的这个循环缓冲区.
• 'pop/unpush'方法更直观,性能相当好,接受最极端的数字.
• 遗憾的是,'copyWithin'方法对于性能而言非常糟糕(在多个浏览器中测试过),很快就会产生不可接受的延迟.它也没有IE支持.这是一个如此简单的方法!我希望它更好.
• Felix Kling在评论中提出的"链表"方法实际上是一个非常好的选择.我最初无视它,因为它似乎是我不需要的许多额外的东西,但令我惊讶的是......

我实际需要的是最近最少使用(LRU)地图(使用双向链表).现在,由于我没有在原始问题中指定我的额外要求,我仍然将Bergi的答案标记为该特定问题的最佳答案.但是,因为我需要知道我的缓存中是否已经存在一个值,如果是这样,将其标记为缓存中的最新项,我必须添加到我的循环缓冲区add()方法(主要是indexOf())的附加逻辑使它不再多效率高于'pop/unpush'方法.但是,在这些情况下,LRUMap的性能会使其他两个水中的水都爆炸!

总结一下:

1. 链接列表 - 大多数选项,同时仍保持良好的性能
2. 循环缓冲区 - 仅添加和获取的最佳性能
3. 流行/不褪色 - 最直观,最简单
4. copyWithin - 目前表现糟糕,没理由使用

Answer 1

如果我有一个缓存最近N个项目的数组,一旦达到限制N,我将不得不删除最旧的,同时添加最新的.

你不是要在数组中复制东西,O(n)每次都会采取步骤.

相反,这是环形缓冲区的完美用例.只需保留列表的"开始"和"结束"的偏移量,然后使用该偏移量访问缓冲区并以其模数为其模数.

var cache = new Array(10000);
cache.offset = 0;

function cacheItem(item) {
    cache[cache.offset++] = item;
    cache.offset %= cache.length;
}
function cacheGet(i) { // backwards, 0 is most recent
    return cache[(cache.offset - 1 - i + cache.length) % cache.length];
}