大域的最適化
手続き呼び出しの最適化
再帰手続きの最適化
末端再帰とは
名前の通り、その手続きの本体の最後に自分自身を呼び出す
末端再帰の除去
末端再帰呼出しは、無条件ジャンプで置き換えられる
ただし、実引数を仮引数に設定しておくこと
>手続き本体の最後で自分自身を呼び出す場合には、呼び出された手続きのデータ領域(駆動コード)は呼び出し側の手続きのデータ領域を再利用することができ、その制御情報も再利用できる。また、呼び出し側の手続きが保存しておくべきほかの情報がないことから、この末端再帰の除去の最適化となっている。
c_Bool ans;
int a[10000];
void Bsearch(int x, int i, int j) {
int m;
if(i>j){
ans=false;
}else{
m=(i+j)/2;
if(x>a[m])Bsearch(x,m+1,j);
else if(x<a[m])Bsearch(x,i,m-1);
else ans=true;
}
}
↓
_Bool ans;
int a[10000];
void Bsearch(int x, int i, int j) {
int m;
L:if(i>j){ // ラベルを付与
ans=false;
}else{
m=(i+j)/2;
if(x>a[m]){i=m+1; goto L;}; // goto文にした
else if(x<a[m]){j=m-1; goto L;}; // goto文にした
else ans=true;
}
}
↓ // そもそも関数にしない
while(true){
if(i>j){
ans=false;break;
}
else {
m=(i+j)/2;
if(x>a[m])i=m+1;
else if(x<a[m])j=m-1;
else{ans=true;break;}
}
}
手続き間最適化
ソースコード全体の最適化
他にも
その一時変数がその後も使えるかどうかを考えたり、途中式をあとで使うかを考えたりし、処理を減らしたり、記憶したりさせたり。