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秒以上かかるので注意!)。

[ymuto109]

あとで処理

[yujiorama]

20次元くらいからは blute force のほうが早くなるって algorithm in nutshell で書かれてたけど試してない

[nyamadandan]

K-D木のJavaScipt実装．WebGLでゲームが作られるようになったら使われるようになるかもしれないアルゴリズムの一つ．

[ototoi]

すばらしい対応の早さ。さすが。構築が遅い理由は再帰を下る際、配列をコピーしているため。これはjavascriptではソート範囲限定ができないためサブ配列を作成してることによる。

[you_got]

さすが 対応が早いですね 脱帽