c++ - 2 次元空間のアイテムをメモリにマッピングする

Question

2次元座標（符号付き短距離）で識別されるアイテムの数があります。すべてのアイテムは、64KB のデータを含むクラスです。常時500～1500点ほどの商品がございます。アイテムは通常、ポイントの周りに ~ 20 のグループになっています。私の質問は、メモリをあまり消費しないようにどのようにマップすればよいかということです。アイテムはゆっくりと追加/削除され (1 秒あたり 1 ～ 10)、非常に頻繁にフェッチされるため、リストからの要素 (より大きな構造へのポインター) のフェッチはできるだけ高速にする必要があります。

私が思いついたのは、いくつかの gridContainer クラスがあり、64x64 ポインターの四角形を格納するとしましょう。他の gridContainer を格納するメイン グリッド コンテナーがあり、このネストされた gridContainer は、マップする実際のアイテムを格納します (これにより、4096x4096 の実際のアイテムが許可されます)。[260, 130] などの特定のアイテムにアクセスするには、それを 64 で割り、商をとって親 gridContainer の位置を見つけ、余りをとってネストされた gridContainer の位置を見つけます。したがって、[270,145] の場合、[4,2] と [14,17] になります。

私も使おうと思っていたのstd::mapですが、中身がわからず、どんな性能が期待できるのかもわかりません。

私の方法に関する提案、またはそれを行うためのより良い方法はありますか?

Answer 1

すでに提案されているように、単に ab ツリー コンテナーである std::map を使用することも、より高速になる可能性があるハッシュ テーブルを使用することもできます。クアッド ツリーもオプションの 1 つです。これは、前の 2 つのオプションよりもはるかに複雑になりますが、初期のオプションを提供します。

負荷が最小のハッシュ テーブルでは、O(1) ルックアップの可能性が高くなりますが、n = アイテムが存在する場合、最悪の場合は O(n) になります。負荷を約 10% 未満に抑えることができる場合、O(1) よりも悪化するには、本当に恐ろしいハッシュ関数が必要になります。これは明らかに多くの余分なメモリを消費しますが、最速のオプションになる可能性があります。ハッシュ テーブルの比較型はかなり複雑です。キー タイプ (この場合は short のペア) の入力を受け取り、インデックスを返すハッシュ関数があります。そのインデックスは、オブジェクトの半固定配列上の位置に対応します。そこに既にオブジェクトが存在する場合、衝突を解決する必要があり、実行時間が長くなる可能性があるため、疎であるほど良いです。

クアッド ツリーの最良の場合のリターン時間は 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

いつでもstd::map<std::pair<short, short>, *item>これを使用して、時間内に取得および追加できますlog(n)が、より正確な答えを得るには、高速にするために必要な操作を知る必要があります

Answer 3

クワッド ツリーは、あなたが探しているもののようです。