kd-treeバランス時のソート

2009-10-22
#algorithm
kd-treeを作ったとき軸に沿ってのソートにクイックソートを使っていた。

だけど各レベルで完全にソートする必要はなくて、中央とする個数の左と右で値の大小関係が成り立ってればいい。 「フォトンマッピング」本ではちょっと凝ったやりかたをしている：

#define  swap(ph, a, b) { Photon *ph2=ph[a]; ph[a]=ph[b]; ph[b]=ph2; }

void median_split(Photon** p, int start, int end, int median, int axis) {
  int left = start;
  int right = end;

  while (right > left) {
    const float v = p[right]->pos[axis];
    int i = left-1;
    int j = right;
    for (;;) {
      while (p[++i]->pos[axis] < v);
      while (p[--j]->pos[axis] > v && j>left);
      if (i >= j) break;
      swap(p, i, j);
    }

    swap(p, i, right);
    if (i >= median)  right = i-1;
    if (i <= median)  left = i+1;
  }
}

どう動作するのかパッと見わからないんだけど、クイックソートが２重再帰するところをmedianを含むほうだけをループするようにしてるぽい（参考：クイックソートのソース）。 適当に見積もったところ、全体のソートでのスワップ回数は n.log2(n) 程度になるっぽい。

ではと思って速度を比較したところ、クイックソートを使った場合とほとんど差がなかった、おかしいな？ 上のやり方だとソートの基準値を右端に取っているのとループでの判定が多いからかも知れず。 あと大方ソート済みのデータに弱いのかも知れず。qsortと同じようにちょっと書き換え：

while (right > left) {
  const float v = p[(left+right)/2]->pos[axis];
  int i = left-1;
  int j = right+1;
  for (;;) {
    while (p[++i]->pos[axis] < v);
    while (p[--j]->pos[axis] > v);
    if (i >= j) break;
    swap(p, i, j);
  }

  if (i >= median)  right = i-1;
  if (i <= median)  left = i+1;
}

このように変更したところ、1000万個のフォトンのソートにクイックソートを使った場合 1分40秒かかったところが 28秒271 と3.5倍高速になった。まあ劇的ではないけど、多少は速いようだ。

codepadで試す

http://www.kmonos.net/wlog/103.html#_0111091111 のnth_elementと同じ要領でいけると思うんだけど、具体的にどうやるのかわかってない。

下のように変更するとちゃんとソートできない模様。ダメじゃん。

関連記事

新着記事