Подтвердить что ты не робот

Циклический буфер в JavaScript

Кто-нибудь уже реализовал циклический буфер в JavaScript? Как вы это сделаете без указателей?

4b9b3361

ОТВЕТЫ

Ответ 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= {};

Ответ 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);},

Ответ 3

Как и многие другие, мне понравилось решение noiv, но я хотел несколько более удобный API:

var createRingBuffer = function(length){
  /* https://stackoverflow.com/a/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 перемещает буфер назад один и возвращает то, что там (например, popping without delete)
  • next отменяет prev (перемещает буфер вперед и возвращает его)

Я использовал это, чтобы сохранить историю команд, которую я мог бы перевернуть в приложении, используя методы prev и next, которые приятно возвращают undefined, когда им некуда идти.

Ответ 4

Это быстрый макет кода, который вы могли бы использовать (он, вероятно, не работает и имеет ошибки в нем, но показывает, как это можно сделать):

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());

Конечно, вы могли бы реализовать его с помощью массива с классом, который бы внутренне использовал массив и сохранял значение текущего элемента индекса и перемещал его.

Ответ 5

Я лично использую реализацию Trevor Norris, которую вы можете найти здесь: https://github.com/trevnorris/cbuffer

и я вполне доволен этим: -)

Ответ 6

Короткий и сладкий:

// 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

Ответ 7

Я не мог заставить код Роберта Коритника работать, поэтому я отредактировал его следующим образом:

    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

Ответ 8

Мне очень нравится, как noiv11 решил это, и для моей потребности я добавил дополнительный буфер свойств, который возвращает буфер:

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);

Ответ 9

Вместо реализации круговой очереди с 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]

Ответ 10

Я думаю, вы должны это сделать, просто используя объекты. Что-то вроде этого:

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;

Теперь вы просто сохраните значение в каждом свойстве значения ссылки.

Ответ 11

Один из подходов - использовать связанный список, как предложили другие. Другой способ - использовать простой массив в качестве буфера и отслеживать позиции чтения и записи через индексы в этот массив.

Ответ 12

Благодарим вас за простой и эффективный решение. Мне также нужно было иметь доступ к буферу, например 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"]);
});

Ответ 13

Бесстыдная самонакладка:

Если вы ищете вращающийся буфер node.js, я написал один из них, который можно найти здесь: http://npmjs.org/packages/pivot-buffer p >

Документация в настоящее время отсутствует, но RotatingBuffer#push позволяет добавить буфер в текущий буфер, вращая предыдущие данные, если новая длина больше длины, указанной в конструкторе.

Ответ 14

Это очень просто, если вы теперь знаете, что такое Array.prototype.length :

function CircularBuffer(size) {
  Array.call(this,size); //superclass
  this.length = 0; //current index
  this.size = size; //buffer size
};

CircularBuffer.prototype = Object.create(Array.prototype);
CircularBuffer.prototype.constructor = CircularBuffer;
CircularBuffer.prototype.constructor.name = "CircularBuffer";

CircularBuffer.prototype.push = function push(elem){
  Array.prototype.push.call(this,elem);
  if (this.length >= this.size) this.length = 0;
  return this.length;
}

CircularBuffer.prototype.pop = function pop(){
  var r = this[this.length];
  if (this.length <= 0) this.length = this.size;  
  this.length--;
  return r;
}

Ответ 15

Спустя почти 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)};');

Ответ 16

Я предпочитаю более простые подходы. Это должно быть три строки, ИМО.

Что-то вроде

const makeRing = sz                   => ({ sz, buf: new Array(size) }),
      at       = ({sz, buf}, pos)     => buf[pos % sz],
      set      = ({sz, buf}, pos, to) => buf[pos % sz] = to;

Тогда вы можете просто

const ring = makeRing(10);

ring.buf.fill(1);
set(ring, 35, 'TWO!');

console.log(ring.buf);
console.log(at(ring, 65));