【C#】【Unity】DictionaryとListの速度比較

• はじめに
• サンプルデータ
• 計測1. 格納したデータをそのまま取り出す
• 計測2. 指定したKeyに合致するデータを取り出す
• 計測3. 指定したKeyに合致するデータを取り出す(Listは要素番号指定)
• 計測4. Valueを検索する
• 計測5. Keyをstringにしてみる
• 計測6. KeyをCustom classにしてみる
• 計測7. KeyをCustom classにしてみる(ListでGetHashCodeGetHashCode -> Equalsの順に検索)
• おわりに
• 参照

はじめに

ここ最近 Unity 2017 Game Optimization を読んでいるのですが、
その中の一つに格納したデータを検索したりするなら List を使うより Dictionary を使うと良いよ、というものがありました。

これはどんな検索の仕方でも早くなるの？など気になったので調べてみました。

サンプルデータ

Dictionary は Key と Value を1対で持ちます。

List でも同じようにデータを対で持たせるため、下記のようなクラスを使うことにします。

SampleValue.cs

public class SampleValue {
    public int Id { get; set; }
    public string Category { get; set; }
}

で、データは下記のようにセットします(検証内容によって途中で変えますが)。

DictionarySample.cs

using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Profiling;
using UnityEngine.UI;
using Debug = UnityEngine.Debug;

public class DictionarySample: MonoBehaviour {
    public Button ListButton;
    public Button DictionaryButton;        
    private List< SampleValue> sampleList;
    private Dictionary< int, string> sampleDictionary;
        
    private void Start() {
        sampleList = new List< SampleValue>();
        sampleDictionary = new Dictionary< int, string>();

        var categoryNum = 0;
        for (var i = 0; i < 100000; i++) {
            var newValue = new SampleValue {
                Id = i,
                Category = "Category" + categoryNum
            };
            sampleList.Add(newValue);
            sampleDictionary.Add(i, "Category" + categoryNum);

            categoryNum++;
            if (categoryNum > 5) {
                categoryNum = 0;
            }
        }
        ListButton.onClick.AddListener(() => {
            Profiler.BeginSample("SamplingProfile");
           
            // 検証用の処理呼び出し.
            OutputListValues();
                
            Profiler.EndSample();
        });
        DictionaryButton.onClick.AddListener(() => {
            Profiler.BeginSample("SamplingProfile");

            // 検証用の処理呼び出し.
            OutputDictionaryValues()

            Profiler.EndSample();
        });
    }        
}

計測1. 格納したデータをそのまま取り出す

まずは格納したデータを、検索などせずにそのまま取り出してみます。

DictionarySample.cs

～省略～
private void OutputListValues() {
    foreach (var s in sampleList) {
        result = s.Category;
    }
}
private void OutputDictionaryValues() {
    foreach (var s in sampleDictionary) {
        result = s.Value;
    }
}
～省略～

List の方が良い結果となりました。

計測2. 指定したKeyに合致するデータを取り出す

Key (List では Id) の値が合致するデータを取り出してみます。
今回 Id と List の要素番号が同じであるためあまり意味がない部分もありますが、そこは気にしない方向で。

なお Dictionary と List の速度比較の話を検索すると、この方法で検証していることが多いです。

DictionarySample.cs

～省略～
private void OutputListValues() {
    var result = "";
    for (var i = 0; i < sampleList.Count; i++) {
        if (sampleList[i].Id == i) {
            result = sampleList[i].Category;
        }
    }
}
private void OutputDictionaryValues() {
    var result = "";
    for (var i = 0; i < sampleDictionary.Count; i++) {
        result = sampleDictionary[i];
    }
}
～省略～

う～ん？一回目は List の方が速い、という結果になりました(誤差の範囲内かもですが)。

計測3. 指定したKeyに合致するデータを取り出す(Listは要素番号指定)

今回 List が持つ Id と、要素番号は全く同じです。

このようなデータの場合に、 List の要素番号を指定してデータを取り出すのと Dictionary で Key (Id, 要素番号と同じ) を指定してデータを取り出すのとではどちらが速いでしょうか。

DictionarySample.cs

～省略～
private void OutputListValues() {
    for (var i = 0; i < sampleList.Count; i++) {
        result = sampleList[i].Category;
    }
}

// Dictionaryは上記と同じ.

～省略～

そもそも List での Id 比較の速度による影響が少なかったようで、
あまり変わりませんでした。

