C#でHashSetを使う方が得になるボーダーライン

# はじめに
C#でコレクション内の要素を取得する際、`List`の場合は配列の捜査が必要なため`O(N)`の計算時間がかかりますが、`HashSet`を作ることで`O(1)`で検索できるので、何度も計算する場合は`HashSet`を作成するのが良いです。
しかし、`HashSet`を作成するのにも多少の（リストのコピーと比べるとかなり大きな）計算コストがかかってしまいます。そこで、`HashSet`を作成しても得ができるボーダーラインを調べてみました。

計測ツールの理由から、`Unity`のエディタで実行していますが、他の環境でも結果にさほど差は無いとは思います。

結論を先に書いてしまうと、要素の検索回数が **10~20回** あたりがボーダーラインになります。


# 実験
整数のリスト`List<int>`から要素を検索する計算時間と、リストからハッシュ`HashSet<int>`を作成してから検索する計算時間を比較しました。 `検索回数` と `コレクションの要素数` を変化させながら調べました。
コレクションは`0`から`N-1`までの数列で、検索する値は常に`N/2`を用いました。

#### 実行環境
Windows11, Unity Editorの Play Modeで実行。
Unityのバージョン: 2022.2.4f1 (Roslyn, C#9.0)
CPU: Intel® Core™ i9-9900KF (クロック数: 3.6GHz. 最大5.0GHz)

## 計測結果
![スクリーンショット 2023-03-25 201343.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606045/b161ab59-e123-fd01-856f-1dd4d6413f41.jpeg)

計測した結果、画像のような結果となりました（画像を拡大してご確認下さい）。縦軸が検索回数 (`Contains(N/2)`の実行回数)、横軸がコレクションのサイズ(`N`)です。
`List`のほうが早ければ青、`HashSet`のほうが早ければ赤で表示しています。
概ね要素の検索回数が **10回と20回の間** で勝敗が分かれています。実行時間を詳細に見てみると、要素数が`10,000,000`くらいになると、Hashが衝突してパフォーマンスが鈍くなっていることも確認できます。

## 結論
-  コレクションサイズが大きい方が、`Hash`の効果は（当然）大きい。ただし、いずれのサイズでも検索回数が **10回以下** なら`HashSet`を作成するコストのほうが大きい。

## 計測方法について
[こちらのプロファイラ](https://qiita.com/uminohiyoko/items/f9b6a4e09082ce09cb57)を利用し、次のコードで計算時間を計測しました。
計測した処理部分の抜粋がこちらです。
```C#
var myList = Enumerable.Range(0, collectionSize).ToList();
var task1 = new MeasureTimeTask(() =>
{
    for (int i = 0; i < loopNum; i++)
    {
        _ = myList.Contains(collectionSize/2);
    }  
}, $"List");
var task2 = new MeasureTimeTask(() =>
{
    var hashSet = myList.ToHashSet();
    for (int i = 0; i < loopNum; i++)
    {
        _ = hashSet.Contains(collectionSize/2);
    }  
}, $"HashSet");
yield return new CompareTimeTask(task1, task2);
```

<details><summary>全文がこちらです</summary><div>

``` HashSetProfiler.cs
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
using IMGUIProfiler;

public class HashSetProfiler : MonoBehaviour
{
    private MultiProfilerHandler _profilerHandler;
    private static readonly double[] loopNumList = new double[] {1e0, 1e1, 2e1, 5e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8}; 

    private void Start()
    {
        Application.targetFrameRate = 60; // 目標FPSを設定

        var collectionSizeList = new int[]
        {
            10,
            100,
            1000,
            10000,
            100000,
            1000000,
            10000000,
        };

        _profilerHandler = new MultiProfilerHandler(
            collectionSizeList.Select(size => new MultiTaskProfiler(CreateComparableLoopTasks(size), 
                $"collection size of: {size:N0}"))
                .Prepend(new MultiTaskProfiler(loopNumList.Select(size =>
                    new ShowDescriptionTask($"\n要素の検索回数: {size:N0}\n")), "実行数 \\ Collectionサイズ"))
            );
    }

    private void OnGUI()
    {
        _profilerHandler.OnGUI();
    }

    private void Update()
    {
        _profilerHandler.Update();
    }
    
    // ループ数とコレクションサイズを変えながらListとhashSetの実行時間を比較する
    private IEnumerable<IProfileableTask> CreateComparableLoopTasks(int collectionSize)
    {
        foreach (var loopNum in loopNumList)
        {
            if (loopNum * collectionSize >= 1e10) yield break;
            
            var myList = Enumerable.Range(0, collectionSize).ToList();
            var task1 = new MeasureTimeTask(() =>
            {
                for (int i = 0; i < loopNum; i++)
                {
                    _ = myList.Contains(collectionSize/2);
                }  
            }, $"List");
            var task2 = new MeasureTimeTask(() =>
            {
                var hashSet = myList.ToHashSet();
                for (int i = 0; i < loopNum; i++)
                {
                    _ = hashSet.Contains(collectionSize/2);
                }  
            }, $"HashSet");
            yield return new CompareTimeTask(task1, task2);
        }
    }
}
```

</div></details>