4

QuadTree のバッキング構造として HashMap を使用することを検討しています。モートン シーケンスを使用して、関心のある領域の各正方形を一意に識別できると思います。私の QuadTree の高さは最大で 16 であることはわかっています。私の計算では、65,536 x 65,536 のマトリックスになり、最大で 4,294,967,296 個のセルが得られるはずです。HashMap の要素が多すぎるかどうかは誰にもわかりませんか? Tree を使用して常に QuadTree を作成できましたが、HashMap を使用するとパフォーマンスが向上すると考えました。

高さ 1 == (2x2) == 4 のモートン シーケンス

高さ 2 のモートン シーケンス == (4x4) == 16

高さ 3 のモートン シーケンス == (8x8) == 64

最大高さ 3 の木の Morton Sequencing の例。

ここに画像の説明を入力

これが私が知っていることです：

  • 既知の長方形の領域で緯度/経度でデータを取得します。
  • データはエリア全体を完全にカバーするわけではなく、そのエリアのどこかでチャンクに統合される可能性があります。(さらに悪いケースは、4,294,967,296 セルすべてのデータです)
  • データの解像度は、領域を 65k x 65k の長方形に分割することになります。
  • また、データの挿入/更新のために 10 対 1 のクエリが発生する可能性が高いこともわかっています。
4

5 に答える 5

2

ハッシュマップは良い考えではありません。ナビゲーション システムで使用されるより良い解決策があります。

各 Quadtree セルに文字を割り当てます: A (左、上)、B (右、上)、C、および D。

これで、文字列を介して各クワッド セルにアドレス指定できます。

ABACE: これは、レベル 5 のセルを識別します。(A->B->A->C->E) その特定の Quadtree コーディングの詳細については、インターネットを検索してください。

忘れないでください: サブ分割ルール (セルをより小さいセルに分割するタイミング) を決定し、取得するセルの数を決定します。あなたが与える数は、はるかに高いです。これは、Google マップのクワッド ツリーで 1:1 を思い出させる理論的な計算にすぎません。

さらに、アプリケーションに必要な Quadtree のタイプを知ることも重要です。

ポイント クワッドツリー、リージョン クワッドツリー (バウンディング ボックス)、ライン クワッドツリー。

Java での既存の Quadtree 実装を知っている場合。コメントを投稿するか、この回答を編集してください。

さらに、すべてのソリューションに 1 つを実装することはできません。
サポートする要素の数をおおよそ知る必要があります。予想される最大値と等しくない理論上の最大値は、適切なアプローチではありません。

それをメイン メモリに格納するか、ディスクに格納するかを決定する必要があるため、これも四分木の構造に影響することを知っておく必要があります。「ABCD」ソリューションは、ディスクからの動的ロードに適しています。

Google のアプローチでは画像を四分木に格納します。これは格納したいポイントとは異なるため、計算が現実的であるとは思えません。

世界中のすべての国のすべての通りを保存したい場合は、ポイントの数がわかっているため、その数を見積もることができます (OpenStreetMap、TomTom (Teelatlas)、または (Nokia Maps) Navteq.

四分木をディスクに保存する必要があることに気付いた場合は、おそらくサイズが開いており、ディスク容量によってのみ制限されています。

于 2013-01-17T16:52:49.890 に答える
1

Quad Treeを Tree として実装すると、より良い結果が得られると思います。HashMap にこのような大きなデータベースを実際に実装するのは、とにかく悪い考えです。衝突が多いと、HashMap のパフォーマンスが大幅に低下するためです。

どうやら、あなたは自分が持っているデータの量を正確に知っています。その場合、HashMap は完全に冗長です。HashMap は、データの量がわからない場合に使用します。しかし、この場合、ツリーのすべてのノードに 4 つの要素があることがわかります。それでは、なぜ HashMap をわざわざ使用するのでしょうか。

また、あなたのテーブルは明らかに少なくとも 4GB の大きさです。ほとんどのシステムでは、それはあなたの記憶にかろうじて収まります。また、Java VM のオーバーヘッドもあるのに、なぜこれをメモリに格納するのでしょうか。ディスク上で適切に機能するデータ構造を見つける方がよいでしょう。空間データのそのようなデータ構造の 1 つ (クアッド ツリーを使用しているため、あなたが持っていると思います) はR-Treeです。

于 2013-01-17T15:44:36.293 に答える
1

おっと、ここで一度に多くの概念を取得しています。まず第一に、あなたは何を達成しようとしていますか？四分木を保存し​​ますか? 細胞のマトリックス？ハッシュルックアップ？

四分木が必要な場合、なぜハッシュ マップを使用するのでしょうか。各ノードに最大 4 つの子ノードが存在する可能性があることがわかっています。ハッシュ マップは、クイック ルックアップが必要な任意の数のキーと値のマッピングに役立ちます。4 つしかない場合、ハッシュは重要ではないかもしれません。また、マップをネストできますが、少し扱いに​​くいです。何らかのデータ構造を使用するか、独自のデータ構造を作成する方がよいでしょう。

また、四分木で何を達成しようとしていますか? マトリックス内のセルをすばやく検索しますか? そこでは、いくつかの座標マッピング関数がより役立つ場合があります。

最後に、ハッシュ マップ内のノードの量についてはそれほど心配していません。65536² セルは、セルあたり 1 バイトであっても、最終的に 4 GiB のメモリになります。

「このデータでの私の目標は何ですか」という質問に戻って、それに適合するように管理しながら、どのデータ構造がそれに役立つかを見つけるのが最善だと思います（ルックアップなどの要件を念頭に置いてください）。記憶に。

于 2013-01-17T15:44:44.343 に答える
0

スペースと速度の両方の理由から、直接リンクされたノードを必ず使用してください。

データがこれだけ大きいので、Java は完全に避けたいと思います。あなたは常にガベージコレクターに翻弄されます。より金属に近い言語を選びましょう: C または C++、Pascal/Delphi、Ada など。

4 つの子ポインターを配列に入れて、リーフを 2 ビット インデックスのパックされた配列として参照できるようにします (Ada を使用する良い理由です。Ada を使用すると、まったくいじらずにそのようなものを定義できます)。これがモートンシーケンシングだと思います。私はその用語を知りませんでした。

子にインデックスを付けるこの方法自体が、Java を避ける理由です。ノード クラス インスタンスに子配列を含めると、ポインターと配列サイズ フィールドが必要になります。他の言語では必要ないノードあたり 8 または 16 バイトです。40億個の細胞があるので、それはたくさんあります。

実際には、計算を行う必要があります。暗黙的なリーフ セルを使用する場合でも、表現するノードは 10 億あります。それらを参照するために 32 ビット インデックスを使用する場合 (64 ビット ポインタの代わりにメモリを節約するため)、ノードあたりの最小値は 16 バイトです。ノード属性はわずか 4 バイトだとします。次に、Java のオーバーヘッドがなくても、完全なツリーだけで 20 ギガバイトを使用できます。

RAM には十分な予算を確保することをお勧めします。

于 2013-01-18T02:21:32.187 に答える