作爲「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循環緩衝區隊列實現

回答

相關問題