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

# はじめに

競プロ([AtCoder](https://atcoder.jp/))をやっていると、配列の要素数や検索回数が大きい場合、重複削除目的ではなく高速化のために、配列(`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`)より速いのか検証しました。

## 結論

:::note info
検索値が数値の場合で以下に記載した条件の場合の結論です
`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<br>300|100<br>30|
|Kotlin|Map#[]|10<br>100|100<br>30|

## 環境

* PC:MacBook Air M1 2020, メモリ 16GB, OS 14.6.1
* Ruby 3.2.2
* [Bun 1.1.26](https://bun.sh)(Javascriptの実行環境)
* Kotlin 1.8.20, SDK corretto18
* IntelliJ IDEA 2024.2.1 (Community Edition)


## 計測

### 方法

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

    ```javascript:例：配列の要素数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:Ruby
        TargetObj = Struct.new(:value)
        ```
        ```javascript:Javascript
        { "value": number }
        ```
        ```kotlin:Kotlin
        data class TargetObj(val value: Int)
        ```

## 各言語の対象メソッドと計測ライブラリ

### Ruby

#### 対象メソッド

* [Array#include?](https://docs.ruby-lang.org/ja/latest/method/Array/i/include=3f.html) vs [Set#include?](https://docs.ruby-lang.org/ja/latest/method/Set/i/=3d=3d=3d.html)
* [Array#find](https://docs.ruby-lang.org/ja/latest/method/Enumerable/i/detect.html) vs [Hash#[]](https://docs.ruby-lang.org/ja/latest/method/Hash/i/=5b=5d.html)

#### 計測ライブラリ

* `benchmark`ライブラリの[Benchmark.realtime](https://docs.ruby-lang.org/ja/latest/class/Benchmark.html)を使用


### Javascript

#### 対象メソッド

* [Array#includes](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/includes) vs [Set#has](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Set/has)
* [Array#find](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/find) vs [Map#get](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Map/get)

#### 計測ライブラリ

* `perf_hooks`モジュールの[performance.now](https://nodejs.org/api/perf_hooks.html#performancenow)を使用

### Kotlin

#### 対象メソッド

`Array`より`List`を使用することが多いため`List`との比較としました

* [List#contains](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-list/contains.html) vs [Set#contains](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-set/contains.html)
* [List#find](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/find.html) vs [Map#[]](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-map/get.html)

#### 計測ライブラリ

* [measureNanoTime](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.system/measure-nano-time.html)関数を使用

### 解析

* `Array`(or `List`)の実行時間に対する`Set` or `Map`(or `Hash`)の実行時間の比で表しました
* **1未満**の値であれば **`Set` or `Map`(or `Hash`)の方が** `Array`より**速い**ことになります
* 解析には、`Python 3.11.9`で`pandas`, `matplotlib`, `seaborn`等を用いました

## 結果

:::note info
記載した条件のもと行った結果です
実行環境や検索する値の型によっても結果は変わります
:::


### Ruby

#### [Array#include?](https://docs.ruby-lang.org/ja/latest/method/Array/i/include=3f.html) vs [Set#include?](https://docs.ruby-lang.org/ja/latest/method/Set/i/=3d=3d=3d.html)

* 配列の要素数が30以上、かつ検索回数が100回以上であれば`Set`に変換しても良さそう

![array_include_vs_set_include_ratio_heatmap_ruby.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2493295/e1dd3f0c-44b2-a0c7-806f-a0549aaa23fc.png)

#### [Array#find](https://docs.ruby-lang.org/ja/latest/method/Enumerable/i/detect.html) vs [Hash#[]](https://docs.ruby-lang.org/ja/latest/method/Hash/i/=5b=5d.html)

* 10回以上検索するなら、`Hash`に変換する方が良さそう

![array_find_vs_hash_[]_ratio_heatmap_ruby.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2493295/e9b808e0-ce82-da1f-b1f4-6d567e7b29ec.png)

### Javascript

:::note info
Bun 1.1.26 で実行
:::


#### [Array#includes](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/includes) vs [Set#has](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Set/has)

* 検索回数が100回以上であれば配列の要素数に関係なく、`Set`に変換する方が良さそう
* `Set`に変換した後での存在確認は当然`Array`よりも`Set`の方が断然速い

```plantuml
@startuml
<style>
root {
  Padding 0
  Margin 0
}
caption {
  FontSize 17
}
</style>
title <img:https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2493295/4ade0e8e-a5a0-852d-4a4e-7486ea688f59.png>
caption Setの変換も含めて計測
@enduml
```

```plantuml
@startuml
<style>
root {
  Padding 0
  Margin 0
}
caption {
  FontSize 17
}
</style>
title <img:https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2493295/02a87e6e-ace6-7d64-c2d3-425eb34d3aba.png>
caption 事前にSetに変換後計測
@enduml
```

#### [Array#find](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/find) vs [Map#get](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Map/get)

* 30回以上検索するなら配列の要素数に関係なく、`Map`に変換する方が良さそう

![array_find_vs_map_get_ratio_heatmap_javascript.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2493295/bdead799-c57d-952a-f57d-6da8c067ea78.png)

### Kotlin

### [List#contains](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-list/contains.html) vs [Set#contains](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-set/contains.html)

* 配列の要素数が30以上で検索回数が100回以上であれば、`Set`に変換した方が良さそう
* 配列の要素数が300以上であれば、検索回数が30回以上でも、`Set`に変換した方が良さそう

![list_contains_vs_set_contains_ratio_heatmap_kotlin.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2493295/32ff8692-3e0c-2f28-4eff-5f2a4534d698.png)

### [List#find](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/find.html) vs [Map#[]](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-map/get.html)

* 配列の要素数が10以上で検索回数が100回以上であれば、`Map`に変換する方が良さそう
* 配列の要素数が100以上であれば検索回数が30回以上でも`Map`に変換する方が良さそう

![list_find_vs_map_[]_ratio_heatmap_kotlin.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2493295/4bd7f7bd-8297-3ee8-d0f7-2dcabf3382f9.png)

## 感想・問題点

* 処理時間の絶対値は小さな差異でも比としては大きく見えるので注意が必要ですね
* `Javascript`を`Node`で実行すると、注釈[^1]に記載した通り誤差が大きかったので`Bun`で行ったのですが、そのことに関しては、また別の機会に
* 今回はvalueを数値にしましたが、文字列にした場合言語によっては少し結果が異なりました
* 対応のない*t*検定で有意差があるところを境界にしようかと思い行いましたが、多重検定の問題もあるしあまり意味がないかと思いやめました
* 競プロでは、なんでも`Set`や`Map`に変換していましたが、実業務ではスケールを考えて使い分けようと思いました

[^1]:配列数30,000、検索回数10,000で`Array#includes`を`Node v20.10.0`で実行すると、10回(配列は毎回変更、検索値は配列に存在しない値)の試行中最大4桁の差異が出ました。一方、[`Bun 1.1.26`]((https://bun.sh))は誤差が小さかったため選択しました