⏱️

JavaScriptのSetの生成が思いのほか遅い

2022/12/20に公開約1,100字

ある配列に特定の要素が含まれるかどうかを確認したいときに、Setを生成するかどうか悩むので、計測してみた

const length = 10_000_000;
const array = [];

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

/**
 * 
 * @param {string} label 
 * @param {() => void} handler 
 */
const measure = (label, handler) => {
    performance.mark("start");
    handler();
    performance.mark("finish");
    performance.measure(label, "start", "finish");
};

measure("set", () => {
    new Set(array);
});
measure("includes", () => {
    array.includes(length);
});

console.info(performance.getEntriesByType("measure").map(({name, duration}) => `${name} : ${Math.floor(duration)}ms`).join("\n"));
% node ./main.js
set : 1416ms
includes : 7ms

setの生成が想像よりもだいぶ遅い
これはnodeだけど、Chrome上で実行しても大体似たような結論になった

これまで5回ぐらい使い回すならSetを作っていたけど、最低でも100回ぐらいは使い回さないと元が取れないことがわかった

ちなみに、配列の中身が全て違うケースはSetの生成コストとしては最悪のようで、配列の要素数が多くても値の被りが多いと結構早くなる

for (let i = 0; i < length; i++) {
    array.push(100);
}
% node ./main.js
set : 57ms
includes : 5ms

こういうケースなら10回ぐらい使いまわせば元がとれる
要素がどれぐらい被っている想定かによってSetを使うかどうかの判断も変わってきそう

結論

要素が全く被っていない想定の場合、100回ぐらい使い回すならSetを使うのもあり
要素がほぼ被っている想定の場合、10回ぐらい使い回すならSetを使うのもあり

Discussion

ログインするとコメントできます