JavaScript中的循环缓冲区

Question

是否已经有人在JavaScript中实现了循环缓冲区？如果没有指针，你会怎么做？

- user191800

---

你可能应该澄清“循环缓冲区”。你感兴趣的是什么类型的API？缓冲区中放入了什么？等等。 - Pointy

理想情况下，API 应该包含： push(key, value) get(key) 并且当缓冲区达到最大大小时，第一个保存的项将被覆盖。 - user191800

不要介意我自己推销一下：如果你正在寻找一个旋转的node.js缓冲区，我写了一个可以在这里找到：http://npmjs.org/packages/pivot-buffer。目前文档还不够完善，但是`RotatingBuffer#push`允许你将缓冲区附加到当前缓冲区，如果新长度大于构造函数中指定的长度，则旋转以前的数据。 - Yotam Ofek

Answer 1

巧合的是，我今天早些时候刚写了一个！我不知道你的具体要求是什么，但这可能会有用。

它提供了一个类似于无限长度数组的接口，但“忘记”旧项：

// Circular buffer storage. Externally-apparent 'length' increases indefinitely
// while any items with indexes below length-n will be forgotten (undefined
// will be returned if you try to get them, trying to set is an exception).
// n represents the initial length of the array, not a maximum
function CircularBuffer(n) {
    this._array= new Array(n);
    this.length= 0;
}
CircularBuffer.prototype.toString= function() {
    return '[object CircularBuffer('+this._array.length+') length '+this.length+']';
};
CircularBuffer.prototype.get= function(i) {
    if (i<0 || i<this.length-this._array.length)
        return undefined;
    return this._array[i%this._array.length];
};
CircularBuffer.prototype.set= function(i, v) {
    if (i<0 || i<this.length-this._array.length)
        throw CircularBuffer.IndexError;
    while (i>this.length) {
        this._array[this.length%this._array.length]= undefined;
        this.length++;
    }
    this._array[i%this._array.length]= v;
    if (i==this.length)
        this.length++;
};
CircularBuffer.IndexError= {};

- bobince

---

不错。我添加了push方法：CircularBuffer.prototype.push = function(v) { this._array[this.length%this._array.length] = v; this.length++; }; - forresto

“Indefinitely” 的意思是 1.7976931348623157e+308，而这又意味着“无限大”的数值，在某个时刻表示为正无穷大。+1 - loveNoHate

它只能工作到 Number_MAX_SAFE_INTEGER 或 2^53 - 1。这是因为 Number_MAX_SAFE_INTEGER + 1 等于 Number_MAX_SAFE_INTEGER + 2。仍然是一个非常大的数字，接近10万亿！来源：MDN - Joshua Wade

Answer 2

var createRingBuffer = function(length){

  var pointer = 0, buffer = []; 

  return {
    get  : function(key){return buffer[key];},
    push : function(item){
      buffer[pointer] = item;
      pointer = (length + pointer +1) % length;
    }
  };
};

更新：如果你只想填充缓冲区的数字，请参考以下一行插件：

min  : function(){return Math.min.apply(Math, buffer);},
sum  : function(){return buffer.reduce(function(a, b){ return a + b; }, 0);},

- Torsten Becker

---

为什么你使用 pointer = (length + pointer +1) % length 而不是只用 pointer = (pointer + 1) % length？ - Muxa

将get函数更改为get: function(key){ if (key < 0){ return buffer[pointer+key]; } else if (key === false){ return buffer[pointer - 1]; } else{ return buffer[key]; } }，以支持负索引（从右侧开始）并默认返回最后一个推送的内容，如果没有给定键。 - Two-Bit Alchemist

实际上，我最终添加了一些其他的美好之处，所以我提交了一个变体答案。 - Two-Bit Alchemist

Answer 3

跟很多人一样，我喜欢noiv的解决方案，但我想要一个更好的API：

var createRingBuffer = function(length){
  /* https://dev59.com/eHI-5IYBdhLWcg3w-9wK#4774081 */
  var pointer = 0, buffer = []; 

  return {
    get  : function(key){
        if (key < 0){
            return buffer[pointer+key];
        } else if (key === false){
            return buffer[pointer - 1];
        } else{
            return buffer[key];
        }
    },
    push : function(item){
      buffer[pointer] = item;
      pointer = (pointer + 1) % length;
      return item;
    },
    prev : function(){
        var tmp_pointer = (pointer - 1) % length;
        if (buffer[tmp_pointer]){
            pointer = tmp_pointer;
            return buffer[pointer];
        }
    },
    next : function(){
        if (buffer[pointer]){
            pointer = (pointer + 1) % length;
            return buffer[pointer];
        }
    }
  };
};

改进后的内容：

• get 支持默认参数（返回最后一个压入缓冲区的项）
• get 支持负索引（从右侧开始计数）
• prev 向后移动缓冲区并返回该位置的值（类似于弹出但不删除）
• next 撤消 prev（将缓冲区向前移动并返回其值）

