JavaScript でキューを実装して性能を比較してみた。

今回は、以下の条件で実装を行った。

クラスとして実装する
1個のデータのエンキューとデキューを行うメソッドをそれぞれ実装する
それ以外のメソッド (要素数、先頭を削除せずに取得など) は実装しない
エラー処理 (空のときにデキューを試みるなど) は行わない

なお、実装で出てくる # つきのメンバ変数はプライベートプロパティである。

方針・実装

配列のpush・shift

配列の末尾に要素を追加するメソッド push をエンキューとして用い、配列の先頭から要素を取り除いて返すメソッド shift をデキューとして用いる。
エンキューとデキューがともに1回メソッドを呼び出すだけで実現でき、シンプルな実装になる。

class QueueShift {
  #q = [];

  enqueue(value) {
    this.#q.push(value);
  }

  dequeue() {
    return this.#q.shift();
  }
}

スタックを用いてプッシュ時退避

スタックによるキューの実装と、キューによるスタックの実装 #Python - Qiita
で紹介されている方法である。

2個のスタックを用意する。(JavaScript の配列は、push と pop ができ、スタックとして用いることができる)
1個のスタックはデータ用、もう1個のスタックはプッシュ時の退避用である。

エンキューは、以下の手順で行う。

データ用のスタックにある全てのデータを、退避用のキューに移す
エンキューするデータをデータ用のスタックにプッシュする
退避用のキューの全てのデータを、データ用のスタックに移す

デキューは、データ用のスタックからポップすることで行う。

エンキューを行う際、いちいち全てのデータを退避する操作が発生するので、見るからに効率が悪そうである。

class QueueStackSave {
  #stack1 = [];
  #stack2 = [];

  enqueue(value) {
    while (this.#stack1.length > 0) {
      this.#stack2.push(this.#stack1.pop());
    }
    this.#stack1.push(value);
    while (this.#stack2.length > 0) {
      this.#stack1.push(this.#stack2.pop());
    }
  }

  dequeue() {
    return this.#stack1.pop();
  }
}

スタック2個

様々なページで紹介されている有名な方法である。

エンキュー用とデキュー用の2本のスタックを用意する。
エンキューは、エンキューするデータをエンキュー用のスタックにプッシュすることで行う。
デキューは、デキュー用のスタックからポップすることで行う。
ただし、デキューしようとした時にデキュー用のスタックが空である場合は、ポップする前にエンキュー用のスタックに入っている全てのデータをデキュー用のスタックに移す。

ポップする際に全てのデータを移す処理が重くなる可能性がある気がするが、それぞれのデータがエンキューされてからデキューされるまでに行われる操作は

エンキュー用のスタックにプッシュされる
エンキュー用のスタックからポップされる
デキュー用のスタックにプッシュされる
デキュー用のスタックにポップされる

という4個だけなので、効率が良さそうである。

class QueueStack {
  #stackPush = [];
  #stackPop = [];

  enqueue(value) {
    this.#stackPush.push(value);
  }

  dequeue() {
    if (this.#stackPop.length === 0) {
      while (this.#stackPush.length > 0) {
        this.#stackPop.push(this.#stackPush.pop());
      }
    }
    return this.#stackPop.pop();
  }
}

Map

TypeScript・JavaScriptでFIFOキューを作る方法 #JavaScript - Qiita
で紹介されている方法である。

次のエンキューおよびデキューに用いるキー (連番) をそれぞれ記録し、それぞれのキーに対応する値は Map (連想配列) を用いて管理する。
キーがオーバーフローする可能性が気になるが、オーバーフローさせるには約9千兆個の要素をエンキューしなければならず、1秒に100万個エンキューしても約285年かかるので、これは杞憂となる可能性が高いだろう。

class QueueMap {
  #data = new Map();
  #nextEnqueueKey = 0;
  #nextDequeueKey = 0;

  enqueue(value) {
    this.#data.set(this.#nextEnqueueKey++, value);
  }

  dequeue() {
    const key = this.#nextDequeueKey++;
    const value = this.#data.get(key);
    this.#data.delete(key);
    return value;
  }
}

Set

JavaScript の Set は、要素を格納された順番に取り出すことができる。
この性質をキューとして用いる。
ただし、同じ値は格納できないため、値を配列に格納することで全て違う値として扱われるようにしている。

class QueueSet {
  #q = new Set();

  enqueue(value) {
    this.#q.add([value]);
  }

  dequeue() {
    const value = this.#q.values().next().value;
    this.#q.delete(value);
    return value[0];
  }
}

性能評価

13th Gen Intel(R) Core(TM) i7-13700H 2.40 GHz を搭載した Windows 11 Home 23H2 のパソコンで、

Firefox 124.0.2
Google Chrome 123.0.6312.123
Node.js v20.12.2

を用いてそれぞれのキューを操作する以下のプログラムを実行し、一連の操作にかかった時間を3回ずつ計測して平均をとった。
行う操作の量を表す引数 size を2倍ずつ増やしていき、かかった時間の平均が5秒以上になったら実験を終了するようにした。

class XorShift {
  #x = 123456789;
  #y = 362436069;
  #z = 521288629;
  #w = 88675123;

