std::map最小限のデータで例を挙げます。
以下の2つのマップがあります。
map<string, Object*> map_ShortKey; // keys are single English words
map<string, Object*> map_LongKey; // keys are concatenated English words
map_ShortKeyには、プログラムの開始時に約 50 の要素が取り込まれ、全体を通して一定のままです。ただし、map_LongKeyプログラム全体で継続的に増加し、1000 ～ 10000 要素に達する可能性があります。
これらのマップ内の単語を検索したい場合、最良のアプローチは何ですか?
(1) 最初に で検索しmap_ShortKey、見つからない場合は で検索しm_LongKeyます。
(2) に追加map_ShortKeyしm_LongKeyて検索する
最悪の場合の複雑さを優先し、検索について何も知らない場合(たとえば、キーが別のマップよりも 1 つのマップで見つかる可能性が高い場合)、アプローチ 1 を使用します)。
のルックアップstd::mapは対数の最悪の場合の複雑さを持っているため、最初のケースでは、最悪の場合のlog(n) + log(m)ルックアップの複雑さになります (マップにnとm要素がそれぞれあると仮定します)。したがって、kルックアップにはコストがかかりますk * (log(n) + log(m))。
マップへの挿入も対数の複雑さがあるため、2 番目のケースではm、1 つのマップから別のマップへの挿入を強制し、次にm + n要素を含むマップでルックアップを行います。したがって、kルックアップの場合 (挿入を初めて行う場合)、m * log(n) + k * log(n + m)最悪の場合の複雑さが生じます。
したがって、最悪の場合の複雑さを気にする場合は、アプローチ 1) が次の場合に適しています。
k * (log(n) + log(m)) < m * log(n) + k * log(n + m)
kワークロードnと入力のサイズに基づいて見積もりm、計算を行って何が最適かを判断できます (そして、測定してこれを再確認します)。