【えぬ】〜Theme of えぬ〜 にまつわるはてダ

■libcでqsort()を再帰を使って実装してる香具師は怠慢だろ…常識的に考えて

タイトルは釣り。でもこの件は納得のいく答えがほしかったり。

はじめに

大学の頃アルゴリズムに関する教科書に書かれていたクイックソートの実装の過程に感動した記憶がある。

分割統治法によってソートを進めていくクイックソートを実装するにあたり、最初の実装では関数を再帰で呼び出していく、まあ最初はそれを思いつくよなという展開だったわけだが、次にアルゴリズムの特徴から、「実は再帰を使わなくてもいい」ことが解説され、非再帰に置き換えた実装も提示されていた。

そのとき「libcのqsort()はどんな実装になっているんだろう？」と興味を持ち、LinuxのglibcとFreeBSDのlibcを調べたことがあった。

あれから5年以上たって、そのときの結果を忘れてしまっていたので、改めて調べてみた。

再帰を使っていない実装

• glibc
  • http://sourceware.org/cgi-bin/cvsweb.cgi/libc/stdlib/qsort.c?cvsroot=glibc
  • http://sourceware.org/cgi-bin/cvsweb.cgi/~checkout~/libc/stdlib/qsort.c?rev=1.1&content-type=text/plain&cvsroot=glibc
    (最初のバージョン、91年の時点で非再帰)
• Ruby
  • http://svn.ruby-lang.org/repos/ruby/trunk/util.c
• あと、glibc由来のコード使ってるソフトウェア多数

再帰を使っている実装

• BSD系
  • http://www.jp.freebsd.org/cgi/cvsweb.cgi/src/lib/libc/stdlib/qsort.c
  • http://www.jp.freebsd.org/cgi/cvsweb.cgi/~checkout~/src/lib/libc/stdlib/qsort.c?rev=1.13&content-type=text/plain
  • http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/stdlib/qsort.c
  • http://cvsweb.netbsd.org/bsdweb.cgi/~checkout~/src/lib/libc/stdlib/qsort.c?rev=1.14&content-type=text/plain
  • http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/qsort.c
  • http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/qsort.c?rev=1.10&content-type=text/x-cvsweb-markup
  • いずれも/* Iterate rather than recurse to save stack space */というコメントを含むのが特徴
• Solaris
  • http://cvs.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/lib/libbc/libc/gen/common/qsort.c
• Perl
  • http://public.activestate.com/cgi-bin/perlbrowse?filename=pp_sort.c&show_file=Show+Plain+File

その他

• 再帰処理のクイックソート vs 非再帰処理のクイックソート :: Drk7jpによると、再帰で実装されているPerlのsort()は、PurePerlで実装しなおした非再帰ソートよりも遅い(！！)
• コメント中にSedgewickの名前を出しているコードは大体が非再帰
  • http://www.google.com/codesearch?q=qsort+sedgewick&hl=en&btnG=Search+Code
• 例外もあり
  • http://www.google.com/codesearch?hl=en&q=+qsort+sedgewick+show:SSSliTwaHfU:md0RsifFrNE:0aWbTUcMafI&sa=N&cd=8&ct=rc&cs_p=svn://svn.debian.org/svn/pkg-games/packages/trunk&cs_f=squirrel/squirrel/sqbaselib.cpp#a0