Javascript Umlaufpuffer Queue-Implementierung als "FIFO-Warteschlange"

Question

Gibt es eine Ring-Puffer-Version von Array? Angenommen, die Anzahl der maximal gedrückten Elemente zum Zeitpunkt ist bekannt, muss ich meine eigene FIFO-Warteschlange für die Leistung ableiten? Hier

ist, was ich versucht:

Kreis Umsetzung:

function CBuf(n) 
{ 
    var ctrPush=0; 
    var ctrPop=0; 
    var ab = new ArrayBuffer(n*4); 
    var buf = new Uint32Array(ab); 

    this.push = function (v) { 
     buf[ctrPush%n] = v; 
     ctrPush++; 
    }; 


    this.empty = function() { 
     return (ctrPush == ctrPop); 
    } 


    this.pop = function() { 
     var tmp = buf[ctrPop%n]; 
     ctrPop++; 
     return tmp; 
    }; 
} 

Benchmark einfach Array:

{ 
    var t1 = new Date(); 
    var arr = []; 

    for (var j = 0; j < 1000; j++) { 
     for (var i = 0; i < 10000; i++) { 
      arr.push(i); 
     } 
     for (var i = 0; i < 10000; i++) { 
      arr.shift(); 
     } 
    } 
    var t2 = new Date(); 

    console.log("array time=" + (t2 - t1)); 
} 

Benchmark Ringpuffer:

{ 
    var t1 = new Date(); 
    var arr = new CBuf(10000); 

    for (var j = 0; j < 1000; j++) { 
     for (var i = 0; i < 10000; i++) { 
      arr.push(i); 
     } 
     for (var i = 0; i < 10000; i++) { 
      if(!arr.empty()) 
       arr.pop(); 
     } 
    } 
    var t2 = new Date(); 

    console.log("cbuf time="+(t2 - t1)); 
} 

Ergebnis:

array time=2749 ms 
cbuf time=552 ms (230 if using &(n-1) instead of %n) 

Für max 70k Elemente:

array time=19456 ms 
cbuf time=3872 ms (1700 if using &(n-1) instead of %n) 

scheinen sie ähnliche Zeitkomplexität aber Array Verschiebung ist in NodeJS langsamer zu haben. Vielleicht überprüft es viele Dinge wie Grenzen überprüfen und Größenänderungen ständig? Ich brauche etwas wie eine SIMD Variable, aber mit n Länge.

Ich plane, dies in einer Nodejs Inter-Server-Work Scheduler-Warteschlange zu verwenden.

Edit:

Hier können Sie testen:

https://jsperf.com/fifo-array-vs-circular-buffer-preallocated

Answer 1

drücken und Verschiebung sind langsam. Verwenden Sie einfach einen Array-Index.