再帰する竹内関数も高速化

再帰しない竹内関数の高速化( https://qiita.com/nihongi/items/cb8ba21562d430d4fc63 )の続きです。前回、形が変わりすぎて竹内関数だか何だかわからなくなってきたので、原点に返ります。

正しい竹内関数

tarai02.sh

# !/bin/sh
tarai() {
  echo "${1} ${2} ${3}" >&2
  if [ ${1} -gt ${2} ]; then
    echo -n $(tarai $(tarai $(( ${1} - 1 )) ${2} ${3}) \
                    $(tarai $(( ${2} - 1 )) ${3} ${1}) \
                    $(tarai $(( ${3} - 1 )) ${1} ${2}))
  else
    echo -n ${2}
  fi
}

tarai ${1} ${2} ${3}
echo

前回までの知見で、遅延評価は効果絶大、遅延評価をすればメモ化は不要ということがわかりました。まず、上記のコードを少しだけ変形します。

tarai06.sh

# !/bin/sh
tarai() {
  echo "${1} ${2} ${3}" >&2
  if [ ${1} -gt ${2} ]; then
    x=$(tarai $(( ${1} - 1 )) ${2} ${3})
    y=$(tarai $(( ${2} - 1 )) ${3} ${1})
    z=$(tarai $(( ${3} - 1 )) ${1} ${2})
    echo -n $(tarai ${x} ${y} ${z})
  else
    echo -n ${2}
  fi
}

tarai ${1} ${2} ${3}
echo

ちゃんと再帰呼び出ししています。外側のtaraiに渡す引数を予め計算するように変えただけです。

身も蓋もないショートカット

ここで、x<=yであればTarai(x, y, z)の結果はyだとわかっているので、taraiの呼び出しを省略できます。いわゆる遅延評価というより、ショートカットですね。

tarai07.sh

# !/bin/sh
tarai() {
  echo "${1} ${2} ${3}" >&2
  if [ ${1} -gt ${2} ]; then
    x=$(tarai $(( ${1} - 1 )) ${2} ${3})
    y=$(tarai $(( ${2} - 1 )) ${3} ${1})
    if [ ${x} -gt ${y} ]; then
      z=$(tarai $(( ${3} - 1 )) ${1} ${2})
      echo -n $(tarai ${x} ${y} ${z})
    else
      echo -n ${y}
    fi
  else
    echo -n ${2}
  fi
}

tarai ${1} ${2} ${3}
echo

前回のスタック版と時間を比較してみます。

$ time sh tarai05.sh 100 50 0 2>/dev/null
100

real    0m4.218s
user    0m3.912s
sys     0m0.303s
$ time sh tarai07.sh 100 50 0 2>/dev/null
100

real    0m7.628s
user    0m2.107s
sys     0m5.505s

スタック版の方が速いですが、今回の再帰ショートカット版もいい勝負しています。スタック版ではほとんどの時間がuserモードなのに対して、再帰ショートカット版では、sysモードの時間が大きいという点が興味深いです。

bashの限界か

やっぱ、もっとモダンな言語でやった方が良いよね。(感想)