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個
様々なページで紹介されている有名な方法である。
- スタック２つでキューを作る #algorithm - Qiita
- Stackを使ってQueueを作る - くまメモ
- キューでスタックを、スタックでキューを作る(LeetCode / Implement Stack using Queues, Implement Queue using Stacksより) #Python - Qiita
- [Python] スタックでキューを作る
エンキュー用とデキュー用の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 より効率が良いと考えられる
- 全体の速度は Google Chrome より Node.js のほうが高速だが、
結論
配列の shift を用いた実装の QueueShift は、Firefox では高速に動作し、処理の量によっては QueueStack を超える効率を発揮した。とはいえ、その差はあまり大きくなかった。その上、Google Chrome や Node.js ではかなり効率が悪かった。
今回の実験では、配列の push や pop を用いたキューを用いた有名な方法を用いた QueueStack の効率が、データを Map で管理する QueueMap と比べても、かなり良いことがわかった。
よって、JavaScript においてキューを使いたい場合は、QueueStack の手法を用いるのがよいと考えられる。