【C#】Containsの計算量

きっかけ

競プロでTLEして、BFSで探索済みのインデックスを保持していたListのContainsが原因っぽいので
そんなの常識だろって人は笑って見逃してください

使用したコード

program.cs

var rnd = new Random();

int dataCount = 5000000;
var list = new System.Collections.Generic.List<int>();
for (int i = 0; i < dataCount; i++)
{
    list.Add(rnd.Next(dataCount));
}
var hashSet = new System.Collections.Generic.HashSet<int>(list);

int testcaseCount = 100000;
var testcases = new int[testcaseCount];
for (int i = 0; i < testcaseCount; i++)
{
    testcases[i] = rnd.Next(dataCount);
}

// Stopwatchクラス生成
var sw = new System.Diagnostics.Stopwatch();

//-----------------
// 計測開始
sw.Start();

// ★処理A
for (int i = 0; i < testcaseCount; i++)
{
    list.Contains(testcases[i]);
}

// 計測停止
sw.Stop();

// 結果表示
Console.WriteLine("■処理Aにかかった時間");
TimeSpan ts = sw.Elapsed;
Console.WriteLine($"　{ts}");
Console.WriteLine($"　{ts.Hours}時間 {ts.Minutes}分 {ts.Seconds}秒 {ts.Milliseconds}ミリ秒");
Console.WriteLine($"　{sw.ElapsedMilliseconds}ミリ秒");

//-----------------
// 経過時間をリセットしてから計測開始
sw.Restart();

// ★処理B
for (int i = 0; i < testcaseCount; i++)
{
    hashSet.Contains(testcases[i]);
}

// 計測停止
sw.Stop();

// 結果表示
Console.WriteLine("■処理Bにかかった時間");
ts = sw.Elapsed;
Console.WriteLine($"　{ts}");
Console.WriteLine($"　{ts.Hours}時間 {ts.Minutes}分 {ts.Seconds}秒 {ts.Milliseconds}ミリ秒");
Console.WriteLine($"　{sw.ElapsedMilliseconds}ミリ秒");

結果

データ数	テストケース数	Listの実行時間[ms]	HashSetの実行時間[ms]
100	100000	2	1
1000	100000	13	1
10000	100000	115	1
100000	100000	554	1
1000000	100000	5459	6
10000000	100000	156770	7

　List<T>.Contains()は多分計算量がO(N)なので多くのデータがある状態で使うと相当重い処理になるようです。BFSやDFSで探索済みのインデックスを保持する用途ではHashSetが適切かと思います

参考

C#メモ　処理時間計測
https://qiita.com/Kosen-amai/items/81efaf815b48ab9ffbb6