はじめに
早期returnは熟練の凄腕プログラマーが正しく使えば非常に可読性の高いコードを書くことが出来ます。
一方で、break,continue,return文がしばしば「飼いならされたgoto文」と呼ばれるように本質は機能の制限されたgoto文であるため、考えなしに使うと可読性を著しく低下させる要因になり得ます。
個人的にはgoto文と同様、あるいはそれ以上に注意して使うべきだと思います。1
本記事では、早期returnの危険性およびそれを回避する方法、使っても良い場面について個人的な意見を述べていこうと思います。
なお、私は競技や個人開発を主に行っており、プログラムを業としているわけではないため、プロの方から見たらツッコみどころの多い記事になっているかもしれません。
一応、この記事はかの有名なリーダブルコードの「アホくさ」に反論するために書いた記事2ですが、肝心のリーダブルコードは未履修のエアプです。
追記:別に複数のreturnが嫌いなわけではないです。むしろ無理にreturnを1つにまとめると代入が戻り値を決定する処理になって分かりづらくなることがあるので、ifで分岐してやった方が戻り値が明確になって分かりやすくなります。
早期returnの危険性
暗黙のifブロックが生成される
いきなり変な例ですみませんが、以下のコードを見てください。
/**
*@details 正整数に対して、立っているビットの中で最も左のビットが何番目かを返す
*@note 計算量: nの桁数をkとして、Θ(logk)
*@param [in] n 正整数
*@return 立っているビットの中で最も左のビットが何番目か
*/
int bsrPlus(unsigned int n){
int ans=0;
if(n>>16!=0){ans+=16;ans>>=16;}
if(n>>8!=0){ans+=8;ans>>=8;}
if(n>>4!=0){ans+=4;ans>>=4;}
if(n>>2!=0){ans+=2;ans>>=2;}
if(n>>1!=0){ans+=1;ans>>=1;}
return ans;
}
/**
*@brief 立っているビットの中で最も左のビットが何番目かを返す(早期return版)
*@details 入力が0の場合、-1を返す
*@note 計算量: nの桁数をkとして、Θ(logk)
*@param [in] n 入力
*@retval bsr_plus(n) nが正整数
*@retval -1 nが0
*/
int bsrEarly(unsigned int n){
if(0==n) return -1;
return bsr_plus(n);
}
/**
*@brief 立っているビットの中で最も左のビットが何番目かを返す(if版)
*@details 入力が0の場合、-1を返す
*@note 計算量: nの桁数をkとして、Θ(logk)
*@param [in] n 入力
*@retval bsr_plus(n) nが正整数
*@retval -1 nが0
*/
int bsrIf(unsigned int n){
if(n!=0){
return bsr_plus(n);
}else{
return -1;
}
}
Bit Search Reverseと呼ばれる処理になります。単に真っ先に思い付いたのがこれなだけで、具体的な処理の内容は本質ではないです。
ここで、bsrEarlyとbsrIfは本質的に同様の複雑さの処理を行っているはずです。
にも関わらずbsrEarlyではインデントが浅くなっています。
これは、本来発生すべきインデントを早期returnで隠蔽していると見ることが出来ます。
インデントは可読性を高めるために付けるものにも関わらず、それを隠蔽しているということは、場合によっては可読性を低下させ得るということです。
私はこれを「暗黙のifブロック」と呼んでいます。
そのため、むやみに早期returnを使うと見かけ上はシンプルでも実際には複雑な処理になっている危険性があります。
コーディング規則でインデントの深さを制限している場合は特に注意が必要で、表面上インデントの深さが規則の範囲内でも、早期return込みだと実質的なネストの深さが規定より遥かに深くなっているということがあり得ます。
1つのサブルーチンが複数の役割を持ってしまう(単一責任の原則の違反)
早期returnを利用したい場合といえば、本筋とは関係ない例外的な処理を弾きたい場合だと思います。
ここで冷静に考えると、そのようなサブルーチンには1つのサブルーチン内に「本筋とは関係ない処理を弾く処理」と「そのサブルーチンが行うべき本質的な処理」の2つの役割が混在していることが分かると思います。
ソフトウェア開発には「1つのサブルーチンが持つ役割は1つであるべき」という原則があるらしいです(単一責任の原則)
単一責任の原則の観点で言えば早期returnで処理を弾きつつ本質的な処理を同一サブルーチンで行うことは望ましくなく、本質的な処理と例外的な処理を別々のサブルーチンに分割することがより望ましいと言えます。
早期returnを回避する方法
ラッパーを作り、サブルーチンを分割する
例外を弾くラッパーと本質的な処理を行うサブルーチンに分割し、役割を明確にします。
大抵の場合、ifをネストさせても十分見通せる処理になると思います。
/**
*@details n^m mod pを求める@n
*モンゴメリ演算を使わない ~手抜き~ シンプルな繰り返し二乗法で計算する。
*@note 計算量はΘ(log m)
*@param n 底
*@param m 指数
*@param p 法
*@return n^m mod pを返す
*/
unsigned modPow(unsigned n,unsigned m,unsigned p){
unsigned ans=1;
while(m){
if((m&1)!=0){ //mの最下位ビットが1なら
ans=(unsigned long long)ans*n%p;
}
m/=2;
n=(unsigned long long)n*n%p;
}
return ans;
}
/**
*@details ミラーラビンの1ステップ,2工程目@n
* a^dに対して、二乗をs回繰り返し、どこかで-1が出れば素数の可能性がある
*@note 計算量はΘ(s)@n
*s<=log(n)なので、Θ(logn)
*@param [in] n 素数判定したい3以上の奇数n
*@param [in] ad 1工程目で求めた数a^d
*@param [in] s n-1を素因数分解した際の2の数
*retval -1 nが素数の可能性がある
*retval 0 nが確実に合成数
*/
int millerStepSecond32(unsigned n,unsigned ad,unsigned s){
int i=0;
while(i<s&&ad!=n-1){ //s回二乗を繰り返し、-1が現れないか確認する
ad=(unsigned long long)ad*ad%n;
i++;
}
if(n-1==ad){ //2^{{2^r}d}=-1となるrが存在した
return -1; //素数の可能性がある
}else{ //全てのrで2^{{2^r}d}!=-1
return 0; //確実に合成数
}
}
/**
*@details ミラーラビンの1ステップ,1工程目@n
* a^d=1なら、素数の可能性がある。そうでないなら、2工程目を行う
*@note 1工程目のみの計算量は繰り返し二乗法のΘ(logd) \n
* d<=(n-1)/2なので、最悪計算量Θ(logn)
*@param [in] n 素数判定したい3以上の奇数n
*@param [in] a 素数の証人(一般のミラー・ラビンの場合ランダムな数)
*@param [in] s n-1を素因数分解した際の2の数
*@param [in] d n-1を素因数分解した際の2以外の素因数の積
*retval -1 nが素数の可能性がある
*retval 0 nが確実に合成数
*/
int millerStep32(unsigned n,unsigned a,unsigned s,unsigned d){
unsigned ad=modPow(a,d,n);
if(ad!=1){ //a^dが1でないなら、2工程目を行う
return millerStepSecond32(n,ad,s);
}else{ //a^dが1
return -1; //素数の可能性がある
}
}
/**
*@details n-1を2^s*dの形にする
*@param [in] n 整数n
*@param [out] s n-1を素因数分解した際の2の数
*@param [out] d n-1を素因数分解した際の2以外の素因数の積
*/
void millerSplit32(unsigned n,unsigned *s,unsigned *d){
*d=n-1;
*s=0;
while(0==(*d&1)){ //dが偶数の間、dを2で割り続ける
*d/=2;
(*s)++;
}
}
/**
*@details 32ビットで3以上の奇数に対する 決定的ミラー・ラビン @n
*証人2,7,61でミラー・ラビンの1ステップを実行する
*@note 計算量はn-1=2^s*dとすると、1工程目でΘ(logd),2工程目でΘ(s)@n
*logd<=logn,s<=lognなので、証人1つにつきΘ(logn)@n
*32ビットの場合、証人3つで確実に素数判定できるため、全体でΘ(logn)
*param [in] n 素数判定をしたい3以上の奇数n
*retval -1 nが素数
*retval 0 nが素数でない
*/
int isPrimeOdds32(unsigned n){
unsigned s,d;
unsigned alist[]={2,7,61};
int ans=-1;
millerSplit32(n,&s,&d); //n-1を2^s*dに分離
for(int i=0;i<3&&alist[i]<n;i++){ //最大3つの証人で素数判定
ans&=millerStep32(n,alist[i],s,d); //いずれの証人でも合成数判定が出ていないなら、確実に素数
}
return ans;
}
/**
*@brief 32ビット 決定的ミラー・ラビン
*@note 計算量:nの桁数をkとしたとき、Θ(k) @n
*ただし、四則演算はΘ(1)で完了するものとする
*param [in] n 素数判定をしたい非負整数n
*retval -1 nが素数
*retval 0 nが素数でない
*/
int isPrime32(unsigned n){
//あくまでラッパーに徹し、本格的な素数判定はisPrimeOdds32()に任せる
if(n<=1){ //0,1は素数でない
return 0;
}else if(2==n){ //2は素数
return -1;
}else if(0==(n&1)){ //偶数は素数になり得ない
return 0;
}else{ //3以上の奇数
return isPrimeOdds32(n); //ミラーラビン法
}
}
gotoを使う
コーディング規則により難しい場合もあると思いますが3、明示的なリソースの確保/解放がある場合、スコープの関係でサブルーチンを分割することが難しいため、素直にgotoを使った方が良いです。
早期returnだと例外が複数箇所にある場合、リソース解放処理を複数回入れなきゃいけないので、バグの元になります。
gotoであれば解放処理を一箇所にまとめることが出来るため、解放漏れのリスクは少なくなります。4
また、早期returnと違い、gotoについては危険性が周知されており、使うべき場面が確立されているため、濫用の危険性も少ないです。
/**
*@details 正常に開かれたA,B,Cのファイルについて、A,Bの共通部分をCに出力する
*@param aFILE ファイルAのハンドル
*@param bFILE ファイルBのハンドル
*@param cFILE ファイルCのハンドル
*/
void fileUnionSucceed(FILE *aFile,FILE *bFile,FILE *cFile){
int a=fgetc(aFile),b=fgetc(bFile);
while(a>=0&&b>=0){
if(a==b){
fputc(a,cFile);
}
a=fgetc(aFile);
b=fgetc(bFile);
}
}
/**
*@brief A,Bの2つのファイルを比較し、共通部分をファイルCに出力する
*@param aName ファイルAの名前
*@param bName ファイルBの名前
*@param cName ファイルCの名前
*@retval 0 正常終了
*@retval -1 異常終了
*/
int fileUnion(char aName[],char bName[],char cName[]){
FILE *aFile,*bFile,*cFile;
aFile=fopen(aName,"r");
if(NULL==aFile){
goto aErr;
}
bFile=fopen(bName,"r");
if(NULL==bFile){
goto bErr;
}
cFile=fopen(cName,"w");
if(NULL==cFile){
goto cErr;
}
fileUnionSucceed(aFile,bFile,cFile);
fclose(cFile);
fclose(bFile);
fclose(aFile);
return 0;
cErr:
fclose(bFile);
bErr:
fclose(aFile);
aErr:
return -1;
}
最近の言語では明示的にリソースを確保/解放せずに済む仕組みもあったりするので、それを活用するのも手です。GCを生理的に受け付けない人も一定数居るとは思いますが。
余談ですが、そもそも動的なリソース(明示的でないものも含む)は極力減らした方が良いですし、使うにしてもモジュール化を徹底した方が良いです。
動的リソースを使わなければメモリリークも断片化も起こり得ないので。
使って良い場面
個人的な好みになりますが、純粋な再帰関数では使って良いと思います。
定義通りで美しいからです。
/**
*@brief 愚直フィボナッチ数
*@attention 計算量がΩ(φ^n)なので実用的ではない(φは黄金数(1+√5)/2≒1.618)
*@note 計算量:Ω(φ^n),O(2^n) おそらくΘ(φ^n)なはず。
*@param [in] n 何番目のフィボナッチ数を求めたいか
*@return n番目のフィボナッチ数を返す
*/
int dumbFibonacci(int n){
if(0==n) return 0;
if(1==n) return 1;
return dumbFibonacci(n-1)+dumbFibonacci(n-2);
}
現実的な妥協点
例外を弾くラッパーと本質的な処理に分割するのが理想ではありますが、現実問題毎回ラッパーを書くのも面倒ではあると思います。
書く側からしたら早期returnが楽なのもまた事実です。
毎回ラッパーを書くのが現実的でない場合、以下のような場面でのみ早期returnを使うのが現実的な妥協点だと思います。
- (変数宣言等を除いて)最初2行目以内にする
このようにすることで、サブルーチンの最初だけに着目すれば良く、実質的なネスト深さの追加も2段に収まるため、ある程度の見通しは確保できると思います。
typedef type int
/**
*@details 配列aの範囲[l,r)内からピボットを求める(実装略)
*@param [in] a ピボットを求めたい配列
*@param [in] l,r ビボットを求めたい半開区間[l,r)
*@return ビボットのインデックス
*/
unsigned pivot(type a[],unsigned l,unsigned r);
/**
*@details 配列aをピボットa[p]より大きい要素と小さい要素に分割する(実装略)
*@param [in] a 分割したい配列
*@param [in] l,r 分割したい半開区間[l,r)
*@param [in] p ピボットのインデックス
*@return 大きい要素と小さい要素の境界のインデックス
*/
unsigned partition(type a,unsigned l,unsigned r,unsigned p);
/**
*@brief 末尾再帰最適化のある言語での2-wayクイックソート
*@attention 末尾再帰最適化の無い言語で実行すると最悪空間計算量がΘ(N)に悪化する
*@note 計算量はpivot(),partition()の実装に依存@n
*一般的なmedian3ピボット,Lomuto/Hoare等のパーティションの場合、平均Θ(nlogn)@n
*ピボットをランダム/ランダムな3値の中央値に選び、Horareのパーティションを使うと期待Θ(nlogn)になる…はず(自信なし)@n
*
*@param [in] a ソートしたい配列
*@param [in] l,r ソートしたい半開区間[l,r)
*/
void quickSort(type a[],unsigned l,unsigned r){
if(r-l<=1) return; //サブルーチンの最初でreturnすれば、大きく複雑化することはない
unsigned p=pivot(a,l,r); //ピボットを選択
unsigned m=partition(a,l,r,p); //パーティション
if(m-l<r-m){ //前半の方が小さい
quickSort(a,l,m); //前半を再帰
quickSort(a,m,r); //後半を再帰(末尾再帰)
}else{ //後半の方が小さい
quickSort(a,m,r); //後半を再帰
quickSort(a,l,m); //前半を再帰(末尾再帰)
}
}
おわりに
読みやすいコードの基本は一つのサブルーチンやメソッドを短く,シンプルに保ち、全体を見通せるようにすることです。
早期returnのような応用技術は基本が出来て初めて効果を発揮するものです。
基本が出来ていないうちはむやみやたらに使わず、まずサブルーチンを分割できるか考えて慎重に使うべきだと思います。
-
正直なところ、普段は早期return絶対許さないぐらいの過激派ではあります ↩
-
リーダブルコードの名誉のためにより正確で高火力な表現をすると、私のように「アホくさ」の場面だけ見たエアプ勢が(リーダブルコードで正しく紹介されているであろう)本質を理解しないまま馬鹿の一つ覚えに早期returnを使いまくって読みづらいコードを量産することに文句を言う記事になります。 ↩
-
実はMISRA Cでもgotoは禁止されていないらしいです。 ↩
-
ただし、早期returnと同様暗黙のインデントは発生しますし、解放処理の前にreturnを置く形になるため、早期returnとの併用とも言えます。あくまで解放処理が1箇所にまとまるので早期returnよりマシという立ち位置です。 ↩