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

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

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

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

なお、実装で出てくる `#` つきのメンバ変数は[プライベートプロパティ](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Classes/Private_properties)である。

# 方針・実装

## 配列のpush・shift

配列の末尾に要素を追加するメソッド [push](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/push) をエンキューとして用い、配列の先頭から要素を取り除いて返すメソッド [shift](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/shift) をデキューとして用いる。
エンキューとデキューがともに**1回メソッドを呼び出すだけ**で実現でき、**シンプルな実装になる。**

```javascript
class QueueShift {
  #q = [];

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

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

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

[スタックによるキューの実装と、キューによるスタックの実装 #Python - Qiita](https://qiita.com/maebaru/items/579afe3c30edc143968d)
で紹介されている方法である。

2個のスタックを用意する。(JavaScript の配列は、[push](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/push) と [pop](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/pop) ができ、スタックとして用いることができる)
1個のスタックはデータ用、もう1個のスタックはプッシュ時の退避用である。

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

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

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

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

```javascript
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個

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

* [スタック２つでキューを作る #algorithm - Qiita](https://qiita.com/Yuki-Inoue/items/e85175e5fe4634befe66)
* [Stackを使ってQueueを作る - くまメモ](https://kumagi.hatenadiary.org/entry/20130202/1359815752)
* [キューでスタックを、スタックでキューを作る(LeetCode / Implement Stack using Queues, Implement Queue using Stacksより) #Python - Qiita](https://qiita.com/mhiro216/items/adc892ede78eec06ef96)
* [[Python] スタックでキューを作る](https://yottagin.com/?p=9942)

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

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

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

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

```javascript
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](https://qiita.com/tronicboy/items/a77ca847245a96c61fe5)
で紹介されている方法である。

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

```javascript
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](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Set) は、要素を格納された順番に取り出すことができる。
この性質をキューとして用いる。
ただし、同じ値は格納できないため、値を配列に格納することで全て違う値として扱われるようにしている。

```javascript
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秒以上になったら実験を終了するようにした。

```javascript
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

![Firefox における処理時間 (小)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/bfdd1ae2-c70f-e73c-f3cd-9b41c8652354.png)
![Firefox における処理時間 (中)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/247865f7-b7c7-5298-2a95-5bf3c0aab639.png)
![Firefox における処理時間 (大)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/b3d72a3d-eb4a-69a7-08a8-7268212164d4.png)

### Google Chrome

![Google Chrome における処理時間 (小)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/ff91ef33-7da1-d5b9-ba35-0a9eaf76bcd2.png)
![Google Chrome における処理時間 (中)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/2fd001ff-4bb0-d87d-3055-ffc01f06c60e.png)
![Google Chrome における処理時間 (大)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/2d3679c4-cd3f-101d-ce1c-cb01a14b3275.png)

### Node.js

![Node.js における処理時間 (小)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/06c67c46-dc93-daa9-a134-701ca4f2654f.png)
![Node.js における処理時間 (中)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/7532e054-afd6-61f1-d7dc-9303d5eff985.png)
![Node.js における処理時間 (大)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/d6e86263-3541-326d-023f-adc53daf08b5.png)

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

### QueueShift

![QueueShift における処理時間](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/e5372c6a-ebe9-1dd9-a99d-1f6c942f9a4b.png)

### QueueStackSave

![QueueStackSave における処理時間](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/db9aafee-3eaf-6390-ff46-c0e4e2150722.png)

### QueueStack

![QueueStack における処理時間](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/3941f1d0-1c04-63b6-7092-ed089c9f2508.png)

### QueueMap

![QueueMap における処理時間](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/eb92d998-b31b-99ce-74db-327c676eef14.png)

### QueueSet

![QueueSet における処理時間](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/b24c0f91-4c09-c79b-3ab2-3289841fdc7a.png)

## 手法の比較

* `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` の手法を用いるのがよいと考えられる。