はじめてのにき

_ A Killer Adversary for Quicksort

http://www.cs.dartmouth.edu/~doug/mdmspe.pdf

via http://research.swtch.com/qsort

「quicksort の最悪計算量は O(n^2) ですよ、でも pivot のとりかたとかでだいたい大丈夫にすることはできますよ」、ってのはよく言われる話だけど、実際 quicksort が n^2 になるようなデータを作る方法を考えてみた、っていう話。

作りかたがちょっと面白くて、 qsort を実際に呼んで、 callback で呼ばれる比較関数で小さい数字から少しずつデータを確定させていく、みたいな。

このコード、 mac とか linux で実行してみると n^2 にならない。 russ cox によると glibc の qsort は実際は merge sort らしいからそういうもんらしい。 mac もそういう感じなのかな。 N が小さい時はわりと n^2 ぽい挙動してるけど…

ぱっとコード見た感じ、 2*(log(N)-1) 回越えて再帰する時は heapsort する、みたいなコードに見えるかな。まーなんとなくわからんでもないし、あとまぁそれならそういう挙動するかな的な。

自分で適当に qsort 書いてみて antiqsort に渡してみたら、モロに O(n^2) になった。おもしろい。 qsort は C だとっていうか余計なメモリ使わない実装は結構むずかしいと思ってて、昔書いた時はすっと書けなかった気がするけど、今回はそんなに苦労しなかった。全然テストしてないからあってるかは知らんけど。

void myqsort(void* base, size_t nel, size_t width,
             int (*compar)(const void*, const void*)) {
  char* pivot = (char*)base;
  char* b = pivot + width;
  char* e = (char*)base + nel * width;
  char* buf = (char*)malloc(width);
  size_t lc = 0;
  while (b < e) {
    int r = compar(pivot, b);
    if (r >= 0) {
      b += width;
      lc++;
    } else {
      e -= width;
      memcpy(buf, b, width);
      memcpy(b, e, width);
      memcpy(e, buf, width);
    }
  }
  if (lc) {
    memcpy(buf, b - width, width);
    memcpy(b - width, pivot, width);
    memcpy(pivot, buf, width);
    myqsort(pivot, lc, width, compar);
  }
  free(buf);
  if (nel - 1 - lc)
    myqsort(b, nel - 1 - lc, width, compar);
}

(16:59)

_ fortress

https://blogs.oracle.com/projectfortress/entry/fortress_wrapping_up

おわったのか…

(23:18)