⏱️

JavaScriptで集合に要素が含まれるかを判定する速度比較

2022/12/22に公開

先日以下の記事を投稿したところ、そもそもSetよりobjectの方が速いということを教えてもらったので測定してみた
https://zenn.dev/malt03/articles/df7bb357240756

import assert from "node:assert";

const length = 10_000_000;
/** @type number[] */
const array = [];

for (let i = 0; i < length; i++) {
    array.push(Math.floor(Math.random() * length));
}

/**
 * @template T
 * @param {string} label 
 * @param {() => T} handler 
 * @returns {T}
 */
const measure = (label, handler) => {
    performance.mark("start");
    const result = handler();
    performance.mark("finish");
    performance.measure(label, "start", "finish");
    return result;
};

const set = measure("new Set", () => new Set(array));
const object = measure("create object", () => {
    /** @type Record<number, boolean> */
    const object = {};
    for (const value of array) object[value] = true;
    return object;
});

const searchNum = 10_000_000;
const counter0 = measure("Set.has", () => {
    let counter = 0;
    for (let i = 0; i < searchNum; i++) if (set.has(i)) counter ++;
    return counter;
});
const counter1 = measure("object in", () => {
    let counter = 0;
    for (let i = 0; i < searchNum; i++) if (i in object) counter ++;
    return counter;
});
const counter2 = measure("object.hasOwnProperty", () => {
    let counter = 0;
    for (let i = 0; i < searchNum; i++) if (object.hasOwnProperty(i)) counter ++;
    return counter;
});

assert.equal(counter0, counter1);
assert.equal(counter0, counter2);

console.info(performance.getEntriesByType("measure").map(({name, duration}) => `${name} : ${Math.floor(duration)}ms`).join("\n"));
% node set-vs-object.mjs
new Set : 1154ms
create object : 1265ms
Set.has : 937ms
object in : 35ms
object.hasOwnProperty : 97ms

ほんとだ…Set遅い…というよりobjectが速い…しかも圧倒的に…
でも可読性で言うとSetの方が良いことは間違いないし…
基本的にはSetを使いつつ、パフォーマンスが絶対優先の場合はobjectを使っていくのがいいかなと思う

Discussion