アルゴリズムを評価するのは、プロにとっても難しい。

アルゴリズム - 186::Diary
* あとメモ化のときの最初の呼び出し回数の評価も間違ってるよね. 1回目は関数をナイーブな実装で評価するから.

ところが、この下りに関して間違いなのは私の元発言ではなく、この突っ込みの方なのである。

そのことは、以下を見れば一目瞭然である。

ナイーブ
プログラム:
出力:
エラー:
メモ化
プログラム:
出力:
エラー:

見てのとおり、二番目の方ではナイーブ実装な実行された回数を数えている。何と出たであろうか。

見ての通り、上のプログラムでは、実行前にメモをわざわざ空にしている。それにも関わらず、ナイーブ実装が呼ばれる回数は厳密にnだ。なぜだろう?

答えは、fib(n-1) + fib(n-2)が同時に実行されるのではなく、どちらかが先に実行されるからだ。再帰から戻って来たとき、もう片方の答えはすでにメモされているのだ。このことは、c++の隣にp('fib(' + n + ')');を加えて実行してみればわかる。

しかしここで主張したいのは、「私の方が正しい」ということではない。実は私もid:smoking186さんと同じ勘違いをしそうになったのだ。しかし私はコードを実際に書いて動かして見た。そして書いて動かしてみれば、この場合は自分の考えが正しいかどうかは手が教えてくれるのだ。「間違い」を指摘してくださるのは結構なのだが、これらのうち実際に自分で動かした上での指摘はどれくらいあるのだろう?

2007-11-29 - okamoto7の日記
アルゴリズムについてこうなんというか不正確な記述がたくさんあって，書いている本人が理解してるかどうかも判断しにくい文章にたくさんブックマークがついていて，しかもそのような方がアルゴリズムに関する書籍を執筆しようとしているという状況がなんかこわいです．

何より私自身が賛成だ。にも関わらず、私ごときがアルゴリズム本を書く気になったのは、アルゴリズムというのはプログラム以上に間違えやすい、というより間違いに気がつきにくいものだからだ。「裸のアルゴリズム」が正しいか否かを証明するのは、数学の証明のように結構難しい。難しいだけあって、しかしそれがプログラムの形で実装されていれば、少なくとも期待どおりの挙動を示すかどうかはそれを動かしてみるだけでわかる。そして動きがあるということは、頭だけではなく目と手でも理解できるということだ。

私が書きたいのは、実際に動く、目と手で触れることができるアルゴリズム本だ。用語の的確さ、内容の正確さは後で直していくこともできる。しかしそこにモノがなければ、それが正しいか間違っているかを判断することすら出来ない。実際、二分検索のオーバーフローバグがわかったのだって、実際にバグが利用によって顕在化してからではないか。

というわけで、私は恥もコードも晒すことにしたのである。

Dan the Man to Err -- and Try