質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.34%

  • アルゴリズム

    427questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

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

解決済

回答 5

投稿

  • 評価
  • クリップ 0
  • VIEW 750

nokuma3329

score 7

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

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

check解決した方法

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

「アルゴリズム」ではありませんが、DBに入れてしまうのが効率的かもしれません。

【第5回 位置情報を保存しよう(前編):位置情報サービスのはじめ方|gihyo.jp … 技術評論社】
http://gihyo.jp/dev/feature/01/location-based-services/0005

【MySQLのgeometry型で○km以内の場所を取得してみました - Qiita】
http://qiita.com/mitani/items/6909406ac4fe0db2d35c

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

二次元データ、というのがしっくりきませんが、データが整列されているならば二分探索できないことはないはずです。

問題なのは、「整列された状態を維持したままのデータ構造を作れるか」が肝心(二分探索の前提)です。一般的に、アルゴリズム設計はデータ構造を先に確定しておくことが定石です。

もちろん、「整列状態の維持」に拘ると、データの追加削除が容易にできなくなります。一般的に、データベースに対する「検索の容易さ」と「修正の容易さ」は両立できない性質があります。したがって、どのようにデータベースを設計すれば良いかはケースバイケースです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

例えば非常に広範囲の施設や店舗などのデータがを一つの塊として管理するようなものを考える必要があるとき、データ個数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側に特別な最適化動作があるのか、そのあたりには興味がわきました。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

同じタグがついた質問を見る

  • アルゴリズム

    427questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。