algorithm - 最近点検索をkd-treeで : 404 Blog Not Found2009年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秒以上かかるので注意!)。
