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)

計測結果

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

結論

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

計測方法について

こちらのプロファイラを利用し、次のコードで計算時間を計測しました。
計測した処理部分の抜粋がこちらです。

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);

全文がこちらです

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);
        }
    }
}