[最適化マニアクス]知らないとはまるDictionaryの問題

Dictionary便利ですよね。特に検索がO(1)で超高速なのが気に入ってます。

しかし世の中そんな甘くはありません。なにかしらのペナルティがあるのが世の常です。そこで今回は、O(1)アクセスを実現するかわりに、どういうデメリットがあるのか調べてみました。

メモリ使用量が多い
Listに比べアクセスが遅い
Enumをキーにすると遅い、boxingでgc allocが発生する
コードサイズが肥大化しやすい
シリアライズできない

メモリ使用量が多い

【C#】Dictionaryの実装・データ構造・アルゴリズムを考える。 | 創造的プログラミングと粘土細工

JUGEMテーマ：コンピュータ【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。上記の投稿で、System.Collections.Generic.Dictionaryの内部の状態を観察す

O(1)検索は魔法ではありません。上記のようなハッシュテーブルを追加で持っています。その分メモリ消費量がListに比べかなり多いです。

Unity2018.2.19f IL2CPP .net4.6 win standloneで測定してみました。単位KB

要素数	List<int>	Dictionary<int,int>
1000	4	21.8
10000	39.1	197.6
100000	390.7	424.4

Listは 4byte×要素数 +ヘッダとシンプルですね。Dictionaryは要素数100000だけおかしな値になりました。しかし要素数100000は使うことがないので無視してもよいでしょう。要素数1000、10000に限定してみれば、Listの約5倍です！メモリ消費量に神経質にならなければいけないモバイルゲームでは気をつける必要があります。

Listに比べアクセスが遅い

どうしてもhashcodeを計算する必要があるためListに比較して遅くなってしまいます。stringのhashcodeとなればさらに遅いでしょう。

ただし、これが露骨にボトルネックになることは現実のプロジェクトではあまりないです。

アセットバンドル名でのアクセスが一番考えられますが、高頻度でアクセスすることがないかぎり問題ないでしょ

Enumをキーにすると遅い、boxingでgc allocが発生する

測定してみると誤差程度です。特に.net4.6では高速化されているため気にしなくてよさそうです。

一方boxingによるgc allocの方は深刻です。アクセスするたびにgc allocが発生します。

回避策は

IEqualityComparerを実装したクラスを用意して、Dictionaryのコンストラクタに設定する
intにキャストして使う

あたりでしょうか。他には、

public enum Week
{
    Mon,
    Tue,
    Wed,
    Tur,
    Fri,
    Sat,
    Sun,
}
private string[] weekStr =
{
    "月","火","水","木","金","土","日"
};
public string GetWeekStr(Week week)
{
    return weekStr[(int)week];
}

このように、enumの配列に対応した要素配列をもつという方法もあります。気をつけるべき点として、enumに変更があった場合対応する配列もちゃんと更新しないと値がずれたり、配列範囲外アクセスになったりします。