2

テキストの壁については前もって申し訳ありません-私がプログラミングを行ってからしばらく経ちましたが、おそらく私が言いたいことにはもっと良い用語があります. 考えられるすべてを検索しましたが、サイトで関連する質問は見つかりませんでしたが、より良い条件で見つけることができたので、どんな助けも大歓迎です!

設定されたタクシー/マンハッタン距離以下で区切られたオブジェクトのグループを見つける際のパフォーマンスを改善しようとしています。 つまり、私の距離が「x」で、点「a」は点「b」から x 単位、点「b」は点「c」から x 単位、点「c」は点「a」から x+3 単位であるとします。 ; a、b、および c をグループとして識別し、それらのいずれかの x 単位内にある任意のオブジェクトを識別する必要があります (など)。

これらのグループを見つけるためのいくつかの単純なアルゴリズムを特定しましたが、パフォーマンスが向上する可能性があると思います。ここではクラスタリング アルゴリズムが関連しているように見えますが、問題に正確に適合するアルゴリズムを見つけることができませんでした。また、データをできるだけ効果的に保存しているかどうかもわかりません。今のところ、静的データを扱っているだけなので、開始する前に必要な形式にコピーできます。ただし、将来的には、ポイントの追加と削除を効率的に処理できる実装が必要です。詳細は次のとおりです。

  • オブジェクトの 2 つの順序付けられていない ArrayLists から始めます。これらの多くのプロパティには、整数座標 (x、y、z) の一意のトリプレットがあります。
  • オブジェクトは非常に大きなボリューム (たとえば、5 億立方単位) にまばらに散らばっており、設定距離は比較的小さい (<15 単位)
  • サイズ 1 のグループを見つける必要がないため、多くの「ノイズ」があります。私のデータでは、3 つ以上のグループは非常にまれです。
  • 90% 以上の時間で近くのオブジェクトが同じタイミングで ArrayLists に追加されるため、可能であればその事実を利用したいと考えています。
  • もう 1 つの有用な事実は、1 つの次元 (y) の範囲が他の 2 つの約 1/10 であるため、必要に応じて 2 次元のグループを後で分割して、2 次元のアルゴリズムを開始する方が高速な方法である可能性があります。
  • これらのグループを見つけたら、関数呼び出しのためにグループ内の各オブジェクトにアクセスする必要があるため、座標だけでなくオブジェクトを識別する必要があります。

オフセット グリッドを使用して ArrayLists を 2 回ループし、作成したグループを再分析するだけのパフォーマンスを改善するにはどうすればよいですか? 私の言語は Java ですが、アルゴリズムは特定の型やライブラリよりも重要です (ただし、それらも取り上げます!)。

4

1 に答える 1

1

Range searchの特殊なケースを実装しようとしていると思います。おそらく、データをkd ツリーに保存すると便利です。少なくとも、検索しているポイントの 1 つを囲むハイパー キューブ内にあるポイントを簡単に抽出できるはずです。次に、それらの距離が要件に一致するかどうかを確認できます。

いくつかの解決策については、「 Fixed-Radius Near Neighbors and Geometric Basics 」も参照してください。

于 2013-01-27T23:19:48.273 に答える