2次元データの効率的な探索方法について

現在地のデータと、住所のデータから最寄りの場所を求める、というプログラムを書いています。
ただ、そこで気になったのが、二次元データには二分探索的な手法はないのか?
ということです。

現状最寄り候補が300点ほどしかないため、全探索でもそこまで時間がかかっているわけではないのですが、
今後に備え、2次元データを効率的に探索する方法を教えていただければと思います。

行動規範の内容に同意します

回答5件

自己解決

「kd木」というのが良さそうでした。
探してみたら各言語ライブラリもあります。
https://github.com/gurgeous/kdtree
ありがとうございました!!

投稿2017/03/25 01:32

nokuma3329

総合スコア15

例えば非常に広範囲の施設や店舗などのデータがを一つの塊として管理するようなものを考える必要があるとき、データ個数Nが全探索可能な程度なら質問者さんが現在やっておられる線形探索で問題ないと思います。家庭用のPCを前提にしたとして1000個でも1000x1000個でも探索自体にかかる計算が複雑でないため現実的な計算時間で求められそうな気がします。

例えばJavaで3.8GHz 2coreの64bit Windows10上でやっても1000x1000個の探索は0.02秒程度のオーダーでした。(1M個の位置情報のみを10MB前後のメモリーを使い全て一度にメモリーにロード済みという素朴すぎる前提ですが)

単に机上での思考として、線形探索が問題となるぐらいのデータ数(例えば一つ一つのデータが位置情報だけでなくもろもろの情報を持つため一度にメモリー上にロードできないといった理由も含めて)をどう探索するかを考えると、foomoさんが指摘されているように一次元のデータとしてソートしておくことはできないでしょうから空間的にソートしておくことが考えられると思います。

各枝は一定範囲の経度・緯度の範囲内のデータをぶら下げることにして下位になるほど小さな範囲とするわけですね。あるデータD0との近傍の点を求めるには、D0が属する最下層の枝B0内にぶら下がっているデータのみ探索し、一番近い点Diを求め、D0-Di間の距離rを半径とする円がB0の範囲におさまれば探索はそれで終わりですし、おさまらなければB0の隣の枝の中のデータも探索範囲にする・・・といった感じかと思います。

しかしメモリーにおさまりきらないようなデータならDBを使うでしょうから自前でアルゴリズムを考えるよりkei344さんのコメントにあるようなgeometry型を使ったDB検索というのが実際的な解になりそうな気がしました。

ただDB素人なのでわからなかったのですが、DB探索時に結局線形探索されることになるのか、それともGeometry型を使った探索でDB側に特別な最適化動作があるのか、そのあたりには興味がわきました。

投稿2017/03/25 02:13

KSwordOfHaste

総合スコア18394

最寄りの場所を、現在地からの距離が最短の箇所だと理解すると、
現在地が決まってからでないと、それぞれの候補地からの距離を算出できないため、
距離でソートされたリストを作成することができません。

二分探索は、事前にソートされたリストが存在することが前提ですので、
二次元データであるかどうかに関係なく、二分探索を使用することはできません。

ただし、実現したいことから考えると、必要なのは、単に最短距離を持つ場所を特定したい、
ということでしょうから、一箇所づつ距離を計算し、現時点での最短距離を与える箇所と比較して
より短い方を現時点での最短距離を与える個所として選定する。を繰り返すのが、
特定の条件がない場合の最適なロジックになります。
（全件探索と書かれているのが、おそらくこれと同等のことを指していると思います。）

投稿2017/03/24 17:05