C# 配列・リスト・ハッシュ生成・挿入・参照の速度比較

C#のイメージ。

C# の Array(配列)、List、Dictionary、でインスタンスの生成にかかる時間、要素の挿入にかかる時間、参照にかかる時間をそれぞれ比較しました。 実行環境は C#, .NETFramework4.5, VisualStudio 2013 Community です。

比較に用いるコード

比較に用いたコードを簡単に並べます。完全なコードは記事の末尾を参照してください。

インスタンスの生成

ここでは要素数 10,000 の各コレクションを、10,000 回用意することにします。

for (int i = 0; i < times; i++)
{
    int[] array = new int[length];
}

for (int i = 0; i < times; i++)
{
    List<int> list = new List<int>(length);
}

for (int i = 0; i < times; i++)
{
    Dictionary<int, int> dictionary = new Dictionary<int, int>(length);
}

要素の挿入

配列のみ要素の挿入はできないので、結果は -1 を返すようにしておきます。 各コレクションの要素数が 10,000 になるまで挿入を繰り返します。

List<int> list = new List<int>(length);

for (int i = 0; i < length; i++)
{
    list.Add(i);
}

Dictionary<int, int> dictionary = new Dictionary<int, int>(length);

for (int i = 0; i < length; i++)
{
    dictionary.Add(i, i);
}

要素の参照

コレクションの持つ 10,000 の要素をすべて参照する前の時間を計測します。

for (int i = 0; i < times; i++)
{
    tempValue = array[i];
}

for (int i = 0; i < times; i++)
{
    tempValue = list[i];
}

stopWatch.Restart();

for (int i = 0; i < times; i++)
{
    tempValue = dictionary[i];
}

実行結果

VisualStudio の機能「コードの最適化」を有効化し、デバッグモードは切って実行しています。 実測値に関しては実行環境に依存するかと思いますが、相対的な速度には影響は出ないでしょう。

非常に単純な検証なので実用的な場面で有効な数値とは言い難いですが、次のようになりました。 当然ですが、概ね高機能なほど遅くなります。

インスタンスの生成
Array0.007 msec
List19.066 msec
Dictionary135.170 msec
要素の挿入
Array-1.000 msec
List0.034 msec
Dictionary0.152 msec
要素の参照
Array0.006 msec
List0.020 msec
Dictionary0.149 msec

挿入と参照に関してはミリ秒以内に収まっているわけですし、当たり前ですが実装は目的に沿った機能かどうかで選択するべきです。

ただし、インスタンスの生成に関しては大きく開きがあるので、高速にインスタンスを生成する必要があるときは、実装方法を考える必要があります。

完全なコード

private static readonly Stopwatch stopWatch = new Stopwatch();

static void Main(string[] args)
{
    GenerateNewInstance(10000, 10000);
    InsertElements(10000, 10000);
    ReferEachElements(10000, 10000);
    Console.ReadLine();
}

/// <summary>
/// 新しいインスタンスの生成にかかる時間を比較します。
/// </summary>
/// <param name="times">
/// 試行回数。
/// </param>
/// <param name="length">
/// コレクションの長さ。
/// </param>
private static void GenerateNewInstance(int times, int length)
{
    double[] result = new double[3];

    // =================================================
    // Array
    // =================================================

    stopWatch.Restart();

    for (int i = 0; i < times; i++)
    {
        int[] array = new int[length];
    }

    stopWatch.Stop();

    result[0] = (double)stopWatch.ElapsedTicks / (double)Stopwatch.Frequency * 1000d;

    // =================================================
    // List
    // =================================================

    stopWatch.Restart();

    for (int i = 0; i < times; i++)
    {
        List<int> list = new List<int>(length);
    }

    stopWatch.Stop();

    result[1] = (double)stopWatch.ElapsedTicks / (double)Stopwatch.Frequency * 1000d;

    // =================================================
    // Dictionary
    // =================================================

    stopWatch.Restart();

    for (int i = 0; i < times; i++)
    {
        Dictionary<int, int> dictionary = new Dictionary<int, int>(length);
    }

    stopWatch.Stop();

    result[2] = (double)stopWatch.ElapsedTicks / (double)Stopwatch.Frequency * 1000d;

    OutputResult("GenerateNewInstance(times : " + times + ", capacity : " + length + ")",
                 "msec",
                 result);
}

