再帰しない竹内関数の高速化( 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の限界か
やっぱ、もっとモダンな言語でやった方が良いよね。(感想)