それってSetにする価値ありますかね？

Posted at 2024-10-14

はじめに

競プロ(AtCoder)をやっていると、配列の要素数や検索回数が大きい場合、重複削除目的ではなく高速化のために、配列(Array, List)をSetやMap(Rubyの場合Hash)に変換することはよくあります。

さて、実業務ではどうでしょうか？

実際に扱う配列の要素数、検索回数が$10^6$程度ということはそんなにないかもしれません。
むしろ、要素数や検索回数が100未満ということが多いのではないでしょうか？

では、この場合に、配列をSetやMap(or Hash)に変換する価値はあるのでしょうか？
もちろん、Set, Map(or Hash)になったものを、検索する速度が速いことはわかります。

しかし、SetやMap(or Hash)に変換するにもコストがかかります。

境界はどこでしょうか？

今回、Ruby, Javascript, Kotlinで、Set, Map(or Hash)の使用は要素数・検索回数がどれくらいだとArray(or List)より速いのか検証しました。

結論

検索値が数値の場合で以下に記載した条件の場合の結論です
JavascriptはBunで実行しています
実行環境や検索する値の型によっても境界は異なります

Set, Map(or Hash)に変換する意味がありそうな境界値

言語	class#method	配列の要素数	検索回数
Ruby	Set#include?	30	100
Ruby	Hash#[]	-	10
Javascript	Set#has	-	100
Javascript	Map#get	-	30
Kotlin	Set#contains	30 300	100 30
Kotlin	Map#[]	10 100	100 30

環境

PC:MacBook Air M1 2020, メモリ 16GB, OS 14.6.1
Ruby 3.2.2
Bun 1.1.26(Javascriptの実行環境)
Kotlin 1.8.20, SDK corretto18
IntelliJ IDEA 2024.2.1 (Community Edition) Memory: 4096M

計測

方法

要素数 × 検索回数の組み合わせに対し、それぞれ10回計測し、平均値をとりました
10回の計測は連続では行わず、かつその都度新たなArray(or List)と検索値を作成しました
Set, Map(or Has)に関しては、Array(or List)からの変換の時間も含めています
Ruby, JavascriptはVSCodeのターミナルで、KotlinはIntelliJ IDEAで実行しました

Javascriptの実行環境にはBunを使用しました¹

例：配列の要素数100個, 検索回数100回の場合のイメージ(10回実行し平均を取る)

const array = [...Array(100)].map((_, i) => i);

// Arrayの時間計測開始
for(let i = 0; i < 100; i++) {
    array.includes(i + 100);
}
// Arrayの時間計測終了

// Setの時間計測開始
const set = new Set(array);
for(let i = 0; i < 100; i++) {
    set.has(i + 100);
}
// Setの時間計測終了

Array(or List) vs Set
- 検索する値は配列の要素に存在しない値としました
- 配列の要素を数値(Integer)としました
- 配列の要素に重複なし
Array(or List) vs Map(or Hash)
- 検索する値は配列の要素に存在しない値としました
- 配列の要素に重複なし
- 配列の要素を以下のようなDTOとし、検索値をvalueとしました
  Ruby
```
TargetObj = Struct.new(:value)
```
  Javascript
```
{ "value": number }
```
  Kotlin
```
data class TargetObj(val value: Int)
```