我用这个来存储命令历史记录，然后可以在应用程序中使用其prev和next方法来翻转，当它们无处可去时，它们很好地返回未定义。

- Two-Bit Alchemist

---

.get() 会一直失败，除非你将 === false 替换为 === undefined。当缓冲区已满时，.get() 将返回 undefined。当缓冲区已满时，.get(-n) 也会返回 undefined。例如：r = createRingBuffer(2); r.push(1); r.push(2); r.get(-1)。 - Orwellophile

Answer 4

近10年过去了，现在可以使用JavaScript ES6来解决这个问题：

    class CircularBuffer {
      constructor(bufferLength) {
        this.buffer = [];
        this.pointer = 0;
        this.bufferLength = bufferLength;
      }
      
      push(element) {
        if(this.buffer.length === this.bufferLength) {
           this.buffer[this.pointer] = element;
        } else {
           this.buffer.push(element);
        }
        this.pointer = (this.pointer + 1) % this.bufferLength;
      }
    
      get(i) {
        return this.buffer[i];
      }
      
      //Gets the ith element before last one 
      getLast(i) {
        return this.buffer[this.pointer+this.bufferLength-1-i];
      }
    
    }

//To use it:

let circularBuffer = new CircularBuffer(3);
circularBuffer.push('a');
circularBuffer.push('b');
circularBuffer.push('c');
// should print a,b,c
console.log(`0 element: ${circularBuffer.get(0)}; 1 element: ${circularBuffer.get(1)}; 2 element: ${circularBuffer.get(2)};`);

console.log('Last element: '+circularBuffer.getLast(0)); // should print 'c'

circularBuffer.push('d');

// should print d,b,c
console.log(`0 element: ${circularBuffer.get(0)}; 1 element: ${circularBuffer.get(1)}; 2 element: ${circularBuffer.get(2)};`);

- Ivan Hristov

Answer 5

简短明了：

// IMPLEMENTATION
function CircularArray(maxLength) {
  this.maxLength = maxLength;
}

CircularArray.prototype = Object.create(Array.prototype);

CircularArray.prototype.push = function(element) {
  Array.prototype.push.call(this, element);
  while (this.length > this.maxLength) {
    this.shift();
  }
}

// USAGE
var ca = new CircularArray(2);
var i;

for (i = 0; i < 100; i++) {
  ca.push(i);
}

console.log(ca[0]);
console.log(ca[1]);
console.log("Length: " + ca.length);

输出：

98
99
Length: 2

- Oliver Heard

Answer 6

这是您可以使用的代码的快速模拟（可能不起作用并且存在错误，但它展示了如何完成）：

var CircularQueueItem = function(value, next, back) {
    this.next = next;
    this.value = value;
    this.back = back;
    return this;
};

var CircularQueue = function(queueLength){
    /// <summary>Creates a circular queue of specified length</summary>
    /// <param name="queueLength" type="int">Length of the circular queue</type>
    this._current = new CircularQueueItem(undefined, undefined, undefined);
    var item = this._current;
    for(var i = 0; i < queueLength - 1; i++)
    {
        item.next = new CircularQueueItem(undefined, undefined, item);
        item = item.next;
    }
    item.next = this._current;
    this._current.back = item;
}

CircularQueue.prototype.push = function(value){
    /// <summary>Pushes a value/object into the circular queue</summary>
    /// <param name="value">Any value/object that should be stored into the queue</param>
    this._current.value = value;
    this._current = this._current.next;
};

CircularQueue.prototype.pop = function(){
    /// <summary>Gets the last pushed value/object from the circular queue</summary>
    /// <returns>Returns the last pushed value/object from the circular queue</returns>
    this._current = this._current.back;
    return this._current.value;
};

使用这个对象的方式如下：

var queue = new CircularQueue(10); // a circular queue with 10 items
queue.push(10);
queue.push(20);
alert(queue.pop());
alert(queue.pop());

当然，您也可以使用数组来实现它，使用一个类来内部使用数组并保持当前项目索引的值，并移动该索引。

- Robert Koritnik

---

所有这些.NET风格的文档注释是什么意思？ - Ionuț G. Stan

@Ionut：如果他在使用.NET，那么Visual Studio 2008+会有JavaScript智能感知功能；否则，其他编辑器将会忽略它们。 - Robert Koritnik

我不知道Visual Studio中有对它们的支持。谢谢你提供的信息。 - Ionuț G. Stan

@Ionut：确保编写AFTER函数声明而不是像C#中通常的BEFORE。这是主要区别。否则，它的工作方式非常相似。 - Robert Koritnik

感到遗憾的是，不必要的XML样式标记使我感到沮丧，但结构化文档得到了高度认可。 - Steven Lu

Answer 7

这是我的理解。具体来说，这是一个非常简单的对象实现，用于圆形/环形滑动缓冲区。

