Entry

新人プログラマとウィザードの差とか都市伝説とか

2009年03月22日

こちらの話から。うーん……微妙だ。

というのも、本来プログラムと言うのは「極力、ループを使ってはならない」ものだと思うからです。
(詳細な説明は省きますが、これはクイックソートとバブルソートの実行速度の差を考えれば明らかで、アセンブラの時代から速度を追求するプログラマは単純ループよりも美しいアルゴリズムで高速化を行ってきました。今はCPUが高速化されているので、そんなことお構いなしに強引にループでぶん回す人も沢山いるようですが、新人プログラマとウィザードの差はここで出ると思います)

mod_perlは本当に速いのか? : PHPスクリプト無料配布所 :: PHP.TO

こういうところから都市伝説が生まれるんだろうけれども,クイックソートとバブルソートはループの有無で速さが違うわけではなくて,数学的なオーダーがそれぞれ O(n log2(n)) と O(n2) な算法だからだったりするんだよな……。つか,アルゴリズムっつのは,そもそもループとか再帰とかいった実装に依存した概念ではない。一般的にクイックソートは実装のしやすさから再帰を使って実装することが多いけれども,再帰を使うことが予定されている算法というわけではありません。再帰を使ったクイックソートには,平均して log2(n) のスタック空間が必要なわけで,スタックサイズに心配がある場合は(組み込みとか),ループを使う場合もあります。また,FORTRAN のような言語では,サブルーチンごとに自動変数を作ることができないから再帰構造を取れなかったりもする。それでもクイックソートは,工夫して行われています。

じゃ,ループと再帰だと再帰の方が速いかというと,必ずしもそういうわけでもない。

関数の再帰呼び出し(recursive function call)というのは,ある関数の中で,その関数自身を呼ぶことなんですけれど,もともとこの関数呼び出しっつのは,非常に高価なインストラクションだったりします。関数を呼ぶときは,引数をスタック上に push して,戻りのアドレスも push して,やっとこさ call できる(stdcall の場合)。スタックに push するっつのは,メモリアクセスですから,普通ノロいんですね。一方,制御を受け取った関数は,push されている引数をレジスタに pop して,戻りのアドレスをメモっといて,しかもその前に呼び元の関数が使っていたレジスタ値を壊さないように,一時退避(push)しておいて……といった具合に,いろいろな準備をして,初めて関数の本体に入れます。

他方で,ループはというと,for-文の類だったら,カウンタにするレジスタをひとつ決めておいて(x86 系だったら ecx とか),inc 命令なり dec 命令なりでインクリメント/デクリメントしつつ,終了条件を判断すればいいだけです。これだけならメモリアクセスは普通ない。条件判断は終了条件によってはやや高価になるけれども,一般的には非常に安上がりです。

ま,コンパイラで適切な最適化を行ってくれたら,関数呼び出しもループも同じようにインラインで展開してくれるし,ループも中身をばらしてくれたりするので,違いがなかったりもするんですが。あくまでも,アセンブリレベルでの話ですけど。

なんつか,自分も気をつけなくちゃとは思うけれども,こゆ都市伝説を広めてるやつ出て来いとも思う。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN