NDW

アプリ開発やトラブルシューティング等のノウハウ、キャンプや登山の紹介や体験談など。

.NET Core 1. システムエンジニアリング 実装技術

.NET Core(C#): List・HashSetのContains性能比較

投稿日:

対象データが処理対象かの判定、データのユニーク化等の用途で、コレクション内のデータ存在チェックを行いたい場合があります。これを実現するために、List/Dictionary等のコレクションクラスのContains()メソッドを使用することになります。
ここでは、各コレクションクラスにおけるContainsの性能測定を行いました。

要約

  • 測定条件は次の通りです。
    • コレクションから文字列キーを検索する際の処理時間を計測する。
    • 対象のコレクションは、List, HaseSet, Dictionary(キーのみ)とする。
    • ランダムな文字列キーをN個格納したコレクションから、ランダムな文字列キーをN回検索する。
      (合計の照合回数は N × N = N2回)
    • 動作確認のため少なくても1件は合致させる。
    • 使用する文字列キーはそれぞれ、半角数字・英大小文字を含む4桁文字とする。
  • 実行環境は次の通りです。
    ハードウェア CPU: AMD Ryzen 5 3400G, MEM: 16GB, SSD: 130GB
    OS Windows 10(64ビット)
    IDE Microsoft Visual Studio Community 2019(16.8.5) + C#(8.0)
  • 測定結果は次の通りです。
    ※N個のキーが登録されたコレクションからキーをN回検索する場合の照合回数を「N2」と表記しています。
    ※計測時間の単位はミリ秒であり、[ms]と表記しています。
    ※計測時間が1 [ms]未満の場合は0 [ms]と表記しています。
    種類 照合回数
    1002 1,0002 10,0002 100,0002
    List 0 [ms] 9 [ms] 720 [ms] 73,102 [ms]
    HashSet 0 [ms] 0 [ms] 0 [ms] 7 [ms]
    Dictionary 0 [ms] 0 [ms] 0 [ms] 7 [ms]
  • 考察

詳細

サンプルコード

    /// <summary>
    /// 同一測定の実行回数
    /// </summary>
    /// <remarks>複数回測定した平均時間を採用</remarks>
    private const int RepeatCount = 3;

    /// <summary>
    /// キーで使用する文字
    /// </summary>
    private const string KeyChars =
        "0123456789" +
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
        "abcdefghijklmnopqrstuvwxyz";

    /// <summary>
    /// キーで使用する文字
    /// </summary>
    private readonly char[] chars = KeyChars.ToCharArray();

    [Theory(DisplayName = "Contains性能比較")]
    [InlineData(0_000_100)]
    [InlineData(0_001_000)]
    [InlineData(0_010_000)]
    [InlineData(0_100_000)]
    // [InlineData(8, 1_000_000)] // 時間がかかりすぎるのでスキップ
    public void CompareContains(long bucketSize)
    {
        // 検索するキー一覧(各テストで共通)
        var keySize = 4;
        var scans = CreateRandomKeyList(keySize, bucketSize);
        var keys = CreateRandomKeyList(keySize, bucketSize);
        scans[scans.Count / 2] = keys[keys.Count / 2]; // 少なくても1件は合致させる

        // Listの評価
        var list = new List<string>(keys);
        ScanEnumerable(list, scans, "List<string>");

        // HashSetの評価
        var enumHashSet = new HashSet<string>(keys);
        ScanEnumerable(enumHashSet, scans, "HashSet<string>");

        // Dictionaryの評価
        var dictionary = keys.ToDictionary(p => p, p => (object)null /* dummy */);
        ScanDictionary(dictionary, scans, "Dictionary<string, object>");
    }

    /// <summary>
    /// IEnumerableを使ったキー検索時間を測定する。
    /// </summary>
    /// <typeparam name="T">検索対象コレクションの型</typeparam>
    /// <param name="enums">検索対象コレクション</param>
    /// <param name="scans">検索するキーのリスト</param>
    /// <param name="prefix">実行結果出力時の接頭文言</param>
    private void ScanEnumerable<T>(IEnumerable<T> enums, List<T> scans, string prefix)
    {
        var watcher = new Stopwatch();
        var elapsed = 0L;
        var hitCount = 0L;
        for (var i = 0; i < RepeatCount; i++)
        {
            GC.Collect(); // テスト前にメモリ状態の初期化を試行

            watcher.Restart();
            foreach (var key in scans) if (enums.Contains(key)) hitCount++;
            watcher.Stop();
            elapsed += watcher.ElapsedMilliseconds;
        }
        var avgElapsed = Math.Ceiling((double)(elapsed / RepeatCount));
        var avgHitCount = Math.Ceiling((double)(hitCount / RepeatCount));
        Console.WriteLine(
            $"{prefix}({enums.Count()}x{scans.Count}) -> elapsed={avgElapsed:#,0}[ms], hit={avgHitCount:#,0}");
    }

    /// <summary>
    /// ディクショナリを使ったキー検索時間を測定する。
    /// </summary>
    /// <typeparam name="K">検索対象ディクショナリのキー型</typeparam>
    /// <typeparam name="V">検索対象ディクショナリのキー型</typeparam>
    /// <param name="dic">検索対象ディクショナリ</param>
    /// <param name="scans">検索するキーのリスト</param>
    /// <param name="prefix">実行結果出力時の接頭文言</param>        
    private void ScanDictionary<K, V>(Dictionary<K, V> dic, List<K> scans, string prefix)
    {
        var watcher = new Stopwatch();
        var elapsed = 0L;
        var hitCount = 0L;
        for (var i = 0; i < RepeatCount; i++)
        {
            GC.Collect(); // テスト前にメモリ状態の初期化を試行

            watcher.Restart();
            foreach (var key in scans) if (dic.ContainsKey(key)) hitCount++;
            watcher.Stop();
            elapsed += watcher.ElapsedMilliseconds;
        }
        var avgElapsed = Math.Ceiling((double)(elapsed / RepeatCount));
        var avgHitCount = Math.Ceiling((double)(hitCount / RepeatCount));
        Console.WriteLine(
            $"{prefix}({dic.Count}x{scans.Count}) -> elapsed={avgElapsed:#,0}[ms], hit={avgHitCount:#,0}");
    }

    /// <summary>
    /// ランダムなキーを生成する。
    /// </summary>
    /// <param name="keySize">作成するキーの長さ</param>
    /// <param name="count">作成するキーの数</param>
    /// <returns></returns>
    private List<string> CreateRandomKeyList(int keySize, long count)
    {
        var keyset = new HashSet<string>();
        var charbuf = new char[keySize];
        var random = new Random();
        for (var i = 0; i < count; )
        {
            // ランダムなキーを生成
            for(var j=0; j<keySize; j++)
                charbuf[j] = chars[random.Next(0, chars.Length)];
            var key = new string(charbuf);

            // 既存キーと重複する場合は再作成
            if (!keyset.Contains(key))
            {
                keyset.Add(key);
                i++;
            }
        }
        return keyset.ToList();
    }
}

