2次元空間の項目をメモリにマッピングする

Question

2次元座標（符号付き近距離）で識別される項目の数があります。すべてのアイテムは、64KBのデータを含むクラスです。いつでも500〜1500程度のアイテムがあります。アイテムは、通常、1点を中心に〜20のグループです。私の質問は、あまりにも多くのメモリを取らないようにマップする必要があります。アイテムはゆっくりと追加/削除され（1秒あたり1〜10）、非常に頻繁にフェッチされるため、リストから要素を取り出す（より大きな構造へのポインタ）可能な限り速くする必要があります。私が思い付いた何

は、64×64のポインタの四角形を格納します言うことができますし、いくつかのgridContainerクラスがあるだろうということです。私は他のgridContainerを格納するメインのグリッドコンテナを持ち、このネストされたgridContainerはマップしたい実際のアイテムを格納します（これは4096x4096の実際のアイテムを許可します）。例えば[260,130]のような特定の項目にアクセスするには、それを64で割って商を取って親のgridContainer位置を見つけ、残りを入れ子のgridContainer位置を見つけます。ですから、[270,145]では[4,2]と[14,17]があります。

私はまた、STLのマップを使用して考えていたが、私はそれの内部を知らないと私はそれを期待すべきかパフォーマンスか分かりません。

私の方法上の任意の提案やそれを行うための任意のより良い方法はありますか？

あなたはいつもこれが log(n)時に検索して追加することが可能になる std::map<std::pair<short, short>, *item>を使用することができますが、より正確な答えを私たちはあなたが Quad Treeは、あなたが探しているもののようです

Answer 1

あなたがのstd ::マップとして既に提案し、ちょうどB木のコンテナで使用することができ、またはあなたがより速くなる可能性を秘めているハッシュテーブルを、使用することができます。クワッドツリーもオプションです。以前の2つのオプションよりもはるかに関与しますが、早期のオプションを提供します。最小の負荷で

ハッシュテーブルはO（1）ルックアップであることのチャンスを有するが、場合N =項目存在、Oの最悪のケース（n）を有しています。あなたが約10％以下の負荷を保つことができれば、O（1）よりも悪くなるためには本当に恐ろしいハッシュ関数が必要です。これは明らかに余分なメモリを大量に消費しますが、最速のオプションとなる可能性があります。ハッシュテーブルの比較型はかなり複雑です。キータイプ（この場合は一対のショート）の入力を受け付け、インデックスを返すハッシャー機能を持っています。そのインデックスは、オブジェクトの半固定配列上の位置に対応します。すでにオブジェクトがある場合は、衝突が解決されなければならないため、実行時間が悪くなる可能性があります。

クワッドツリーは、O（1）の最良のケース戻り時間を持ちますが、空のセルのみが存在しますが、アイテムが存在する場合、検索時間はO（log n）です.nは、所望のフィールド。オブジェクトが非常に少ない場合を除き、これはハッシュテーブルよりも多くのメモリを消費する可能性がありますが、上で述べたように、適切な実行時間が得られ、結果が得られない検索は相対速度で終了します。クワッドツリーの比較タイプは通常、カスケードブールチェックです。

std :: mapの定数参照時間はO（log n）です（nはマップ内の要素です）。これは最もメモリ効率の高いオプションですが、検索の実行時間が保証されています。 std :: mapの比較型はカスケーディングより小さい演算で、int（（short1 < < 16）| short2）の場合もかなり高速です。

使用する可能性が高い容器の概要があります。あなたが使用すべきものは、あなたのテーブルがどれだけ期待できるかによって決まります。いくつかのオブジェクト（< 500）で、おそらくstd :: mapが最良の賭けです。500〜5000の場合は、おそらくクワッドツリーを使用するべきです。それ以上のことがあれば、ツリーのメモリが不揃いになりますので、代わりにハッシュテーブルを使用してください。

Answer 2

ために。

Answer 3

高速である必要は何の操作を知っている必要があり