JSのArray#shiftはとても遅いです． 後輩がキューを実装したくて困っていました．
キューの実装を紹介して，その計測を示します．
とりあえず計測
高速化の議論をするときは，必ず始めにベンチマークを取りましょう．
shift/pop/spliceを比較しました．ベンチマークは10000要素を1つずつ取り除いていくものです．
const n=100000; arr = Array.from(new Array(n)).map((_,i)=>i) for(let i = 0; i < n; i++){ arr.shift() }
結果
| 実装 | 速度 |
|---|---|
| shift | 1.53 ops/sec ±84.16% |
| pop | 36.88 ops/sec ±2.02% |
| spliceによるshift | 0.94 ops/sec ±161.84% |
| spliceによるpop | 22.37 ops/sec ±2.04% |
shiftは要素数に線形の時間が最悪の場合かかります．この例では，shiftはpopの24倍ほど遅くなりました．
spliceは遅いので使う必要がなさそうです．
キューの実装
このshiftの遅さに耐えられない場合は，キューを自分で実装することになります．
実装はいくつか考えられます．
スタック2つでキュー
スタック2つをキューとして扱う事ができます．
キューを{head:[], tail:[]}と初期化します．
エンキューはtailにpushします．
{head:[], tail:[]}{head:[], tail:[1]}{head:[], tail:[1,2]}{head:[], tail:[1,2,3]}
デキューはheadからpopします． もしheadが空の場合は，tailの要素の順番を逆にしてheadに付け加えます
{head:[], tail:[1,2,3]}{head:[3,2], tail:[]}→ 1{head:[3], tail:[]}→ 2{head:[], tail:[]}→ 3
この実装の計算量は，ならし計算量の問題として有名です． tailの要素の順番を逆にするところで線形時間かかるようにみえます． しかし，操作の回数でならすことで，定数時間となります．
リングバッファ
もし，キューの最大要素数がわかっているなら，リングバッファで実装するのが自然です．
初期化は{data: [?,?,?,?,?], head:0, tail:0}です．
エンキューでは，data[tail]に値を書き込み，tailを1増やします．
このとき，tailが最大要素数より大きいならtailを0とします．
{data: [?,?,?,?,?], head:0, tail:0}{data: [1,?,?,?,?], head:0, tail:1}{data: [1,2,?,?,?], head:0, tail:2}{data: [1,2,3,?,?], head:0, tail:3}
デキューでは，data[head]から値を取り出し，headを1増やします．
このとき，headが最大要素数より大きいならheadを0とします．
{data: [1,2,3,?,?], head:0, tail:3}{data: [1,2,3,?,?], head:1, tail:3}→ 1{data: [1,2,3,?,?], head:2, tail:3}→ 2{data: [1,2,3,?,?], head:3, tail:3}→ 3
計算量は定数です．しかし，この方法は予め要素数がわかっているときしか使えません
このdataは要素数固定なので，ArrayとInt32Arrayの両方で比較しました．
それぞれのキュー実装の計測
それぞれのキューに対してエンキュー75%，デキュー25%の確率(線形合同法)で100000回実行します．
const n = 100000; function zigzag(n, init, shift, push) { let seed = 12345; let size = 0; let last = -1; for (let i = 0; i < n; i++) { if (size > 0 && (seed & 20480) == 0) { // 2^12+2^14=20480 last = shift(init); size--; } else { push(init,seed); size++; } seed = (seed * 1664525 + 1013904223) & 2147483647; } return last; }
結果
Run results for: Queue Implement by 2 Stacks - MeasureThat.net
| 実装 | 速度 |
|---|---|
| 素のArray | 10.24 ops/sec ±2.73% |
| 2スタック | 233 ops/sec ±1.65% |
| リングバッファ | 413 ops/sec ±1.75% |
| リングInt32Array | 417 ops/sec ±2.21% |
予想通りInt32Arrayのリングバッファが一番速いです．
しかし，2スタックの実装も十分に速いです． 要素数が可変というメリットがあるので，キューが必要になった場合は2スタック実装がおすすめです，
おまけ．wasm
高速なキューが必要になるほど複雑なロジックをJSで書くことを諦めましょう．
Rustで書いてwasmにすると 1,725 ops/sec ±1.61% でした． リングバッファの4倍ぐらい速いです．
このMDN通りにすれば，すぐにwasmを使い始められます．
素朴な実装です．
extern crate wasm_bindgen; use wasm_bindgen::prelude::*; use std::collections::VecDeque; #[wasm_bindgen] pub fn zigzag(n: i32) -> i32 { let mut vec = VecDeque::new(); let mut seed = 12345; let mut size = 0; let mut last = -1; for _ in 0..n { if size > 0 && (seed & 20480) == 0 { last = vec.pop_front().unwrap(); size -= 1; } else { vec.push_back(seed); size += 1; } seed = (seed * 1664525 + 1013904223) & 2147483647; } return last; }
unpkgからwasmを読み込む方法です．
(async () => { const importObject = { imports: { } }; const ex = 'https://unpkg.com/@wass80/wasm-queue/wasm_queue_bg.wasm'; const wasm_obj = await WebAssembly.instantiateStreaming(fetch(ex), importObject); const wasm = wasm_obj.instance.exports; window.wasm_zigzag = wasm.zigzag })();
