C# Dictionary のループのパフォーマンス

商品コードと値段 のレコードに対し、値段の合計を求めるコードを考えてみたいと思います。

Dictionary 対 List

Dictionary がハッシュテーブルなのに対し、List は順序配列なので、
今回の処理では当然 Listの方が速いと思われます。

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
    public static void Main()
    {
        // テストデータ作成
        var dic = new Dictionary();
        var list = new List<KeyValuePair>();
        for (int i = 0; i < 10000000; i++)
        {
            dic.Add(i, i % 7);
            list.Add(new KeyValuePair(i, i % 7));
        }

        var sw = new System.Diagnostics.Stopwatch();

        sw.Start();
        int total = 0;
        foreach (var key in dic.Keys)
        {
            total += dic[key];
        }
        sw.Stop();
        Console.WriteLine("Dictionary: {0}ms", sw.ElapsedMilliseconds);

        sw.Restart();
        total = 0;
        foreach (var item in list)
        {
            total += item.Value;
        }
        sw.Stop();
        Console.WriteLine("List: {0}ms", sw.ElapsedMilliseconds);
    }
}

実行結果:

Dictionary: 214ms  
List: 88ms

予想通りです。

より速く

Dictionary のループの仕方を変えてやることで、速度改善が図れることがあります。

sw.Restart();
total = 0;
foreach (var item in dic)
{
    total += item.Value;
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);

実行結果:

156ms

Dictionary.Keys ではなく、Dictionary のアイテムそのものを回してやることで、
3割近く改善することができました。

さらに、Valuesそのものを回してやると、

sw.Restart();
total = 0;
foreach (var v in dic.Values)
{
    total += v;
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);

実行結果:

63ms

誤差の範囲かも知れませんが、List より速くなりました。

他の方法

せっかくなので、他の方法も試してみます。

sw.Restart();
total = dic.Sum(r => r.Value);
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);

実行結果:

235ms

Dictionary.Keys のループとあまり変わりませんが、意味はわかりやすいし、
シンプルだし、速度を求めないのであれば個人的には好みです。

無理やりですが配列っぽくアクセスする方法も試してみます。

sw.Restart();
total = 0;
for (int i = 0; i < dic.Count; i++)
{
    total += dic.ElementAt(i).Value;
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);

ただし、この方法は非常に遅いです。
私のPCではテストデータを 1/1000 の個数に変更してようやく、327ms でした。

まとめ(私見)

  • Keyを使ったアクセスが重要でないなら List を使うべき。
  • Dictionary をループさせるなら、Keys ではなく Dictionaryのアイテムで回す。
  • 速度重視でないなら、Linq がわかりやすい。
  • ElementAt() はループの中では使わない。

おすすめ

TOP
TOP