学科の2年生になったつもりで，書いてみます*1．
呼び出し回数を求める方法，とりあえず一つ
最後の問題は…
次のプログラムで，関数fibの呼び出し回数を求める方法を，2種類答えなさい．そして実際に関数fibの呼び出し回数を求めなさい．
/* fib.c */ #include <stdio.h> int fib(int n) { if (n <= 2) return 1; else return fib(n - 1) + fib(n - 2); } int main(void) { printf("%d\n", fib(40)); return 0; }
前回の授業で，類題がありました．たしか，関数に引数を一つ増やす方法でした．その引数はintのポインタでした．
今回は，こうですか…
/* fib.c */ #include <stdio.h> int fib(int n, int *p) { (*p)++; if (n <= 2) return 1; else return fib(n - 1, p) + fib(n - 2, p); } int main(void) { int c = 0; printf("%d\n", fib(40, &c)); printf("%d\n", c); return 0; }
先週は，「(*p)++」のところを「*p++」と書いて，失敗して，TAに詳しく教えてもらったのでした．
さて動かしてみると…
$ make fib $ ./fib 102334155 204668309
結果が出ました．
静的変数でカウントするのは?
あのときのTAさんだ．
「うまく，いきましたね」
「あ，はい」
「問題文には2種類とありますね．もう一つは，どうしますか?」
「えっと…このカウンターをですね，ポインタ渡しにするんじゃなくて，グローバル変数に格納するか，fibの中でstatic変数を宣言するか…」
「グローバル変数を使うほうは，大丈夫．だけど，fibの中で静的変数を定義してカウントするのは，うまくいきません」
「ダメなんですか?」
「実際にプログラムを書いてみればわかるけど*2，出力が大変なことになります」
「出力?」
「はい，関数呼び出しのたびに，今，何回目の呼び出しですっていう出力をするんですよ．合計2億回以上」
「…」
「『最終的に何回呼び出しました』だけを出力したければ，関数呼び出しの外から，何回呼び出したかを格納しているカウンターを参照できないといけないですね」
「ああ，それで，fibの中でstatic変数を作るというのでは，その変数が外から参照できない，だからダメってことですか」
「そうです．先週の問題で，静的変数を定義してよかったのは，関数の中だけでカウントし，そのつど出力するのでよかったからなのです」
元のプログラムを書き換えずに，関数の呼び出し回数を求める方法がある
「でもグローバル変数は使うなと，授業で…」
「そうですね．では全く別の方法を，やってみてくれますか」
「考えるんですか?」
「いえ，先生から，何人かには別の方法を伝えていいと聞いてますんで」
「変なやり方ですね，解き方を教えてくれるって」
「どこかで盛り上がれば，それが演習室全体に波及する，というのを期待されてるようですが」
「へえ」
「それでその方法ですが…gprofというコマンドを調査してください」
「g p r o f，ですか．わかりました」
「そうそう，ソースコードは出題時のに戻しておいてください」
「そこから，何か書くということですか?」
「いえ，ソースコードは手を加えません」
「そんなんでいけるんですか!?」
「ええ．gprofで，できるんですよ」
TAさんは，巡回のため離れていきました．
gprofについて，Googleで調べてみます．上位に来たのはこの2つ．
今回のプログラムなら，こんな風にコマンドを実行していけばいいのでしょうか…
$ gcc -pg -o fib fib.c $ ./fib 102334155 $ gprof ./fib
大量にメッセージが出てきた! そしてまたTAさんが来た．
「どうですか?」
「よく分からないんですが」
「マウスで，端末の右のところを上にスクロールすると，何か出てきませんか?」
「えっと…あ，これですか?」
index % time self children called name
<spontaneous>
[1] 100.0 0.03 1.57 main [1]
1.57 0.00 1/1 fib [2]
-----------------------------------------------
204668308 fib [2]
1.57 0.00 1/1 main [1]
[2] 98.1 1.57 0.00 1+204668308 fib [2]
204668308 fib [2]
-----------------------------------------------「これですね．どう読み解きますか?」
「fibの，204668308というのは…」
「最初のプログラム修正で，合計呼び出し回数を出したところまで，スクロールしてみてください」
「はい…にい，ぜろ，よん，」
「下3桁を覚えておきましょう」
「さん，れい，きゅうです」
「はい．それでもう一回，gprofの出力のところを見ると，どうですか?」
「にい，ぜろ，の，下3桁は，さん，れい，はち．あれ?」
「fibからfibを呼び出すのが，204668308回なのです」
「1個，足りませんが」
「mainからfibを呼び出すのが，1回，ありますね」
「あっ!」
同じ結果に至る2種類の方法を考える意義
「TAさん」
「はいなんでしょう」
「その反応，先生みたいですね」
「ええ，先生の口癖ですね(笑)」
「えっと，2通りの方法で，204668309回，fibを呼び出したのを確認したのですが，これは何になるんでしょうか?」
「うーんと，なんでこんな問題を解くのか，ですか?」
「そうです」
「授業が始まる前に，先生から聞いたところ，もともとはgprofを自習して求めなさいという問題文だったそうです」
「はあ」
「でもそれほどプロファイラが使われるわけではないし」
「プロファイラ? …あ，Webで見たとき，書いてました」
「それと，さっきmainからの1回分を忘れそうになりましたが，その誤答でおしまいにするのはよくないなと，なったようですね」
「それで，2種類の方法でカウントして，同じになることを確認させたんですか」
「そういう出題意図だそうです．あと，どんなときにどっちの方法を使うといいか，考えてみるのは，発展課題としていいですね，ともおっしゃってたかな」
「どんなときに…?」
「どんなときに，最初の，ポインタ渡しでカウントするのがよく，どんなときに，gprofを使うのがいいか，です」
「はあ．えっと…gprofを使うメリットは，元のプログラムを修正しなくていいこと，ですよね」
「そうです．言い換えると，ソースファイルを修正することなく，実行時の関数の呼び出し回数を数えるには，gprofを使うといい，となります」
「では，ソースファイルを修正していいのなら，ポインタ渡しにする，ですか?」
「それは論理的ではありませんねえ」
「あ，はい…」
「課題のプログラムを実行するときに，fib(40)は何回呼び出しますか? fib(39)は何回呼び出しますか? …というように，引数ごとにfibの呼び出し回数を分けると，どうなるでしょうね?」
「えっと…」
「あ，プログラムの修正は，どうしても作ってみたいときにやってください．引数ごとの呼び出し回数は，gprofで求められますか?」
「…無理っぽいですね」
「ええ，無理なのです．より細かく，呼び出し回数を求めたいときは，プログラムに手を加えざるを得ないのです」
フィボナッチ数を再帰呼び出しで計算してはいけないのはなぜか
「そういえばこのプログラム，結果が出るまでちょっと時間がかかるんですけど」
「ああ，それも，出題の意図でしたねえ」
「なんでなんですか?」
「このプログラムのように，フィボナッチ数を再帰呼び出しで計算すると，効率が悪いのです」
「…」
「fib(40)，つまりフィボナッチ数列の40番目の値を求めるのに，2億回を超えるの関数呼び出しが必要って，おかしいと思いません?」
「言われてみれば」
「さっき言った，fibの各引数を何回呼び出すかってのを，fibに与える初期値ごとに求めると，面白い性質が出てくるんだけどね」
「えっとどういうことでしょうか?」
「2重ループを作ってください」
「はあ，まあ，なんか難しそうですが」
「プログラムを書かずに，ちょっと考えてみましょう．fib(40)の値を求めようとしたら，再帰呼び出しで，fib(39)とfib(38)を求めて，その足し算としますね」
「はい，再帰で」
「そこでfib(39)を求めるとき，やっぱり再帰呼び出しで，fib(38)とfib(37)を求めて，足し算ですね」
「はい」
「fib(40)を求めるときの2番目の項のfib(38)と，fib(39)を求めるときの1番目の項のfib(38)って，2回出るのは，どういうことだと思いますか?」
「2回，fib(38)を呼び出しているんですか?」
「そうです．fib(40)という一つの値を，このプログラムで計算するときには，fib(38)を2回呼び出すのです．ちなみにfib(37)を呼び出す回数は，もう少し多くなります．fibの引数が小さくなればなるほど，その関数を呼び出す回数は，どんどん大きくなります」
「大きくなるということは…?」
「それが，このプログラムの実行効率を，悪くしているということですよ．もしですね，すでにfib(38)を求めているんだから，その結果を使いましょうというように，例えば配列を導入して，プログラムを書き換えたらですね…」
「配列を導入したら…」
「呼び出し回数を，うんと小さくできます．再帰を使っていても」
「ということは，このプログラムでちょっと時間がかかる原因は，再帰を使っているからではないってことですか?」
「再帰は共犯者ですかね．主犯は，fibの同じ引数の値を，ほしいと言われたらそのたびに計算しているところです」
「あともう一つ，教えてください」
「いいですよ」
「再帰だけど，効率が悪くない例って，ありますか?」
「そうですねえ，階乗を求めるのは，問題ないでしょうね」
「え，でもあれは，引数が12か13で，オーバーフローになりますよね?」
「うん．じゃあ，階乗の定義式の掛け算を，足し算にかえて，計算する関数を，再帰呼び出しで作ってみてください．それで，大きい値で呼び出しても，時間的には問題ないはずです」
「へえ」
「再帰呼び出しの回数が，引数の値で押さえられるからなんですけどね．同様に，再帰呼び出しでトラックバックをして，深さ優先探索をするのも，素直にプログラムを組めば，効率良くできます」
先生モードで，落ち穂拾い
- このプログラムで，fib(x)の呼び出し回数は，fib(x)の値をyとすると，y*2-1回です．
- このプログラムでは，fib(46)までは大丈夫です（sizeof(int)が4のとき）．fib(47)を求めるとオーバーフローします．
- プログラムを書き換えるのと，gprofのそれぞれで，呼び出し回数を求めるのは，デバッグライト（printfデバッグ）と，gdbで，処理状況や式の値を求めるのと，同じようなものです．
- gprofは，-bオプションをつけると，出力が簡潔になります．
- 「ソースファイルを修正しないなら，gprofを使う」と同値な命題は，「gprofを使わないなら，ソースファイルを修正する」（対偶）であって，「ソースファイルを修正するなら，gprofを使わない」（裏）ではありませんね．
