1

緯度、経度、およびタイム ゾーンのトリプレットの非常に長い半ソート リストがあります。このリストをすばやく検索して、特定の緯度と経度に最も近いタイム ゾーンを見つけられるようにしたいので、このリストを KD ツリーにしたいと考えています。

最初にファイル全体をある種のデータ構造に読み込む必要があると考えています(どのデータ構造ですか?おそらくArrayList<Triplet<Double, Double, String>>?)。次に、その構造の中央値要素を取得してルートにし、左と右のリストを残します。次に、各リストの中央値要素を取得し、それを左または右の子として追加し続けます。

これを最初に試みたときは、時間がかかり、効率が悪いように思えました... しかし、私はそれが間違っていたように感じます。私がやろうとしていることのアルゴリズムまたは疑似コードを教えてもらえますか?

4

1 に答える 1

2

それが役立つ場合は、XYZPoint と呼ばれる内部クラスで XYZ を double として取り込むKD-Tree を Javaで作成しています。XYZ ポイントをタイム ゾーン データで拡張し、経度に X、緯度に Y、Z にゼロを使用できます。これは、少なくとも開始点になる可能性があります。

次に、ポイントに最も近いタイム ゾーンに対して、既に実装されている最近傍 (ユークリッド距離) メソッドを使用できます。

また、.. KD ツリーを作成するために、ウィキペダはHeapSort (リンクされた私の Java 実装)を使用し、中央値を繰り返し削除することを提案しています。

于 2012-10-01T01:08:58.087 に答える