10.3 アルゴリズムの高速化

Aさん

自動で並び替えをやってくれるのはうれしいけれど，このプログラム時間がかかりますねぇ．

M先生

そうだね．並び替えっていうのは，コンピュータができる仕事のうちでも，時間がかかる仕事といわれている．でも，問題はアルゴリズムにもあるんだ．この並び替えプログラム高速化する方法を教えてあげようか．

Aさん

でないと，日が暮れてしまいます．

M先生

よろしい．では，繰り返し実行ではなく，一回一回実行して，一回ごとにプログラムを見ていこう．

Aさん

わかりました．

M先生

今のプログラムだと，先頭に追加したときに カーソル位置 が1に戻ってしまっていることが分かる？

Aさん

あ，ほんとだ．なんでですかね？

M先生

これはSqueakの入れ物を作った人が，カーソルが戻った方が便利だと考えたからそうなるんだろうね．

Aさん

今回の場合は単なるおせっかいですね．

M先生

そうだね．カーソル位置が戻ってしまうと，なかなか最後までいかないから，プログラムが遅くなってしまっている．だからこうしてカーソル位置を変数で記憶しておいて．．

M先生

で，追加した後，カーソルを戻してやればよい．

Aさん

あ，すごく速くなった！今度は一瞬で終わります．

M先生

そう．アルゴリズムには速いものや遅いものがあるんだ．これをアルゴリズムの「 効率 」という．同じ仕事でも，効率が良いアルゴリズムを使うと一瞬で終わるものが，効率の悪いアルゴリズムでは，地球が始まってから今まで計算しても終わらないぐらいの差が出ることもあるんだ．

Aさん

げげ．効率って大事なんですね．

練習問題10.1

日常行っている仕事のアルゴリズムを記述してみよう．