計測4. Valueを検索する

では、 Dictionary の Key ではなく Value から要素を取得する場合はどうでしょうか。

「Category0」という値を持った要素を取得してみることにします。

DictionarySample.cs

～省略～
private void OutputListValues() {
    var result = "";
    foreach (var category in sampleList.Where(c => c.Category == "Category0")) {
        result = category.Category;
    }
}

private void OutputDictionaryValues() {
    var result = "";
    foreach (var category in sampleDictionary.Where(c => c.Value == "Category0")) {
        result = category.Value;
    }
}
～省略～

GC Alloc は List の方が少なく、 速度は Dictionary の方が速い、という結果になりました。

計測5. Keyをstringにしてみる

今のところ List で良くね？て結果ばかりが出て悲しいので、
もう少し Dictionary の得意分野とされる、 Key によるアクセスをもう少し見てみることにします。

まずは今まで int にしていた Key の型を string にしてみます。

SampleValue.cs

public class SampleValue {
    public string Id { get; set; }
    public string Category { get; set; }
}

DictionarySample.cs

～省略～
private List< SampleValue> sampleList;
private Dictionary< string, string> sampleDictionary;
    
private void Start() {
    sampleList = new List< SampleValue>();
    sampleDictionary = new Dictionary< string, string>();

    var categoryNum = 0;
    for (var i = 0; i < 100000; i++) {
        var newValue = new SampleValue {
            Id = "Category" + i,
            Category = "Category" + categoryNum
        };
        sampleList.Add(newValue);
        sampleDictionary.Add("Category" + i, "Category" + categoryNum);
        categoryNum++;
        if (categoryNum > 5) {
            categoryNum = 0;
        }
    }
    ListButton.onClick.AddListener(() => {
        Profiler.BeginSample("SamplingProfile");
        OutputListValues();
        
        Profiler.EndSample();
    });
    DictionaryButton.onClick.AddListener(() => {
        Profiler.BeginSample("SamplingProfile");

        OutputDictionaryValues();
        
        Profiler.EndSample();
    });
}
private void OutputListValues() {
    var result = "";
    for (var i = 0; i < sampleList.Count; i++) {
        if (sampleList[i].Id == "Category10") {
            result = sampleList[i].Category;
        }
    }
}
private void OutputDictionaryValues() {
    var result = "";
    result = sampleDictionary["Category10"];
}

で、結果はこちら。

Dictionary の本領発揮、という感じですね。
(ただ、一回目の直前にスパイクが見られるのが気になりますが)

やはりループしなくても値が取れる、というのは大きい。

計測6. KeyをCustom classにしてみる

次は Key として Custom class を指定してみます。

List でも Value として string の値を持てるよう、下記のクラスを値として持たせるようにします。

SampleValueForList.cs

public class SampleValueForList {
    public SampleValue Key { get; set; }
    public string Value { get; set; }
}

DictionarySample.cs

～省略～
private List< SampleValueForList> sampleList;
private Dictionary< SampleValue, string> sampleDictionary;

private void Start() {
    sampleList = new List< SampleValueForList>();
    sampleDictionary = new Dictionary< SampleValue, string>();

    var categoryNum = 0;
    for (var i = 0; i < 100000; i++) {
        var newValue = new SampleValue(i, "Category" + categoryNum);
        sampleList.Add(new SampleValueForList {
            Key = newValue,
            Value = "Category" + categoryNum
        });
        sampleDictionary.Add(newValue, "Category" + categoryNum);
            
        categoryNum++;
        if (categoryNum > 5) {
            categoryNum = 0;
        }
    }
    ListButton.onClick.AddListener(() => {
        Profiler.BeginSample("SamplingProfile");
        OutputListValues();
        
        Profiler.EndSample();
    });
    DictionaryButton.onClick.AddListener(() => {
        Profiler.BeginSample("SamplingProfile");

        OutputDictionaryValues();
        
        Profiler.EndSample();
    });
}
private void OutputListValues() {
    var result = "";
    var key = new SampleValue(0, "Category0");
    for (var i = 0; i < sampleList.Count; i++) {
        if (sampleList[i].Key.Equals(key)) {
            result = sampleList[i].Value;
            Debug.Log("result " + result);
        }
    }
}
private void OutputDictionaryValues() {
    var result = "";
    var key = new SampleValue(0, "Category0");
    if (sampleDictionary.TryGetValue(key, out result)) {
        Debug.Log("result " + result);
    }
}

