【C#】ListとDictionaryでは検索速度に違いがある？

2024年2月9日

C#でのList<T>とDictionary<TKey, TValue>の検索速度には大きな差があります。これら二つのコレクション型は、内部的にデータを管理する方式が異なるため、検索性能に顕著な違いが生じます。

処理の違い

• List<T>: List<T>は配列ベースのコレクションで、要素に順番にアクセスするため、特定の要素を検索する場合、最悪の場合はリスト内のすべての要素を走査する必要があります。そのため、検索操作は平均してO(n)の時間複雑度を持ちます（nはリストの要素数）。
• Dictionary<TKey, TValue>: Dictionary<TKey, TValue>はハッシュテーブルに基づいており、キーによる高速な検索が可能です。ハッシュ関数を使用してキーから直接インデックスを計算し、そのインデックスに対応する値を迅速に取得できます。理想的な状況では、検索操作はO(1)の時間複雑度を持ちますが、ハッシュの衝突が多い場合は、この性能が低下する可能性があります。

要するに、少数の要素に対する単純な走査が必要な場合はList<T>が適しているかもしれませんが、大量のデータに対して高速な検索を行う必要がある場合はDictionary<TKey, TValue>がはるかに効率的です。

サンプル

以下に、C#でList<T>とDictionary<TKey, TValue>の検索速度の違いを確認する簡単なサンプルコードを示します。このサンプルでは、まず両方のコレクションに同じ数の要素を追加し、特定の要素を検索するのにかかる時間を計測します。

using System.Diagnostics;

var numberOfItems = 100_000_000;
var list = new List<int>();
var dictionary = new Dictionary<int, int>();
var random = new Random();
var stopwatch = new Stopwatch();

// リストとディクショナリーに要素を追加
for (int i = 0; i < numberOfItems; i++)
{
    list.Add(i);
    dictionary.Add(i, i);
}

var searchValue = random.Next(0, numberOfItems); // 検索する値

// Listの検索時間を計測
stopwatch.Start();
var foundInList = list.Contains(searchValue);
stopwatch.Stop();
Console.WriteLine($"Listにおける検索時間: {stopwatch.ElapsedMilliseconds} ms");

// Dictionaryの検索時間を計測
stopwatch.Restart();
var foundInDictionary = dictionary.ContainsKey(searchValue);
stopwatch.Stop();
Console.WriteLine($"Dictionaryにおける検索時間: {stopwatch.ElapsedMilliseconds} ms");

このコードでは、まずList<int>とDictionary<int, int>に10万個の整数を追加します。その後、ランダムに選ばれた値を両方のコレクションで検索し、それぞれの検索にかかった時間をミリ秒単位で出力します。

このサンプルでは、List<T>のContainsメソッドとDictionary<TKey, TValue>のContainsKeyメソッドを使用して検索を行っています。List<T>では全要素を走査する必要があるため、検索時間は要素数に比例して増加します。一方、Dictionary<TKey, TValue>はハッシュテーブルを使用しているため、検索時間はほとんど一定です。この違いにより、大量のデータに対する検索ではDictionary<TKey, TValue>の方がはるかに高速に動作することが確認できます。

実行結果について

このサンプルコードを実行した場合、List<T>の検索にはかなりの時間がかかることが予想されます。特に、検索する値がリストの後半にある場合やリストに含まれていない場合、検索時間はさらに長くなります。List<T>の検索時間はリストのサイズにほぼ比例するため、要素数が多いほど検索時間も長くなります。これは、リストの検索が線形検索（O(n)の時間複雑度）に基づいているためです。

一方で、Dictionary<TKey, TValue>の検索は非常に高速です。Dictionary<TKey, TValue>はハッシュテーブルを使用しており、平均的な場合、検索時間はほぼ一定（O(1)の時間複雑度）です。そのため、ディクショナリのサイズが大きくても、検索にかかる時間は大きく変わらないことが予想されます。

実際にこのコードを実行すると、List<T>での検索時間は数ミリ秒から数十ミリ秒（リストのサイズや検索する値の位置によって異なる）に及ぶ可能性があります。Dictionary<TKey, TValue>での検索時間はほとんどの場合、1ミリ秒未満で完了することが期待されます。

これらの結果は、大量のデータに対する高速な検索が必要な場合、Dictionary<TKey, TValue>がList<T>より適していることを示しています。

参考）Mac Book M1 Pro

ランダム値の場合

結果は一例です
Listでは途中でヒットする場合の時間になりますので、ばらつきます

var searchValue = random.Next(0, numberOfItems); // 検索する値

最終値の場合

Listでは最後までチェックする必要があります

var searchValue = 100_000_000 - 1;

100回繰り返してみる

using System.Diagnostics;

var numberOfItems = 100_000_000;
var list = new List<int>();
var dictionary = new Dictionary<int, int>();
var random = new Random();
var stopwatch = new Stopwatch();

// リストとディクショナリーに要素を追加
for (int i = 0; i < numberOfItems; i++)
{
    list.Add(i);
    dictionary.Add(i, i);
}

// var searchValue = random.Next(0, numberOfItems); // 検索する値
var searchValue = 100_000_000 - 1;

// Listの検索時間を計測
stopwatch.Start();
for (int i = 0; i < 100; i++)
{
    var foundInList = list.Contains(searchValue);
}
stopwatch.Stop();
Console.WriteLine($"Listにおける検索時間: {stopwatch.ElapsedMilliseconds} ms");

// Dictionaryの検索時間を計測
stopwatch.Restart();
for (int i = 0; i < 100; i++)
{
    var foundInDictionary = dictionary.ContainsKey(searchValue);
}
stopwatch.Stop();
Console.WriteLine($"Dictionaryにおける検索時間: {stopwatch.ElapsedMilliseconds} ms");

結果