【TypeScript , JavaScript】includes() は使うべきか？
includes() の罠
const alphabet = [
'a', 'b', 'c', 'd', 'e', 'f', ....
];
配列に指定の値が存在しているか確認する場合、includes 関数を使うことが多いです
しかし、実際これはどうなんだ・・・？というのが今回のお題です。
ECMAScriptの仕様書を読んでみると、includes が実際にどういったことをしているかがわかります
- Repeat, while k < len,
a. Let elementK be ? Get(O, ! ToString(𝔽(k))).
b. If SameValueZero(searchElement, elementK) is true, return true.
c. Set k to k + 1.
注目すべきは10番目、ループ while を使って配列内の値を検証しているようです。
配列の個数が決まっていれば大したことはありませんが、ループ内でincludeを使っていたりすると二重ループが発生していることになります。
count numbers = [
1, 3, 5, 7, 9
];
for (let i = 0; i < 10; i++ ) {
console.log(numbers.includes(i));
}
見た目だとループ回数は10回だが・・・
includes内も含めると、最大50回のループが発生している！？！？
※ includes で最大回数のループが発生した場合を想定
よく言われる時間計算量の O(N^2)問題 ですね（最近知った）。
どうすればループ数がすくなるなるのか
includes を使わないとしても、for や while を使ってしまうと結果は同じです。
もし検証する配列が事前に決まっていれば キーにする ことで解決できます。
in 演算子
const numbers = {
1: true,
3: true,
5: true,
7: true,
9: true,
}
for (let i = 0; i < 10; i++ ) {
console.log(i in numbers);
}
これだと内部でループが発生しないので、見た目通り10回のループで済ませることができます。
obj[k] !== undefined
# TypeScriptの場合は型宣言を忘れずに...
const numbers: { [key: number]: boolean } = {
1: true,
3: true,
5: true,
7: true,
9: true,
}
for (let i = 0; i < 10; i++ ) {
console.log(numbers[i] !== undefined);
}
これでも、見た目通り10回のループで検証できます。
in と !== undefined は どっちが速いのか
結論：ほぼ変わりません
なので、大抵の場合はスッキリかける in を使うほうが良いのかなと思いました
※ 値に undefined を入れている可能性も0ではないので、使い勝手も良いでしょう
in で 計測
const list: {[key: number]: boolean} = {};
for (let i = 0; i < 100000000; i++) {
list[i] = true;
}
console.log('setup clear');
let s = 0;
let e = 0;
console.log('in');
s = performance.now();
console.log(256 in list);
e = performance.now();
console.log(e - s);
# 結果
0.11916299164295197
!== undefined で 計測
const list: {[key: number]: boolean} = {};
for (let i = 0; i < 100000000; i++) {
list[i] = true;
}
let s = 0;
let e = 0;
console.log('!== undefined');
s = performance.now();
console.log(list[256] !== undefined);
e = performance.now();
console.log(e - s);
# 結果
0.11562301218509674
まとめ
今回は、配列の値をキーにするという別アプローチで考えて見ましたが、「そうはいかないんだ！」と言いたい人もいるでしょう。
しかし少し考え方をヒネれば、意外な解決策が出てくるもんです。
膨大な回数になる可能性のあるループを実装する際には、このあたりを意識しておくと将来的に安定したコードになりそうですね。
見にくくなりすぎない程度に、実装時は気をつけてみてください。
追記
コメントより Setオブジェクト が使えるとお声を頂いたので、こちらも紹介しておきます。
Set
const obj = new Set();
obj.add(10);
obj.has(10);
# true
Setオブジェクトでは値を一意に保ってくれるので、キー検索するのと同じように判定ができます。
また、hasメソッドでは内部でループが発生していないので、for文などの内部で使用しても多重ループになりません。
意外な落とし穴が・・・
同じように時間計測すると...
const setObj = new Set();
for (let i = 0; i < 100000000; i++) {
setObj.add(i);
}
let s = 0;
let e = 0;
console.log('!== undefined');
s = performance.now();
console.log(setObj.has(256));
e = performance.now();
console.log(e - s);
# 結果
RangeError: Set maximum size exceeded
まさかのオーバーフロー( ^ω^)ﾅﾝﾔﾃ...
for (let i = 0; i < 16777216; i++) {
setObj.add(i);
}
# OK
for (let i = 0; i < 16777217; i++) {
setObj.add(i);
}
# RangeError: Set maximum size exceeded
16,777,216 個の要素までは通ったので、キリ良く上限っぽいですね
16進数：FFFFFF
10進数：16777215
2進数 ：1111 1111 1111 1111 1111 1111
16進数：1000000
10進数：16777216
2進数 ：1 0000 0000 0000 0000 0000 0000
FFFFFF は 3byte なので、個数上限が 3byte ・・・？
計測結果
const setObj = new Set();
for (let i = 0; i < 16777216; i++) {
setObj.add(i);
}
console.log('setup clear');
let s = 0;
let e = 0;
console.log('set');
s = performance.now();
console.log(setObj.has(512));
e = performance.now();
console.log(e - s);
# 結果
0.11362099647521973
速度も大差ないので問題なさそうですね。
値の検索だと、Setの方が使い勝手は良さそうです。
ホワイトボード
落書き置き場
Discussion
Setオブジェクトを使うのはいかがでしょうか？
ありがとうございます！
Setオブジェクトも使えますね、載せておきますm(_ _)m
ちなみに、同じように 100,000,000 個で試すと
Set maximum size exceededになった・・・16,777,216個まで入れられたので、個数上限が
FFFFFFっぽいです（初めて知った）