[最適化マニアクス]Dictionaryを使わずに高速な検索を実現できるテクニック

.netのDictionaryクラス便利ですよね。なんといってもO(1)で検索できる超高速性能が最高です

ところがDictionaryはシリアライズできないんですよね。どういうことかというと、UnityのScriptableObjectとかJsonUtitlityで扱える形式でファイルに保存できないんです。（方法はあるんですが、手軽ではないです。

ファイルに保存できないということは、マスターデータのような大量のデータをDictionaryで扱えないことになります。大量のデータの中からO(n)で検索するのは時間がかかります。そこで今回はDictionaryを使わずに高速な検索を実現できるテクニックについて書いていきます。

配列でO(1)検索
配列でO(logN)検索

配列でO(1)検索
配列でO(logN)検索

配列でO(1)検索

多くの場合マスターデータは連番で並んでいます。例えばアイテムのマスターデータを考えてみましょう。ID 1 から始まって連番で並んでいます。これはゲーム中では、配列で表現できます。そしてID 18のアイテムマスターを検索したければ

private MasterItem[] masterItems;// index 0 は空
public MasterItem Get(int id)
{
return masterItems[id];
}

このようにしてやれば、O(1)でアクセスすることができます。ポイントは、indexとIDを同値にすることです。index=ID-1の関係にすると、開発中に混乱して意図しないバグの温床になってしまいます。

配列でO(logN)検索

データによってはID自体に意味はなく、別のキーIDがあったりします。例えばシナリオのマスターデータを考えてみましょう。

メインシナリオ
ミッションシナリオ（クエスト、お使いイベントとか
サブシナリオ（町の人との会話

これらにID 1から始まる連番が割り当てられます。しかしメインシナリオやミッションシナリオやサブシナリオは開発するにつれどんどん増えていきます。連番で管理しているとメインとミッションとサブが混在し管理しづらくなります。

そこでよく使われるのが別のキーID、例えばScenarioID　としましょう。メインシナリオは10000始まり。ミッションシナリオは20000始まり。サブシナリオは30000始まりという具合です。

とびとびのIDになった場合は、先のindex=IDの手法が使えません。

しかしこのときIDがソートされていれば、二分探索アルゴリズムを使うことでO(logN)で検索することができます。要素数10000であってもだいたい14回程度のアクセスで検索できます。O(N)探索の1000倍程度早いですね。これはとても強力です。マスターデータは事前に作っておけるので、あらかじめソートしておけば実行時にすることはありません。