高速、低負荷で検索するにはどうしたらいいでしょうか？
条件は次の通りです
１．集合Pはあらかじめ、任意の順番でソートしておける
２．点ｐの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わる
ターゲットの言語はjavascriptで、200msぐらいの間隔で検索を続けるつもりです
集合P の個数が 1000 ~ 10000 点くらいだったらどうしますか？
みなさんのアイディアを貸してください
No.1
1823
246
40pt
０：確認すると、距離はユークリッド距離、つまりSQRT（x*x+y*y)であり、
margin*2 を直径とする円内にあって一番近い、ですね。
１：ソートを第1順位x、第2順位yでしておけば、まずx,yの値を見て、
範囲を点pから、±margin, すなわち、margin*2を一編とする
正方形内の点に限られます。これが最初のデータ量削減。
この範囲にPの点がなければ、近似点はない。あれば２へ。
２：次に、±(margin/2)の範囲の点の存在を確認します。
あればその中に限定。なければ、±(margin*3/4)の
範囲に広げてみる。なければ、±(margin*3/4)～±margin
にはあります。
３．２で点があれば、±(margin/4)で見て、なければ
±(margin/4)～±(margin/2)にあります。
４．点数が高々1万点なら、その範囲でユークリッド距離を
順に求めていってもよいと思います。
No.2
79184
40pt
こういうのはどうでしょう。
集合ｐの座標値の小数点（任意の点pの座標も含めて）が例えば最大下三桁だとする。
集合ｐのX座標を１０００倍した集合Aをつくる。
集合ｐのY座標を１０００倍した集合Bをつくる。
AもBも整数で昇順ソート済みとする。
任意の点p（x,y）を各1000倍したものを（X,Y）とする。
Marginをm、1000倍したのをMとする。
集合Aから、X-M<=A<=X+Mとなる要素を抜き出す。AAとする（例えば３個とする）
同様に集合Bから、Y-M<=B<=Y+Mとなる要素を抜き出す。BBとする（例えば３個とする）
AAの要素とBBの要素の直積（３×３で９個）をとり、各1000で割るとそれは集合ｐのX、Y座標となる。
これは任意の点pと集合ｐの要素の距離ではなく、X座標のMarginとY座標のMarginが独立にmとした場合に要件を満足するようと思いますが、どうなのでしょうか。
直積というと、ベクトルの計算にでてくるやつでしょうか。
なんとなくイメージがつかめたような気がしますが、
具体的にどうプログラムしようか考えるとわかりません＞＜
でも、ありがとうございました
GoldenDawn
2009/04/17 12:57:38
2
1
1
1
17
16
you_got
practicalscheme
確認事項はそのとおりです
１．のアルゴリズムで悩んでいます
(1,1), (1,2), .... (1, 100)
(2,1), (2,2), .... (2, 100)
(3,1), (3,2), .... (3, 100)
(4,1), (4,2), .... (4, 100)
(5,1), (5,2), .... (5, 100)
このうち、(3,50) に関して margin = 1 で調べるとすると
(2, 49), (2, 50), (2, 51)
(3, 49), (3, 50), (3, 51)
(4, 49), (4, 50), (4, 51)
を範囲にしたいわけです
しかし、この正方形だけを範囲にするにはどうやったらいいのでしょう？
> ソートを第1順位x、第2順位yでしておけば
となると
(1,1), (1,2), (1,3) ... (1,100), (2,1), (2,2),.....(5,100)
という順列になります
(2,49) から (4,51) の範囲を指定すると
(2,49) ... (2,100), (3,1), (3,2), .... (3,100), (4,1), (4,2), ... (4,51)
が検索範囲になります
(2,52) .. (3,48), (3,52) .. (4,48) が無駄な検索範囲となってしまいます
sibazyun さんのおっしゃるように、正方形の領域を検索対象とするには
どのようなデータの持ち方をしたらよいでしょう。。