小提示。尽管人们称其为类似的名称，例如“循环”，“环”，“队列”，但值得澄清的是，它们可能意味着不同的事情。

1. 环形/循环队列。您可以将元素添加到头部，并从尾部裁剪它们。最小大小为0，最大大小为底层数组的大小。该队列包装在底层数组周围。

2. 相同的东西，队列，FIFO，先进先出，但具有可变（无限）的最大大小，并使用标准的push()和unshift()数组方法进行实现。要添加元素，只需将其push()到数组中，要消耗元素，只需将其unshift()，这就是标准函数，无需发明任何东西。

3. 恒定大小的滑动缓冲区，其中新元素添加到头部（右侧），缓冲区向后滑动（向左），并且最左边过多的元素会自动丢失。从概念上讲，它是一个滑动缓冲区，只是以最有效的方式实现为圆形/环形缓冲区。

这是（3）种的实现。它可以用作数据可视化小部件的后端，例如用于实时监视的滑动线图。

对象：

function make_CRS_Buffer(size) {
    return {
        A:  [],
        Ai: 0,
        Asz:    size,
        add:    function(value) {
            this.A[ this.Ai ] = value;
            this.Ai = (this.Ai + 1) % this.Asz;
        },
        forall: function(callback) {
            var mAi = this.A.length < this.Asz ? 0 : this.Ai;
            for (var i = 0; i < this.A.length; i++) {
                callback(this.A[ (mAi + i) % this.Asz ]);
            }

        }
    };
}

使用方法：

var buff1 = make_CRS_Buffer(5);

buff1.add(cnt);

buff1.forall(value => {
    b1.innerHTML += value + " ";
});

以下是一个完整的功能示例，有两个缓冲区并行运行：

var b1 = document.getElementById("b1");
var b2 = document.getElementById("b2");

var cnt = 0;

var buff1 = make_CRS_Buffer(5);
var buff2 = make_CRS_Buffer(12);


function add() {
 buff1.add(cnt);
 buff2.add(cnt);
 cnt ++;
 
 b1.innerHTML = "";
 buff1.forall(value => {
  b1.innerHTML += value + " ";
 });
 
 b2.innerHTML = "";
 buff2.forall(value => {
  b2.innerHTML += value + " ";
 });
}

function make_CRS_Buffer(size) {
 return {
  A: [],
  Ai: 0,
  Asz: size,
  add: function(value) {
   this.A[ this.Ai ] = value;
   this.Ai = (this.Ai + 1) % this.Asz;
  },
  forall: function(callback) {
   var mAi = this.A.length < this.Asz ? 0 : this.Ai;
   for (var i = 0; i < this.A.length; i++) {
    callback(this.A[ (mAi + i) % this.Asz ]);
   }
  
  }
 };
}

<!DOCTYPE html>
<html>
<body>

<h1>Circular/Ring Sliding Buffer</h1>

<p><i>(c) 2020, Leonid Titov</i>

<div id="b1" style="
 background-color: hsl(0,0%,80%);
 padding: 5px;
">empty</div>

<div id="b2" style="
 background-color: hsl(0,0%,80%);
 padding: 5px;
">empty</div>

<br>
<button onclick="add()">Add one more</button>

</body>
</html>

希望对您有所帮助。

- latitov

Answer 8

不必使用JavaScript实现循环队列，我们可以使用数组的一些内置函数来实现循环队列。

例如： 假设我们需要实现长度为4的循环队列。

var circular = new Array();
var maxLength = 4;
var addElementToQueue = function(element){
    if(circular.length == maxLength){
        circular.pop();
    }
    circular.unshift(element);
};
addElementToQueue(1);
addElementToQueue(2);
addElementToQueue(3);
addElementToQueue(4);

输出：

循环数组 [4, 3, 2, 1]

如果您尝试向此数组添加另一个元素，例如：

addElementToQueue(5);

输出：

循环的数组为 [5, 4, 3, 2]

- Puneet

---

unshift不是O(n)吗？这似乎是实现循环缓冲区的一种非常糟糕的方式。 - Navin

Answer 9

我个人使用Trevor Norris的实现，您可以在此处找到： https://github.com/trevnorris/cbuffer 我对其感到非常满意 :-)

- laurentIsRunning

Answer 10

很多答案，但没有看到像下面这样的功能简单的方法...像(ES6)这样的形式：

const circularAdd = maxSize => (queue, newItem) =>
  queue.concat([newItem]).slice(Math.max(0, queue.length + 1 - maxSize));

这可以用作减少器（reducer），例如在可观测流（observable streams）中的scan。

// Suppose newItem$ is a simple new value emitter
const itemBuffer$ = newItem$.pipe(scan(circularAdd(100), []));
// itemBuffer$ will now emit arrays with max 100 items, where the new item is last

编辑

我现在看到，这并不是对这个特定问题的回答，因为它没有提供阅读位置... :)

- Johan t Hart