kd-tree Visualization(3)

2009-04-28 kd-tree Visualization(3)

kd-tree Visualization(3)

さて、先日のエントリにて、メディアンを加味した2d木の構築を紹介しました。コードの見通しを簡潔にする目的もあり、メディアンの選択にはsort()を用いました。

#!/usr/bin/python -t

from operator import itemgetter
from random import seed, randint

def build(points, d=1):
    pts = list(points)

    if not pts:
        return None
    
    h = len(pts) // 2

    pts.sort(key=itemgetter(d))

    d = (d + 1) % 2

    return [build(pts[0:h],  d),
            build(pts[h+1:], d),
            pts[h]]

if __name__ == '__main__':
    seed(0)
    pts = [(randint(1, 100), randint(1, 100))
           for i in range(32)]

    tree = [None, build(pts), (0, 0)]

一般的にsort()を用いたメディアンの選択はコストが高いことで知られています。また、kd木は再帰的に木構造を構築するアルゴリズムです。そのため、均衡の取れた木構造を構築するためには、メディアンも再帰的に分割される領域の数とほぼ同じ回数分選択しなければなりません。これは、サンプルの数が増えれば増えるほど、sort()に費やすコストが高く付くことを意味します。

さて、少々メディアンから離れて、座標群の整列について考えてみましょう。座標群は予め整列していなければならないでしょうか? その必要はありません*1。検証も兼ねて、先日のエントリにて記載したコードを変更してみましょう。

from operator import itemgetter
from itertools import groupby

def median(iterable, key=None):
    if key is None:
        key = lambda x: x
    pool = tuple(iterable)
    h = len(pool) // 2
    return sorted(pool, key=key)[h]

def build(points, d=1):
    pts = tuple(points)

    if not pts:
        return None

    m = median(pts, key=itemgetter(d))

    dpts = { -1: [], 0: [], 1: [], }
    for k, g in groupby(pts, key=lambda x: (x[d] > m[d]) - (x[d] < m[d])):
        dpts[k].extend(g)

    h = len(dpts[0]) // 2

    d = (d + 1) % 2

    return [build(dpts[-1] + dpts[0][0:h],    d),
            build(dpts[ 1] + dpts[0][h+1:-1], d),
            dpts[0][h]]

今回のコードでは新たにmedian()関数を用意しました。median()関数はその名の通り、座標群から注目している軸をキーとしたメディアンを検索する関数です。

また、median()関数の呼び出し直後に行われている処理は、座標群の分割です。dptsは分割された座標群を保持するための辞書オブジェクトで、以下のように構成されます。

dpts[-1]: メディアンよりも小さな値を持つ座標群
dpts[ 0]: メディアンと同じ値を持つ座標群
dpts[ 1]: メディアンよりも大きな値を持つ座標群

分割にはメディアンと同様、注目している軸をキーとしていることに注意してください。また、メディアンと同じ値を持つ座標群を抽出することは冗長に思えるかもしれません。しかしながら、メディアンと同じ値を持つ座標が複数個存在する場合を考慮しています。

さて、median()関数では今sorted()関数(非破壊的なソート関数)を用いていますが、build()関数から掃き出すことが出来ました。念のためPostScriptにて可視してみます。

木構造としても可視化してみます。

先日のエントリと全く同じ結果を得ることが出来ました*2。このことからも、座標群は予め整列されていなくてもよいことが分かります。

残るはsort()を用いないメディアンの選択アルゴリズムを採択すればよいのですが、メディアンの選択はkd木とはまた別分野の大変難しい問題となります。また日を改めて考えてみたいと思います。

参考

アルゴリズムC〈第2巻〉探索・文字列・計算幾何

作者: R.セジウィック,Robert Sedgewick,野下浩平,佐藤創,星守,田口東
出版社/メーカー: 近代科学社
発売日: 1996/09
メディア: 単行本
購入: 5人クリック: 77回
この商品を含むブログ (10件) を見る

フォトンマッピング―実写に迫るコンピュータグラフィックス

作者: Henrik Wann Jensen,苗村健
出版社/メーカー: オーム社
発売日: 2002/07
メディア: 単行本
購入: 4人クリック: 46回
この商品を含むブログ (10件) を見る

追記

Selecting median using Quick Select Algorithm(1)としてメディアンの選択アルゴリズムを紹介しています。

Permalink | コメント(7) | トラックバック(2) | 01:27

*1：用途によっては必要があるようだ

*2：全く同じ結果だったので、先日のエントリと同じ画像を使用している

コメントを書く

you_got 2009/04/29 03:12 >メディアンの選択アルゴリズム
どんなものが出てくるのかわくわくします
うーーん　なんだろう

hiromi 2011/01/26 13:47 素晴らしい、ブログですね。どのように図を作っているのか教えて下さい。私のSFでCGを細々としています。

agw 2011/01/26 15:14 コメントありがとうございます。同業者さんなんですね。嬉しいです。

そのほとんどは、

1. PostScriptで記述(もしくはPython等で生成)し、
2. Preview.appでレンダリングを行い、
3. PNG等で出力

という段取りを取っています。

http://d.hatena.ne.jp/agw/20100321等ではCanvasエレメント(JavaScript)でレンダリングを行っていますが、比率で言えば圧倒的にPostScriptが多いですかねー。

hiromi 2011/01/26 16:26 I'd like know more details and hopefully I can do same things.
Is it possible to talk with you when you are available?

agw 2011/01/26 17:19 Thanks for you reply. I should have had to tell you that I'm heavy dependence on Macs, and Preview.app is the one of utilities that comes with it.

I have no problem with talking with you. How can I contact with you, anyways?

In addition, why don't you just start learning about PostScript? I would really recommend this document as good start point:

PostScript 基礎文法最速マスター:

http://d.hatena.ne.jp/dayflower/20100203/1265185183

hiromi 2011/01/26 21:01 I'm wondering if you can see my email address from your side or not.
I prefer python. I haven't seen postscript more than 20 years.
Preview.app is a key here then. I started using Mac recently.

agw 2011/01/26 22:21 Thanks for letting me know your contact. I'm not quite sure but your contact might not show to the public by some reason.

Unfortunately, I don't get your point about Python very much. What I mostly did with my visualizations is to generate codes written in PostScript with Python. Plus, Preview.app is not the key. Rasterizing can be also done by Ghostscript, however, I just feel that the result by Preview.app is more plausible than the one by Ghostscript.

Anyways, I'll shoot you a message very soon!

スパム対策のためのダミーです。もし見えても何も入力しないでください