javascript - जावास्क्रिप्ट में परिपत्र बफर




data-structures circular-buffer (9)

क्या किसी ने जावास्क्रिप्ट में पहले से ही एक गोलाकार बफर लागू किया है? पॉइंटर्स के बिना आप ऐसा कैसे करेंगे?


आपके सरल और कुशल solution लिए धन्यवाद नोव। मुझे पेर्स की तरह बफर तक पहुंचने में भी सक्षम होना जरूरी था , लेकिन मैं आइटम को जोड़े गए क्रम में प्राप्त करना चाहता था। तो यहां मैं क्या समाप्त हुआ:

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"]);
});

एक दृष्टिकोण एक लिंक की गई सूची का उपयोग करना होगा जैसा कि अन्य ने सुझाव दिया है। एक और तकनीक बफर के रूप में एक सरल सरणी का उपयोग करना और उस सरणी में सूचकांक के माध्यम से पढ़ने और लिखने की स्थिति का ट्रैक रखना होगा।


छोटा एवं सुन्दर:

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

जावास्क्रिप्ट के साथ परिपत्र कतार लागू करने के बजाय, हम सर्कुलर कतार कार्यान्वयन को प्राप्त करने के लिए सरणी के कुछ अंतर्निहित कार्यों का उपयोग कर सकते हैं।

उदाहरण: मान लें कि हमें लंबाई 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]


मुझे लगता है कि आप वस्तुओं का उपयोग करके ऐसा करने में सक्षम होना चाहिए। कुछ इस तरह:

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 ने इसे कैसे हल किया और मेरी ज़रूरत के लिए मैंने एक अतिरिक्त संपत्ति 'बफर' जोड़ा जो बफर लौटाता है:

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

आप निश्चित रूप से सरणी का उपयोग करके इसे एक वर्ग के साथ कार्यान्वित कर सकते हैं जो आंतरिक रूप से सरणी का उपयोग करेगा और वर्तमान आइटम इंडेक्स का मूल्य रखेगा और उसे ले जायेगा।


लापरवाह स्वयं प्लग:

यदि आप घूर्णन नोड.जेएस बफर की तलाश में हैं, तो मैंने एक लिखा है जो यहां पाया जा सकता है: http://npmjs.org/packages/pivot-buffer

दस्तावेज़ीकरण में वर्तमान में कमी है, लेकिन RotatingBuffer#push आपको बफर को वर्तमान बफर में जोड़ने की अनुमति देता है, जो पिछले डेटा को घुमाता है यदि नई लंबाई कन्स्ट्रक्टर में निर्दिष्ट लंबाई से अधिक है।


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





circular-buffer