以前から色々ご指摘頂いているkp氏から、今回のループへの展開の実測結果についての考察を頂いています。有難うございます。
「河馬は赤い血を流す」より引用します。
以前再起関数はループに変換でき、ループにしたほうが一般的に速いと書きましたが、この際当然ながらアルゴリズム自体をループに適したものにしなければ速くなることはないでしょう。
なるほど。ということは、再帰呼び出しのコストはそもそもそれほどヘビーではないのかも知れませんね。ループに適したアルゴリズムの方が、再帰で書く方が見た目簡潔なアルゴリズムよりも一般的には速いだろう、と。これは、アルゴリズムを選定する場合の一つの目安として考えるべきなのかも知れません。
なお今回、私は読者に分かり易いということを第一に、高校生の教科書に載っている通りのアルゴリズムを選択していまず。そもそも初手から高速になり得ないものを選択してしまっているわけです。無駄の多いアルゴリズムであることは最初から承知していますし、それは既に屁理屈太郎氏からも指摘頂いています。
ということで、そもそも今回は高速化そのものが目的ではなく「JavaとＣとで（見た目）同じに見えるソースコードで、その実行性能にどれだけ違いがあるのか」もしくは「JavaとＣとで、性能のボトルネックとなっている部分はどこなのか」ということを調べることが主眼ですので、ループに展開する際にアルゴリズムを変更してしまっては意味が無いと私は考えています。
行列式の計算についてのより高速なアルゴリズムはすでによく知られていますし、わざわざ私がここで改めて考えたとしても、あまり意義は無いんではないかと。参考→掃き出し法による行列式計算
ですから、kp氏の以下の部分の指摘については、今回の論点からは外れているように思います。
件のソースでは二行二列まで展開した部分で、結果的に同じものを複数回計算しています。これを解消しようとすれば、必然的にループの形態をとることになるはずです。
行列式の計算以外でも、例えば階乗の計算やフィボナッチの計算などでは、その定義が再起的であるが故に再起関数として実装するととてつもなく遅いプログラムが出来上がります。これらも逆方向(数字の小さい方)から計算するなら、ループにするのが自然です。
ただ、どうせこの日記は暇つぶしですから、今やってる実測の比較が終わったら、色々な行列式計算のアルゴリズムを用いたプログラムの実測をやってみようかなぁとも思っています。参考にさせて頂きます。
数字の小さい方から求めるとか、確かに計算回数を減らせるような気がするので、頭の体操代わりに自分で考えて見ようかと。
あと、同じ日の日記で以下のような指摘を頂いています。引用します。
Pentium4 1.9GHz+Borland C++ 5.5で3.5秒前後。ただ改変する前も7秒程度で終了していた。さらに、事前メモリ確保バージョンを試したところ4.5秒程度だったので、ただ単に gccのmallocの実装がタコってるだけのような気もしてきた。
