Arrayのshiftは本当に遅いのかやってみた

ごく単純なキューが欲しくなった。

配列をキューとして扱う

配列のshiftは O(N) だということを知識として知っていたけど、実際に計測してみたことはなかったのでやってみた。

実装

pushが O(1) なのは流石に確認してない。

array.ts

import { measure, dump } from "./measure";

const n = 1000000;

const array = new Array<number>();

for (let i = 1; i <= n; i++) {
    array.push(i);

    if (i % 100000 === 0) {
        measure(i.toString(), () => {
            for (let j = 0; j < 10000; j++) {
                array.shift();
                array.push(0);
            }
        });
    }
}

dump();

計測

% npx ts-node ./array.ts
100000 : 157ms
200000 : 311ms
300000 : 466ms
400000 : 727ms
500000 : 782ms
600000 : 931ms
700000 : 1080ms
800000 : 1241ms
900000 : 1432ms
1000000 : 1608ms

確かに O(N) っぽい。

キューを実装してみる

実装

なーんかもっとスマートに実装できそうな気がするけど、よしとする。
わざわざ QueueNodes でラップしてるのは、一方が undefined だったらもう一方も undefined なことを保証したかったから。

queue.ts

type QueueNode<T> = {
    value: T;
    next?: QueueNode<T>;
};

type QueueNodes<T> = {
    head: QueueNode<T>;
    tail: QueueNode<T>;
};

export class Queue<T> {
    #nodes: QueueNodes<T> | undefined = undefined;

    enqueue(value: T) {
        if (this.#nodes == undefined) {
            const root: QueueNode<T> = { value };
            this.#nodes = { head: root, tail: root };
        } else {
            this.#nodes.tail.next = { value };
            this.#nodes.tail = this.#nodes.tail.next;
        }
    }

    dequeue(): T | undefined {
        if (this.#nodes == undefined) return undefined;
        const value = this.#nodes.head.value;

        if (this.#nodes.head.next == undefined) {
            this.#nodes = undefined;
        } else {
            this.#nodes.head = this.#nodes.head.next;
        }

        return value;
    }
}

計測

main.ts

import assert from "node:assert";
import { measure, dump } from "./measure";

import { Queue } from "./queue";

const n = 1000000;

const a = measure("array", () => {
    const array = new Array<number>();

    for (let i = 0; i < n; i++) {
        array.push(i);
    }

    const result: number[] = [];
    for (let i = 0; i < n; i++) {
        result.push(array.shift()!);
    }
    return result;
});

const b = measure("queue", () => {
    const queue = new Queue<number>();
    
    for (let i = 0; i < n; i++) {
        queue.enqueue(i);
    }

    const result: number[] = [];
    for (let i = 0; i < n; i++) {
        result.push(queue.dequeue()!);
    }
    return result;
});

assert.deepStrictEqual(a, b);

dump();

% npx ts-node ./main.ts
array : 7114ms
queue : 52ms

いい感じ

一応

measure.ts はこんな感じ。

measure.ts

export const measure = <T>(label: string, handler: () => T): T => {
    performance.mark("start");
    const result = handler();
    performance.mark("finish");
    performance.measure(label, "start", "finish");
    return result;
};
export const dump = () => console.info(performance.getEntriesByType("measure").map(({name, duration}) => `${name} : ${Math.floor(duration)}ms`).join("\n"));