wassup?

プログラミング、ボドゲ、ボカロ

JSのArray#shiftが遅いのでキューを頑張る.結果wasmは速い.

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

結果

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