再帰関数(メソッド)のチューニング例

##人の書いたコードを書き直したくなる病気
「C#の多倍長整数型(BigInteger)の数学メソッドをちょびっと書きました」の最大公約数算出メソッド

最大公約数

public BigInteger GCD(BigInteger x,BigInteger y) {
    if(x < y)
        SwapNum(ref x,ref y);
    return y == 0 ? x : GCD(y,x % y);
}

public void SwapNum(ref BigInteger x,ref BigInteger y) {
    BigInteger tmp;
    tmp = x;
    x = y;
    y = tmp;
}

再帰メソッドは一度呼ぶだけで内部的に何度も実行されるため、ちょっとした効率化にけっこう効果があったりします。
上に挙げたメソッドもこれはこれでまったく問題ないんですが、いくつか無駄があるので段階を踏んでだんだん効率アップしていきます。

##先にオチを書いておく
この短いコードに最適化できるネタが複数入っているので興味を引いただけで、ここに書かれるコードに実用的価値はありません。

• ユーグリッド互除法が優秀すぎるため、扱う数が大きくなってもそれほど深い再帰にはならない。
  再帰やループのネストが深いところほどちょっとした改良がパフォーマンスに大きな影響を与えるんだけど、このメソッドだとそれほどでもない。
• ネタ元の@Euglenachさんも書かれているように、BigInteger型は標準で最大公約数メソッドを持っている。
  標準ライブラリは実行効率もよく考えられているので、たいていの場合車輪の再発明をする価値はありません。

##気を取り直して、改良してみよう

再帰やループの高速化の基本は「終了条件はなるべく先に、他の処理をやる前に書く」
この場合の終了条件は「y == 0ならxを返しこれ以上再帰しない」の部分。その前に「小さい方の数をyにする」という処理があるけど、これは「x == 0ならyを返し、y == 0ならxを返す」とすればメソッドの先頭に移動できる。

step1

public BigInteger GCD(BigInteger x,BigInteger y) {
    if(x == 0) return y;
    if(y == 0) return x;
    if(x < y)
        SwapNum(ref x,ref y);
    return GCD(y,x % y);
}

とはいってもこの場合後半の処理をすっ飛ばせるのは「最初にxまたはyが0のときか、最大公約数が見つかった場合だけ」なのであまり速度に違いはないです。

#必要なのは変数を入れ替えることじゃない

    if(x < y)
        SwapNum(ref x,ref y);

の部分がやろうとしてることは「大きい方の数と小さい方の数の組み合わせが欲しい」というだけで、それを入れる変数がxとyである必要はない。
だってその後やってることはGCDの引数として使うだけだから。
それならこう書いた方がメソッド呼び出しが減って速度が速くなる。

step2

public BigInteger GCD(BigInteger x,BigInteger y) {
    if(x == 0) return y;
    if(y == 0) return x;
    BigInteger large, small;
    if(x < y)
    { large = y; small = x; }
    else
    { large = x; small = y; }
    return GCD(small, large % small);
}

#再帰するときのパラメータに注目

このコードは最大公約数を得るためのものということもあって、xとyに負の数が入ることは想定されていない(と思う)。
そして最後の行で再帰のために渡しているパラメータは

• 第一パラメータ(x)は決して0にはならない。(0の場合は一行目か二行目ではじかれて最後の行に到達しないから)
• 第一パラメータ(x)は常に第二パラメータ(y)より大きい。(余りは必ず割る数より小さいから)

となると、再帰呼び出しされている場合は「xが0」と「xがyより小さい」を考慮する必要がないことになる。
だったら「メソッドとして公開する部分」と「最大公約数を探す部分」を分けると比較と条件分岐を減らせる。

step3

//最大公約数を求める公開メソッド
public BigInteger GCD(BigInteger x, BigInteger y) {
    if (x <= 0 || y <= 0) return 0;//最大公約数を求めるのに0を渡すことはないだろうけど、念のため

    BigInteger large, small;
    if (x < y)
    { large = y; small = x; }
    else
    { large = x; small = y; }
    return innerGCD(small, large % small);
}

//最大公約数を求める処理本体
private BigInteger innerGCD(BigInteger large, BigInteger small) {
    if(small == 0) return large;
    return innerGCD(small, large % small);
}

三項演算子を使ってもっとコンパクトにしてみよう。

step4

//最大公約数を求める公開メソッド
public BigInteger GCD(BigInteger x, BigInteger y) {
    if (x <= 0 || y <= 0) return 0;//最大公約数を求めるのに0を渡すことはないだろうけど、念のため
    return (x < y) ? innerGCD(x, y % x) : innerGCD(y, x % y);
}

//最大公約数を求める処理本体
private BigInteger innerGCD(BigInteger large, BigInteger small)
    => (small == 0) ? large : innerGCD(small, large % small);

こんなに短くなったよ！それにたぶん速くなったよ！
でもちょっとわかりにくいので、わかりやすさではstep2くらいがちょうどいいかもね。
そして上の方で書いたように、BigIntegerの標準メソッドがあるのでまったくの無駄だよ！

まあ再帰関数は「外部から呼ばれたときにだけ必要な処理」と「本当に再帰する必要がある処理」に分けることで効率がよくなるケースは割とあるので参考までに。

##おまけ(追記)

「あ、ローカル関数ってまさにこういうときに使うやつだった」と思い出したので、innerGCDをローカル関数化してひとつのメソッドにまとめました。

step5

//最大公約数を求める公開メソッド
public BigInteger GCD(BigInteger x, BigInteger y)
{
    //最大公約数を求める処理本隊(再帰ローカル関数)
    BigInteger innerGCD(BigInteger large, BigInteger small)
        => (small != 0) ? innerGCD(small, large % small) : large;

    if (x <= 0 || y <= 0) return 0;//最大公約数を求めるのに0やマイナスを渡すことはないだろうけど、念のため
    return (x < y) ? innerGCD(y, x) : innerGCD(x, y);
}