実行結果

  • Contains性能比較(bucketSize: 100)
    List(100×100) -> elapsed=0[ms], hit=1
    HashSet(100×100) -> elapsed=0[ms], hit=1
    Dictionary(100×100) -> elapsed=0[ms], hit=1
  • Contains性能比較(bucketSize: 1000)
    List(1000×1000) -> elapsed=9[ms], hit=1
    HashSet(1000×1000) -> elapsed=0[ms], hit=1
    Dictionary(1000×1000) -> elapsed=0[ms], hit=1
  • Contains性能比較(bucketSize: 10000)
    List(10000×10000) -> elapsed=720[ms], hit=9
    HashSet(10000×10000) -> elapsed=0[ms], hit=9
    Dictionary(10000×10000) -> elapsed=0[ms], hit=9
  • Contains性能比較(bucketSize: 100000)
    List(100000×100000) -> elapsed=73,102[ms], hit=657
    HashSet(100000×100000) -> elapsed=7[ms], hit=657
    Dictionary(100000×100000) -> elapsed=7[ms], hit=657






-.NET Core, 1. システムエンジニアリング, 実装技術

関連記事

Red Hat Developer ProgramでのRHELの使用

概要 CentOSのサポート終了に伴い、Red Hatが提供する開発者プログラム(Red Hat Developer Program)に参加すれば、開発者でも本番でRHELを使用できるようになりました …

wildflyへのwarデプロイの自動化

更新したWebアプリをWildflyにデプロイするのが面倒なのでスクリプトを作成してみました。 前提 実行環境はCentOS Linux 7です。 JavaEEのWebアプリの配布形式であるwarファ …

Windows10で開発・検証用のプロキシサーバを構築

本番環境でプロキシを介して通信を行うアプリを開発したいが、開発環境ではプロキシがない… そんな時のためにローカルに検証用のプロキシサーバを構築してみます。 概要 Windows 10(64 …

.NET Core(C#): Moqを使ったモック作成方法

はじめに 次の環境を使用して動作確認しています。 OS Windows 10(64ビット) IDE Microsoft Visual Studio Community 2019(16.8.5) + C …

Excel VBAで独自形式のCSVファイルを作成

概要 ExcelはRFC4180に準拠したCSV出力が可能ですが、逆にRFC4180に準拠しない独自形式のCSV出力はできません。 そのため、ここではExcel VBAを使って独自のCSVファイルを出 …