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

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

1 要約
2 詳細
- 2.1 サンプルコード
- 2.2 実行結果

要約

測定条件は次の通りです。
- コレクションから文字列キーを検索する際の処理時間を計測する。
- 対象のコレクションは、List, HaseSet, Dictionary(キーのみ)とする。
- ランダムな文字列キーをN個格納したコレクションから、ランダムな文字列キーをN回検索する。
  (合計の照合回数は N × N = N²回)
- 動作確認のため少なくても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回検索する場合の照合回数を「N²」と表記しています。
※計測時間の単位はミリ秒であり、[ms]と表記しています。
※計測時間が1 [ms]未満の場合は0 [ms]と表記しています。
種類照合回数
100² 1,000² 10,000² 100,000²
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]
考察
- 比較回数(コレクションに含まれるデータ件数 × 検索回数)が少ない場合は差がありませんが、1,000²近辺からListの検索時間が他と比べて大きくなっていきます。
- リファレンスを見ると、Listの計算量はO(n)、HashSet/Dictionaryの計算量はO(1)となっています。これらを使ってN回の検索を行う場合、Listの計算量はO(n²)、HashSet/Dictionaryの計算量はO(n)になるためだと思われます。
- 比較回数が少ない場面ではListでも問題ありませんが、比較回数が多くなる可能性がある場合はHashSet/Dictionaryを使用した方が安全です。
- 個人的には、処理が多数繰り返される処理で、5個以上の条件を持つif文や5個以上の値を持つリストはHashSetかDictionaryに置き換えるようにしています。

ハードウェア	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)

種類
List	9 [ms]	720 [ms]	73,102 [ms]
HashSet	0 [ms]	0 [ms]	7 [ms]
Dictionary	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 );  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(); }}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

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

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

種類	照合回数
種類	100²	1,000²	10,000²	100,000²
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]