私も JavaScript でキューを実装してみた

これは何？

が面白かったので勝手に参加してみた。

書いたコード

こんなのを書いてみた。

javascript

class QueueNabe {
    slotSize = 0xfeff;
    constructor(){
        this.headNode = this.tailNode = { prev:undefined, next:undefined, slot:Array(this.slotSize) }
    }
    head = 0;
    tail = 0;
    enqueue(x) {
        if (this.slotSize === this.tail) {
            this.tailNode.next = { prev:this.tailNode, next:undefined, slot:Array(this.slotSize) }
            this.tailNode = this.tailNode.next
            this.tail = 0;
        }
        this.tailNode.slot[this.tail++] = x;
    }
    dequeue() {
        if (this.head === this.slotSize) {
            this.headNode = this.headNode.next
            this.headNode.prev = undefined
            this.head = 0
        }
        return this.headNode.slot[this.head++];
    }
}

というわけで、前述の記事で最強っぽかった QueueStack と勝負。

結果

node で試した。
環境は、 MacBook Pro (Apple M1 非 Max）

グラフ

両対数グラフ注意。
最初の何件かは捨てた。

データ

size	QueueStack	QueueNabe:
100	0.6666666666666666	0.3333333333333333
200	0.3333333333333333	0
400	0.3333333333333333	0.3333333333333333
800	0	0.6666666666666666
1600	0.6666666666666666	1
3200	1.6666666666666667	1
6400	2.6666666666666665	1
12800	5.666666666666667	7.333333333333333
25600	14	6.333333333333333
51200	22.333333333333332	13
102400	47	27
204800	91.33333333333333	53.666666666666664
409600	186.66666666666666	111.66666666666667
819200	335.3333333333333	134.66666666666666
1638400	674	216.33333333333334
3276800	1358	436.3333333333333
6553600	2650.6666666666665	882.6666666666666
13107200	5353	1770.3333333333333
26214400		3730
52428800		7612

解説

中身は、連結リスト。
連結リストの中に固定長の配列がある。

配列の長さが怪しい定数だけど、ハウスキーピングを入れて 2の16乗 という気分。ハウスキーピングのサイズは知らないので適当に減らした。

で。

enqueue 連結リストの末尾にある配列に追加。配列の末尾を超える場合は連結リストに配列を追加。
dequeue 連結リストの先頭にある配列から取得。配列末尾に到達したら、連結リストの先頭から撤去。

という作戦。

いくら enqueue / dequeue してもコピーは発生しない。

補足

アロケータの感じによっては固定サイズよりうまい方法があると思うけど、固定長にすることでアロケータが速くなりがち。

あるいは。不要になった配列を積極的に再利用するコードを入れると速くなることもあると思う。

あと。
連結リストで書いたけど、リストが大して長くないので、配列で持ってもそんなに変わらないと思う。
短い場合は配列のほうが速いかもね。

最後に

以上です。