作为“FIFO队列”的Javascript循环缓冲区队列实现

是否有数组的循环缓冲区版本？假设已知最大推送元素的数量是已知的，我是否必须派生自己的FIFO队列来获得性能？作为“FIFO队列”的Javascript循环缓冲区队列实现

这里是我的尝试：

通知执行：

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

基准简单数组：

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

基准循环缓冲区：

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

结果：

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

对于最大70K元素：

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

他们似乎有相似的时间复杂性，但阵列移是在慢的NodeJS。也许它会检查许多事情，例如边界检查和不断调整大小？我需要类似SIMD变量但长度为n的东西。

我打算在nodejs服务器间工作调度器队列上使用它。

编辑：

在这里，您可以测试：

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

来源

2016-11-24 huseyin tugrul buyukisik

你想要的东西就像一个普通的数组，但是你**不需要的就是来回移动数组内容，因为这些是线性操作。只需保留自己的循环缓冲区开始和结束的索引值即可。 – Pointy

小心：'＆（n-1）'与'％n'不同，除非'n'是2的幂。 – jmrk

Push和转变是缓慢的。只需使用数组索引。

来源

2016-11-24 18:57:13 user835611

小修正：推得快。转变缓慢。像建议的'CBuf'实现这样的基于索引的是要走的路（但要小心溢出！）。 – jmrk

作为“FIFO队列”的Javascript循环缓冲区队列实现

回答

相关问题