  rand() {
    const t = (this.#x ^ (this.#x << 11)) >>> 0;
    this.#x = this.#y;
    this.#y = this.#z;
    this.#z = this.#w;
    this.#w = ((this.#w ^ (this.#w >>> 19)) ^ (t ^ (t >>> 8))) >>> 0;
    return this.#w;
  }
}

function testQueue(queueClass, size) {
  const rngEnqueue = new XorShift();
  const rngDequeue = new XorShift();
  const q = new queueClass();
  const startTime = new Date().getTime();
  for (let i = 0; i < 5 * size; i++) {
    q.enqueue(rngEnqueue.rand());
  }
  for (let i = 0; i < 5; i++) {
    for (let j = 0; j < size; j++) {
      if (q.dequeue() !== rngDequeue.rand()) throw "broken queue";
    }
    for (let j = 0; j < size; j++) {
      q.enqueue(rngEnqueue.rand());
    }
  }
  for (let i = 0; i < 5 * size; i++) {
    if (q.dequeue() !== rngDequeue.rand()) throw "broken queue";
  }
  const endTime = new Date().getTime();
  return endTime - startTime;
}

async function testQueue2(queueClass, timeThreshold, repeatNum) {
  console.log("----- testing " + queueClass.name + " -----");
  let size = 100;
  const resultList = [];
  for (;;) {
    console.log("running with size " + size);
    let sum = 0;
    for (let i = 0; i < repeatNum; i++) {
      const res = testQueue(queueClass, size);
      console.log("run " + i + " / " + repeatNum + " : " + res + "ms");
      await new Promise((resolve) => setTimeout(resolve, 0));
      sum += res;
    }
    const average = sum / repeatNum;
    console.log("average: " + average + "ms");
    resultList.push(average);
    if (average >= timeThreshold) break;
    size *= 2;
  }
  console.log("results for " + queueClass.name + ":");
  console.log(resultList.join("\n"));
}

(async () => {
  const queues = [QueueShift, QueueStackSave, QueueStack, QueueMap, QueueSet];
  for (let i = 0; i < queues.length; i++) {
    await testQueue2(queues[i], 5000, 3);
  }
})();

処理時間の表

Firefox

処理にかかった時間 [ms] は以下のようになった。

size	QueueShift	QueueStackSave	QueueStack	QueueMap	QueueSet
100	1	91	3	2	6
200	2	354	4	4	11
400	6	1408	5	4	35
800	9	5444	10	10	119
1600	18		21	22	562
3200	36		41	42	1638
6400	72		81	84	6302
12800	147		160	167
25600	289		319	334
51200	589		639	669
102400	1222		1270	1335
204800	2638		2535	2773
409600	6026		5071	6047

Google Chrome

処理にかかった時間 [ms] は以下のようになった。

size	QueueShift	QueueStackSave	QueueStack	QueueMap	QueueSet
100	1	5	0	0	1
200	0	22	0	0	2
400	1	98	1	0	2
800	3	485	1	0	6
1600	2	2205	1	1	19
3200	593	9634	3	4	82
6400	2407		5	7	302
12800	9366		6	11	1222
25600			11	26	4596
51200			22	52	21939
102400			45	108
204800			90	316
409600			202	883
819200			364	1900
1638400			736	4374
3276800			1443	エラー
6553600			2722
13107200			エラー

QueueStack では、size = 13107200 において

RangeError: Invalid array length

というエラーが発生した。
また、QueueMap では、size = 3276800 において

RangeError: Map maximum size exceeded

というエラーが発生した。

Node.js

処理にかかった時間 [ms] は以下のようになった。

size	QueueShift	QueueStackSave	QueueStack	QueueMap	QueueSet
100	0	7	0	0	1
200	1	25	1	1	1
400	0	111	1	1	5
800	1	478	1	2	12
1600	1	2050	3	5	23
3200	597	8207	5	8	83
6400	2354		8	10	325
12800	9329		14	13	1293
25600			17	28	5313
51200			22	63
102400			45	153
204800			92	434
409600			180	1129
819200			350	2852
1638400			704	5841
3276800			1439
6553600			2619
13107200			5282

処理時間のグラフ (ランタイム別)

Firefox

Google Chrome

Node.js

処理時間のグラフ (手法別)

QueueShift

QueueStackSave

QueueStack

QueueMap

QueueSet

手法の比較

QueueStackSave は、見た目通り非常に遅かった
QueueShift は、Firefox では QueueMap と同程度の高性能を発揮したものの、その他のランタイムでは QueueStackSave の次に遅かった
QueueSet は、QueueStackSave や Firefox 以外における QueueShift よりは高速に動作したが、QueueStack や QueueMap と比べると圧倒的に遅かった
QueueMap は健闘したが、QueueStack よりも速度や Google Chrome における最大要素数において劣る結果となった
QueueStack は、今回実験を行った全てのランタイムにおいて最速だった

ランタイムの比較

Firefox は配列の shift は効率よくできるようであるが、全体的に Google Chrome や Node.js と比べて JavaScript の実行が遅いようである
QueueShift、QueueStackSave、QueueStack では Google Chrome より Node.js のほうが高速だが、QueueMap および QueueSet では Node.js よち Google Chrome のほうが高速に動作した
- 全体の速度は Google Chrome より Node.js のほうが高速だが、Map や Set の操作は Google Chrome のほうが Node.js より効率が良いと考えられる

結論

配列の shift を用いた実装の QueueShift は、Firefox では高速に動作し、処理の量によっては QueueStack を超える効率を発揮した。とはいえ、その差はあまり大きくなかった。その上、Google Chrome や Node.js ではかなり効率が悪かった。

今回の実験では、配列の push や pop を用いたキューを用いた有名な方法を用いた QueueStack の効率が、データを Map で管理する QueueMap と比べても、かなり良いことがわかった。

よって、JavaScript においてキューを使いたい場合は、QueueStack の手法を用いるのがよいと考えられる。