Visualization(1)Algorithm前回のエントリに引き続き、連続したビット群の総数を求めるアルゴリズムを考える予定でしたが、今回は空間分割データ構造に関するエントリにしました。人力検索はてなに以下のような問題が提示されていたのがきっかけでした。人力検索はてな私もコメントにてid:pacticalschemeさんが挙げられていた「四分木」、「kd木」あたりを思い浮かべました。id:you_gotさんが例として掲載した座標群を与えた場合に、kd木がどのように構築されるかすぐに想像出来ませんでした。人力検索はてな実際のデータはもっと分散したものなのでしょうが、例に挙げられたこの座標群は極端に整列していますね。Cにも取り上げられています。日本語版では、第2巻、計算幾何の領域検索の章に掲載されています。Cから抜粋したkd木のコードです。書籍では解説と共に進行していくので、これらのコードを単純に組み上げても実際に動作するコードにはなりませんが、検証コードの元として十分なものです。今回は以下のコードを元にPythonで記述しています。Cで取られているアプローチに合わせてみることにします。コードが正しいかを確かめるために、以下のような座標群を用いました。Cに合わせ、x、y双方の要素を1より大きい整数値としました。61)]この頂点群は、Pythonで以下のように生成しました。range(32)]画像にすると、こんな座標群です。座標に振られている番号は、1から始まる座標群のインデックス値です。2d木を構築してみます。pt)結果をPostScriptで可視化してみます。先ほどと異なり座標に振られている番号は、kd木に挿入された順番を表しています。この場合は逐次座標を挿入しているため番号の並びは変わっていません。バランスが悪そうですね。このままではよく分からないので、木表現として可視化してみました。1番の接点の左右にぶら下がっている2番と9番の接点を比べると、2番により多くの接点がぶら下がっていますね。バランスの悪さを客観的に観測することが出来ました。N)と言われていますので、接点数が32個のこの木では5回になるはずです。この状態のkd木では、31番の座標を検索するのに9回計算しなければならなさそうですね。バランスの良いkd木を構築する一つのアイデアとして、座標群のメディアンで分割していく方法がありますが、それはまた次回以降のエントリで記載するとして、id:you_gotさんが挙げていた極端に整列している座標群を与えて2d木を構築してみました。1刻みの座標群では可視化した際に煩雑となるため、10刻みで座標群を生成します。101)]Pythonで上述の座標群を生成するには、以下のようにします。10)]可視化したものは、以下です。何やら大変なことになっていますね。木表現として可視化したものは以下です。いやはや、バランスが悪い。バランスの取れたkd木の場合、検索の計算量は7回ほどですが、この状態だと最悪21回の計算量となっています。次回はメディアンを加味したkd木の構築が如何ほどバランスを改善するかを可視化したいと思います。agwの日記として続編を記載しました。agwの日記にて、二分木の描画方法を考察しました。