ただしそのままだと Dictionary 、 List ともに結果は 0 件になります。

Dictionary で指定した Key が存在するかを確認するのは FindEntry というメソッドですが、
この中でも登場する GetHashCode 、 Equals を override して Key として渡された SampleValue と比較できるようにする必要があります。

Dictionary

～省略～
private int FindEntry(TKey key) {
    if ((object) key == null)
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    if (this.buckets != null) {
        int num = this.comparer.GetHashCode(key) & int.MaxValue;
        for (int index = this.buckets[num % this.buckets.Length]; index >= 0; index = this.entries[index].next) {
            if (this.entries[index].hashCode == num && this.comparer.Equals(this.entries[index].key, key))
                return index;
        }
    }
    return -1;
}
～省略～

SampleValue.cs

public class SampleValue {
    public int Id { get; private set; }
    public string Category { get; private set; }

    public SampleValue(int newId, string newCateogry) {
        Id = newId;
        Category = newCateogry;
    }
    
    public override int GetHashCode() {
        return Id;
    }
    public override bool Equals(object obj) {
        return Equals(obj as SampleValue);
    }
    public bool Equals(SampleValue obj) {
        return obj != null && obj.Id == this.Id && obj.Category == this.Category;
    }
    
}

Log 出力してみるとわかりますが、 Dictionary を検索するとき GetHashCode で HashCode の値を比較 -> 同じ場合は Equals で比較、
という順番で比較が行われます。
(※実行時間の問題から、要素数は減らしてから確認した方が良いと思います)

また、 Dictionary に値を追加するときにも上記の方法で既存の値を確認していることがわかります。

GetHashCode で得られる値は、すべて異なるものである必要はありません。

ただし、異なる値に同じ HashCode 値が設定されてしまうと、 Equals で確認する量が増え、遅くなります。

試しにすべて 0 を設定してみたところ、 Dictionary に値を追加するところで固まってしまい、
時間の計測ができませんでした。

ということで適切な値を設定する必要があります。

計測7. KeyをCustom classにしてみる(ListでGetHashCode -> Equalsの順に検索)

List でも Dictionary で Key を探すように、 GetHashCode -> Equals の順に検索すると同じように速くなるでしょうか。

DictionarySample.cs

～省略～
private void OutputListValues() {
    var result = "";
    var key = new SampleValue(0, "Category0");
    for (var i = 0; i < sampleList.Count; i++) {
        if (sampleList[i].Key.GetHashCode() == key.GetHashCode() &&
            sampleList[i].Key.Equals(key)) {
            result = sampleList[i].Value;
            Debug.Log("result " + result);
        }
    }
}

// Dictionaryは上記と同じ.

～省略～

Dictionary には及ばないものの、速くなりましたね。

おわりに

今回の結果を元に考えると、Key を指定することができ、かつ期待する検索結果が少ない場合は Dictionary を使うことで高速化が望めそうです。
反対に検索結果が多い、また色んな条件で検索したい場合は List の方が強い、またはあまり変わらない、ということになりそうです。

また今回言及はしませんでしたが、 Dictionary では List や配列のように順序を持たないため、
要素番号で指定したい、また格納されたデータを決まった順番で扱いたい場合は List を使う必要があります。

SortedDictionary という自動で要素が並び替えられるものもありますが、
パフォーマンス面では Dictionary に劣り、かつ要素番号での指定はできません。

Unity 2017 Game Optimization でも指摘されていますが、
それぞれの特性を活かして効果的に使い分けていきたいところです。

参照

Dictionary

• Unity 2017 Game Optimization
• Dictionary<TKey, TValue> Class - msdn.aspx)
• Programming C# 5.0
• c# Dictionary with class as Key - Stack Overflow* C# Dictionary Versus List Lookup Time - Net-informations.com

GetHashCode

• ジェネリックコレクション その2 Dictionary (System.Collections.Generic) - Programming/.NET Framework/コレクション - 総武ソフトウェア推進所
• ジェネリックコレクション その3 SortedListとSortedDictionary (System.Collections.Generic) - Programming/.NET Framework/コレクション - 総武ソフトウェア推進所
• Object.GetHashCode メソッド (System) - msdn.aspx)
• [Effective C#] 項目10 GetHashCode() の罠に注意すること - まさくらのブログ