この記事はボトルネックになりやすいループする処理を省略するか高速化すればプログラムは大きく高速化しやすいということを仰々しく述べる記事です。
プログラムの計算量はオーダーと呼ばれる単位で表されることがままあります。オーダーとはアルゴリズムの最大次数を表したものです。ざっくばらんに言えば、巨大なデータを扱ったときの計算量の増え方を表したものです。オーダーはO(n)、O(n^2)、O(logn)などと記述します。
int a = 1; for(int i = 0; i < n; i++) a++;
ならばnが十分に大きい時、n回の計算をするのでO(n)と表します。
int a = 1; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) a++;
ならばnが十分に大きい時、n^2回の計算をするのでO(n^2)と表します。下図はよくあるオーダーの値の変化の比較です。
定数オーダーO(1)の計算量が小さいこと、乗数が絡んだオーダーが極端に大きくなることがわかります。先ほど挙げた様にプログラムのループ部分はO(n)となり、二重ループ部分はO(n^2)となります。仮にnが十分に大きいとした場合、計算時間のを大半を占めるのはO(n)以上の部分であり、ループ部分はそのO(n)以上の部分になります。つまりnが十分に大きい場合、ループ部分が計算時間の大半を占めやすいといえます。ここからプログラムの大きな高速化は計算時間の大半を占めるであろうループの様な何度も呼ばれる部分を高速化、あるいは省略することで実現しやすいといえます。
速度を要求されるプログラムを作る場合、ループ内のコーディングには工夫を凝らすべきであり、そもそもループ中の処理を減らした方がよいです。また、一見ループでなくとも呼びだした先がボトルネックとなっている場合もあります。SQLや関数などはよく見えないところで行動していたりします。関数単位、行単位の呼び出し回数、実行時間を調べることがボトルネックがどのタイミングにあるかの把握になり、どこがボトルネックであるかを知ることにつながりやすいです。ループ内のコーディングに凝らす工夫としては、諸所の小技をググったりするとよいと思います。大体、目的に適したシンプルな関数なり記述なりが高速化につながっています。
