🔍

長い配列内要素の存在チェックにはSetがおすすめ

2023/12/14に公開

JavaScript

tech

「配列の中に特定の値が存在するか」というチェックには

Array.prototype.includes

をよく使うと思うのですが、実装中の機能で

(A) 数千件のデータの中に該当する1件があるかを調べる
(B) Aの処理を数千件回す

という処理をincludesを使って書いていて、
直感的に「これは遅いんじゃないか」と思ったので、
普段あまり使わないSetを検証してみたら
includesよりもかなり速かったでメモ。

Array.prototype.includes

Set

検証コード

// テストデータの生成
const N = 1000000; // テストデータの件数
const testData = Array.from({ length: N }, (_, i) => `item${i}`);
const searchItem = 'item999999'; // 検索するアイテム

// 配列での検索
const startTimeArray = performance.now();
const existsInArray = testData.includes(searchItem);
const endTimeArray = performance.now();
console.log(`Array search: ${existsInArray}, Time: ${endTimeArray - startTimeArray} ms`);

// Setでの検索
const testDataSet = new Set(testData);
const startTimeSet = performance.now();
const existsInSet = testDataSet.has(searchItem);
const endTimeSet = performance.now();
console.log(`Set search: ${existsInSet}, Time: ${endTimeSet - startTimeSet} ms`);

検証結果



### 10件
'Array search: false, Time: 0.0029579997062683105 ms' 
'Set search: false, Time: 0.0013749971985816956 ms' 

### 100件
'Array search: false, Time: 0.002749994397163391 ms' 
'Set search: false, Time: 0.0015420019626617432 ms' 

### 1000件
'Array search: false, Time: 0.004041999578475952 ms'  
'Set search: false, Time: 0.0014159977436065674 ms' 

### 10000件
'Array search: false, Time: 0.013416998088359833 ms'  
'Set search: false, Time: 0.0015420019626617432 ms' 

### 100000件
'Array search: false, Time: 0.13016699999570847 ms'  
'Set search: false, Time: 0.0022919997572898865 ms' 

### 1000000件
'Array search: true, Time: 2.483542002737522 ms' 
'Set search: true, Time: 0.005458995699882507 ms'

件数が多くなると如実に違いが出ますね。。

ただ、先ほどのコード、配列をSetに変換する処理の時間を入れてなかったので
それも含めると、


### 1000000件

'Array search: true, Time: 2.199583001434803 ms'  
'Set search: true, Time: 211.06970800459385 ms'

逆転しました。
大きい配列を変換する処理にはそれなりに時間がかかるようです。
なので一概にSetにすればいい、というわけではありません。

一度、Setに変換してしまえばその後のチェックが爆速なので、

小さい配列の時は、includes
大きい配列、かつ何度もチェックする必要がある時はSet

にするのが良さそうです。

Array.prototype.includes

Set

検証コード

検証結果

Discussion