とりあえず計測

高速化の議論をするときは，必ず始めにベンチマークを取りましょう．

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

結果

www.measurethat.net

実装	速度
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を使い始められます．

developer.mozilla.org

素朴な実装です．

github.com

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