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

C#

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

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

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

  • 配列で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倍程度早いですね。これはとても強力です。マスターデータは事前に作っておけるので、あらかじめソートしておけば実行時にすることはありません。

【C#】 LowerBound, UpperBound (二分探索)
 私は時折、頭の体操代わりにプロコン問題を解いたりしているのだが、使う言語はその時々で変えてるので、関数によっては無いと不便に思うものがある。LowerBound, UpperBound はその代表例かな。ものによっては BinarySearch でも同じ結果を得られるものもあるが、やはりあった方が良いので改めて書いて...

.netには標準でSortedListというのもあります。ただしこちらはkeyが必要なので通常のListよりメモリ使用量が多くなります。

SortedList Class (System.Collections.Generic)
関連付けられた 実装に基づいて、キーにより並べ替えられた、キーと値のペアのコレクションを表します。Represents a collection of key/value pairs that are sorted by key based on the associated implementation.

コメント