トップ «前の日記(2012-07-18) 最新 次の日記(2012-07-24)» 編集

はじめてのにき

ここの位置付け

2004|11|
2005|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|07|08|09|10|11|12|
2020|01|02|03|04|05|06|07|08|09|10|11|12|
2021|01|02|03|04|05|06|07|08|09|10|11|12|
2022|01|02|03|04|05|06|07|08|09|10|11|12|
2023|01|02|03|04|05|06|07|08|09|10|11|12|
2024|01|02|03|

ToDo:


2012-07-22

_ 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)

お名前:
E-mail:
コメント:
人生、宇宙、すべての答え
本日のリンク元

2012年
7月
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
1.Gimite(2012-07-19 16:35) 2.mtve(2012-07-18 17:48) 3.lrlj(2012-07-03 23:34)
search / home / index

全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。

shinichiro.hamaji _at_ gmail.com / shinichiro.h