[B! algorithm][kd-tree] yukimori_726のブックマーク

yukimori_726 id:yukimori_726

algorithmとkd-treeに関するyukimori_726のブックマーク (2)

kd-tree Visualization(1) - agwの日記
前回のエントリに引き続き、連続したビット群の総数を求めるアルゴリズムを考える予定でしたが、今回は空間分割データ構造に関するエントリにしました。人力検索はてなに以下のような問題が提示されていたのがきっかけでした。二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています高速、低負荷で検索するにはどうしたらいいでしょうか？条件は次の通りです１．集合Pはあらかじめ、任意の順番でソートしておける２．点ｐの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わるターゲットの言語はjavascriptで、200msぐらいの間隔で検索を続けるつもりです集合P の個数が 1000 ~ 10000 点くらいだったらどうしますか？二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索する… - 人力検索
yukimori_726 2009/05/24
algorithm

kd-tree

programming

virtualization
リンク
algorithm - 最近点検索をkd-treeで : 404 Blog Not Found
2009年04月30日01:00 カテゴリMathLightweight Languages algorithm - 最近点検索をkd-treeでというわけで、kd-treeによる検索も実装してみました。はてなブックマーク - ototoiのブックマークデータ数が少ない場合、この全検索が高速。ただデータが多くなってくるとkd-treeがいいと思う。点ならば配列をソートするだけで実現できる。以下のデモでは、単にkd-treeによる検索だけではなく、kd-tree構築の速度と、総当たりの場合の速度の比較もできるようにしてあります。10,000点ぐらいだと、その差を顕著に感じることが出来るでしょう。100,000点ぐらいあると、感動的なほど差が出ます。それだけあってもkd-treeの方はほぼ1ms以内に検索が終わるのですから(ただしこの場合、デモの実行に合計10秒以上かかるので注意!)。
yukimori_726 2009/04/30
algorithm

javascript

programming

kd-tree
リンク
1