Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

再帰しない竹内関数の高速化( 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の限界か

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした