C# ArrayとDictionaryの速度比較

いくつかの数値に対して何かをカウントしていくような形式の時には手癖でDictionaryを使っていたのですが、それで痛い目に遭ったので反省としてかかる時間を調査。

AtCoderの問題が調査のきっかけです。問題はこちら。解法そのままなので気になる方は解いてからどうぞ。

 ・やること
10⁷までのArray/Dictionaryを作り、1から10⁷までそれぞれについてその数の10⁷までの倍数のカウントを1増やしていく

具体的には以下の通り。

・Array

//①Arrayの作成
sw.Start();
var array = new int[N + 1];
sw.Stop();
Console.WriteLine(sw.Elapsed);

//②カウントの加算
sw.Start();
for (var i = 1; i <= N; i++)
{
    for (var j = i; j <= N; j += i)
    {
        array[j] += 1;
    }
}
sw.Stop();
Console.WriteLine(sw.Elapsed);

・Dictionary

//①Dictionaryの作成
sw.Start();
var dict = new Dictionary<int, int>();
for (var i = 1; i <= N; i++)
{
    dict.Add(i, 0);
}
sw.Stop();
Console.WriteLine(sw.Elapsed);

//②カウントの加算
sw.Restart();
for (var i = 1; i <= N; i++)
{
    for (var j = i; j <= N; j += i)
    {
        dict[j] += 1;
    }
}
sw.Stop();
Console.WriteLine(sw.Elapsed);

結果は以下。単位は秒です。

Array	①作成	②加算
1回目	00.0003549	01.6939147
2回目	00.0003953	01.7070274

Dictionary	①作成	②加算
1回目	00.3353714	17.2990964
2回目	00.3310036	17.2898917

DictionaryはArrayの約10倍かかるんですね。10⁶までなら実用的な時間(2ms)内に終わるんですが、10⁷になると厳しいと。 1~Nまで網羅的に使うことがわかっている場合は極力Arrayを使うよう気を付けます。