JavaScript で循環バッファを実装した人はいますか? ポインタなしでどうやってそれをしますか?
20 に答える
奇妙な偶然の一致、私は今日早く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= {};
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);},
これは、使用できるコードの簡単なモックアップです (おそらく動作しておらず、バグがありますが、それを実行する方法を示しています)。
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());
もちろん、配列を使用して実装することも、内部的に配列を使用して現在の項目インデックスの値を保持し、それを移動するクラスを使用して実装することもできます。
短くて甘い:
// 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
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]
個人的には、 https ://github.com/trevnorris/cbuffer にある Trevor Norris の実装を使用しています 。
そして私はそれにとても満足しています:-)
Robert Koritnik のコードを動作させることができなかったので、動作するように見える次のように編集しました。
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;
this.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;
};
this.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;
};
return this;
}
使用するには:
var queue = new CircularQueue(3); // a circular queue with 3 items
queue.push("a");
queue.push("b");
queue.push("c");
queue.push("d");
alert(queue.pop()); // d
alert(queue.pop()); // c
alert(queue.pop()); // b
alert(queue.pop()); // d
alert(queue.pop()); // c
1つのアプローチは、他の人が示唆しているように、リンクリストを使用することです。もう1つの手法は、単純な配列をバッファーとして使用し、その配列へのインデックスを介して読み取り位置と書き込み位置を追跡することです。
シンプルで効率的なソリューションをありがとうnoiv 。PerSのようにバッファにアクセスできるようにする必要もありましたが、追加された順序でアイテムを取得したかったのです。だからここに私が終わったものがあります:
function buffer(capacity) {
if (!(capacity > 0)) {
throw new Error();
}
var pointer = 0, buffer = [];
var publicObj = {
get: function (key) {
if (key === undefined) {
// return all items in the order they were added
if (pointer == 0 || buffer.length < capacity) {
// the buffer as it is now is in order
return buffer;
}
// split and join the two parts so the result is in order
return buffer.slice(pointer).concat(buffer.slice(0, pointer));
}
return buffer[key];
},
push: function (item) {
buffer[pointer] = item;
pointer = (capacity + pointer + 1) % capacity;
// update public length field
publicObj.length = buffer.length;
},
capacity: capacity,
length: 0
};
return publicObj;
}
テストスイートは次のとおりです。
QUnit.module("buffer");
QUnit.test("constructor", function () {
QUnit.expect(4);
QUnit.equal(buffer(1).capacity, 1, "minimum length of 1 is allowed");
QUnit.equal(buffer(10).capacity, 10);
QUnit.throws(
function () {
buffer(-1);
},
Error,
"must throuw exception on negative length"
);
QUnit.throws(
function () {
buffer(0);
},
Error,
"must throw exception on zero length"
);
});
QUnit.test("push", function () {
QUnit.expect(5);
var b = buffer(5);
QUnit.equal(b.length, 0);
b.push("1");
QUnit.equal(b.length, 1);
b.push("2");
b.push("3");
b.push("4");
b.push("5");
QUnit.equal(b.length, 5);
b.push("6");
QUnit.equal(b.length, 5);
b.push("7");
b.push("8");
QUnit.equal(b.length, 5);
});
QUnit.test("get(key)", function () {
QUnit.expect(8);
var b = buffer(3);
QUnit.equal(b.get(0), undefined);
b.push("a");
QUnit.equal(b.get(0), "a");
b.push("b");
QUnit.equal(b.get(1), "b");
b.push("c");
QUnit.equal(b.get(2), "c");
b.push("d");
QUnit.equal(b.get(0), "d");
b = buffer(1);
b.push("1");
QUnit.equal(b.get(0), "1");
b.push("2");
QUnit.equal(b.get(0), "2");
QUnit.equal(b.length, 1);
});
QUnit.test("get()", function () {
QUnit.expect(7);
var b = buffer(3);
QUnit.deepEqual(b.get(), []);
b.push("a");
QUnit.deepEqual(b.get(), ["a"]);
b.push("b");
QUnit.deepEqual(b.get(), ["a", "b"]);
b.push("c");
QUnit.deepEqual(b.get(), ["a", "b", "c"]);
b.push("d");
QUnit.deepEqual(b.get(), ["b", "c", "d"]);
b.push("e");
QUnit.deepEqual(b.get(), ["c", "d", "e"]);
b.push("f");
QUnit.deepEqual(b.get(), ["d", "e", "f"]);
});
私はnoiv11がこれをどのように解決したかが本当に好きで、私の必要性のために、バッファを返す追加のプロパティ「buffer」を追加しました:
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;
},
buffer : buffer
};
};
// sample use
var rbuffer = createRingBuffer(3);
rbuffer.push('a');
rbuffer.push('b');
rbuffer.push('c');
alert(rbuffer.buffer.toString());
rbuffer.push('d');
alert(rbuffer.buffer.toString());
var el = rbuffer.get(0);
alert(el);
オブジェクトを使用するだけでこれを行うことができるはずだと思います。このようなもの:
var link = function(next, value) {
this.next = next;
this.value = value;
};
var last = new link();
var second = link(last);
var first = link(second);
last.next = first;
ここで、各リンクの value プロパティに値を格納するだけです。