私も JavaScript で 両端キューを書いてみた

これは何？

を拝見して。

そういえば、 C++ の deque のようなものって書いたことないなと思って書いてみた。

実装方針

deque のソースコードを見たわけじゃないけど、こんな感じじゃないかなと思っている。

• オブジェクトはスロットを何面か持っている。スロットは確保した時点でサイズ固定の配列。
• 一連のスロットは、概ね単なる配列として持つが、先頭より前とか末尾よりあとに使われないスロットを死蔵することができるようにする。
• バッファの先頭は、先頭のスロットに、バッファの末尾は末尾のスロットにある。
• 末尾への追記を続けてスロットが満タンになったらスロットを末尾に追加（死蔵スロットがあればそれを利用）。
• 先頭への追記を続けてスロットが満タンになったらスロットを先頭に追加（死蔵スロットがあればそれを利用）。
• 末尾からの撤去を続けて末尾のスロットがからっぽになったら、末尾のスロットを撤去。撤去されたスロットは開放されず、死蔵される。
• 先頭からの撤去を続けて先頭のスロットがからっぽになったら、先頭のスロットを撤去。撤去されたスロットは開放されず、死蔵される。
• スロット撤去時に死蔵スロットがたくさんあったら開放するが、死蔵スロットをゼロ個にはしない。
• 新たに作るスロットに格納できる要素の数は、下限を設けつつ、deque の要素数ぐらいのサイズにする。

スロットは概ね単なる配列なので、先頭へのスロット追加時に、スロット数を $S$ とすると $ \mathcal{O} (S)$ の計算が必要になるけど、$S$ 自体が小さいし、発生頻度も低いので平均的には $ \mathcal{O} (1)$ で計算できていると思う。

コードは、スロット部とスロットを利用した deque 部がそれぞれ 50行弱、合わせて 100行弱になった。もうちょっと短く書けると思ったんだけどなぁ。

実装は以下。

100行弱の JavaScript による実装

JavaScript_for_node

'use strict';

const newDeque = () => {
    const newSlots = () => {
        const slots = {
            m: [],
            beginIx: 0,
            endIx: 0,
        };
        slots.front = () => { return slots.m[slots.beginIx]; };
        slots.back = () => { return slots.m[slots.endIx - 1]; };
        slots.size = () => { return slots.endIx - slots.beginIx; };
        slots.newBuffer = (s) => {
            return Array(Math.max(1<<10, s));
        };
        slots.push_back = (s) => {
            if (slots.endIx === slots.m.length) {
                slots.m.push(slots.newBuffer(s));
                // console.log(slots.m.map( e=>e.length));
            }
            slots.endIx++;
        };
        slots.push_front = (s) => {
            if (slots.beginIx === 0) {
                slots.m.unshift(slots.newBuffer(s));
                // console.log(slots.m.map( e=>e.length));
                slots.endIx++;
            } else {
                --slots.beginIx;
            }
        };
        slots.pop_back = () => {
            --slots.endIx;
            if (slots.endIx + 4 < slots.m.length) {
                slots.m = slots.m.slice(0, slots.endIx + 2);
            }
        };
        slots.pop_front = () => {
            ++slots.beginIx;
            if (4 < slots.beginIx) {
                const s = slots.size();
                slots.m = slots.m.slice(slots.beginIx - 2);
                slots.beginIx = 2;
                slots.endIx = 2 + s;
            }
        };
        return slots;
    };


    const o = {
        slots: newSlots(),
        size: 0,
        headS: undefined,
        tailS: undefined,
        head: undefined,
        tail: undefined,
        itemCount: 0,
    };
    o.push = (x) => {
        if (o.slots.size() === 0 || o.slots.back().length === o.tail) {
            o.slots.push_back(o.size());
            o.tail = 0;
            if (o.head === undefined) { o.head = 0; }
        }
        o.slots.back()[o.tail++] = x;
        ++o.itemCount;
    };
    o.pop = () => {
        if (o.size === 0) { return undefined; }
        if (o.tail === 0) {
            o.slots.pop_back();
            o.tail = o.slots.back().length;
        }
        --o.itemCount;
        return o.slots.back()[--o.tail];
    };
    o.shift = () => {
        if (o.size === 0) { return undefined; }
        if (o.head === o.slots.front().length) {
            o.slots.pop_front();
            o.head = 0;
        }
        --o.itemCount;
        return o.slots.front()[o.head++];
    };
    o.unshift = (x) => {
        if (o.slots.size() === 0 || o.head === 0) {
            o.slots.push_front(o.size());
            o.head = o.slots.front().length;
            if (o.tail === undefined) { o.tail = o.head; }
        }
        o.slots.front()[--o.head] = x;
        ++o.itemCount;
    };
    o.size = () => { return o.itemCount; };
    return o;
};

module.exports = newDeque;

処理時間

こんな方法で実行時間を測ってみた。

JavaScript_for_node

'use strict';

const newQueue = require('./'+process.argv[2]);
const loopCount = 2500;

const compareElements = (q) => {
    while (q.size() != 0) {
        const b = (q.size() % 2 == 0);
        b ? q.pop() : q.shift();
    }
};

const test = () => {
    console.log("test");
    const q = newQueue();
    let ix = 0;
    for (let c = 0; c < loopCount; ++c) {
        q.push(++ix);
        for (let i = 0; i < loopCount; ++i) {
            q.unshift(++ix);
            q.pop();
        }
    }
    compareElements(q);
};

test();

この計算は前述の記事にとって特に不利なものらしく、実行時間は下表のようになった。

実装	時間
上記の拙作	0.182s
ほぼ Array そのまま	1.143s
前述の記事 の実装	9.849s

改善とか調整とかすべきポイント

スロットの管理を賢くすると速くなるかもしれないけど、大差ないんじゃないかと思う。

あたらしくスロットを作るときのサイズをどうするのが良いのかわからなかった。根拠なく「1024個 と deque に今入っている要素の数の多い方」ということにした。
ほとんどの環境でこれで困ることはないんじゃないかと想像している。
まあこれもユースケースによって何がベストなのか全然変わってくるとは思う。

スロットを積極的に破棄するとメモリ使用量が減り、スロットの破棄を控えると速度が上がる。これもバランスの問題なので用途によってベストの値が違うと思う。

JavaScript に慣れていないので普通こういう書き方しないよ、という意見がありそうだと思っている。

「先頭から N 番目」というアクセスが定数時間でできると思うんだけど、どうやるんだろ。スロットが複数ある場合に先頭からなめる以外にいい方法があるんだろうか。まあ先頭からなめてもスロット数はそんなに多くならないから困らないわけだけど。

そもそも

そもそも。
格納する要素数の最大値が既知ならこんな複雑なものを使う必要はなく、リングバッファを使うのが正解。