/// <summary>
/// 要素の挿入にかかる時間を比較します。
/// 配列は -1 を返します。
/// </summary>
/// <param name="times">
/// 試行回数。
/// </param>
/// <param name="length">
/// コレクションの長さ。
/// </param>
private static void InsertElements(int times, int length)
{
    double[] result = new double[3];

    // =================================================
    // Array
    // =================================================

    result[0] = -1;

    // =================================================
    // List
    // =================================================

    List<int> list = new List<int>(length);

    stopWatch.Restart();

    for (int i = 0; i < length; i++)
    {
        list.Add(i);
    }

    stopWatch.Stop();

    result[1] = (double)stopWatch.ElapsedTicks / (double)Stopwatch.Frequency * 1000d;

    // =================================================
    // Dictionary
    // =================================================

    Dictionary<int, int> dictionary = new Dictionary<int, int>(length);

    stopWatch.Restart();

    for (int i = 0; i < length; i++)
    {
        dictionary.Add(i, i);
    }

    stopWatch.Stop();

    result[2] = (double)stopWatch.ElapsedTicks / (double)Stopwatch.Frequency * 1000d;

    OutputResult("InsertElements(times : " + times + ", capacity : " + length + ")",
                 "msec",
                 result);
}

/// <summary>
/// 要素の参照にかかる時間を比較します。
/// </summary>
/// <param name="times">
/// 試行回数。
/// </param>
/// <param name="length">
/// 各コレクションの長さ。
/// </param>
private static void ReferEachElements(int times, int length)
{
    double[] result = new double[3];
    int tempValue = 0;

    // =================================================
    // Array
    // =================================================

    int[] array = new int[length];

    for (int i = 0; i < length; i++)
    {
        array[i] = i;
    }

    stopWatch.Restart();

    for (int i = 0; i < times; i++)
    {
        tempValue = array[i];
    }

    stopWatch.Stop();

    result[0] = (double)stopWatch.ElapsedTicks / (double)Stopwatch.Frequency * 1000d;

    // =================================================
    // List
    // =================================================

    List<int> list = new List<int>(length);

    for (int i = 0; i < length; i++)
    {
        list.Add(i);
    }

    stopWatch.Restart();

    for (int i = 0; i < times; i++)
    {
        tempValue = list[i];
    }

    stopWatch.Stop();

    result[1] = (double)stopWatch.ElapsedTicks / (double)Stopwatch.Frequency * 1000d;

    // =================================================
    // Dictionary
    // =================================================

    Dictionary<int, int> dictionary = new Dictionary<int, int>(length);

    for (int i = 0; i < length; i++)
    {
        dictionary.Add(i, i);
    }

    stopWatch.Restart();

    for (int i = 0; i < times; i++)
    {
        tempValue = dictionary[i];
    }

    stopWatch.Stop();

    result[2] = (double)stopWatch.ElapsedTicks / (double)Stopwatch.Frequency * 1000d;

    OutputResult("ReferEachElements(times : " + times + ", capacity : " + length + ")",
                 "msec",
                 result);
}

/// <summary>
/// 比較実験の実行結果を出力します。
/// </summary>
/// <param name="title">
/// 比較実験のタイトル。
/// </param>
/// <param name="unit">
/// 比較実験の単位。
/// </param>
/// <param name="result">
/// 比較実験の結果。
/// </param>
private static void OutputResult(string title, string unit, double[] result)
{
    Console.WriteLine("= " + title);
    Console.WriteLine();
    Console.WriteLine("!| Array      |> {0:f3} " + unit, result[0]);
    Console.WriteLine("!| List       |> {0:f3} " + unit, result[1]);
    Console.WriteLine("!| Dictionary |> {0:f3} " + unit, result[2]);
    Console.WriteLine();
}