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

再帰しない竹内関数

More than 1 year has passed since last update.

bashで竹内関数( https://qiita.com/nihongi/items/21a4a215920150ef7eb8 )の続きです。

ジョブの定義

スタックにジョブを積んでいって上から処理していく方式に変更します。まず、ジョブの形式を定義します。

job[0]: 第一パラメータの数値、未定の場合は"x"
job[1]: 第二パラメータの数値、未定の場合は"y"
job[2]: 第三パラメータの数値、未定の場合は"z"
job[3]: taraiの計算結果の数値、未定の場合は"r"
job[4]: 計算結果rの代入先のjob(スタックの何番目か)
job[5]: 計算結果rの代入先("x", "y", "z", "r")

処理の手順は次の通りです。

  • スタックからjobを取り出す
    • rが計算済みの場合
      • これが最初のjobであれば終了
      • そうでなければ、計算結果の代入先に代入する
    • rが計算済みでない場合
      • rがすぐに計算可能か(すなわちx<=yか)→yes
        • これが最後のジョブの場合はここで終了
        • そうでなければ、計算結果の代入先にyを代入する
      • rがすぐに計算可能か(すなわちx<=yか)→no
        • jobをスタックに戻す
        • rを計算するための新たなjob(tarai4つ分)をスタックに追加する

要するに、スタックの一番上を処理して、結果が出た場合は、スタックの途中にでも結果を入れていくというスタイルです。

ソースです。

tarai03.sh
#!/bin/sh
stack[0]="${1} ${2} ${3} r -1 r"

replace() {
  # ${1}番目のスタックの文字${2}を数字${3}に置き換える
  tmp=$(echo ${stack[${1}]} | sed -e s/${2}/${3}/)
  stack[${1}]=${tmp}
}

while true
do
  i=$(( ${#stack[@]} - 1 ))
  job=(${stack[i]})
  unset stack[i]
  echo "${job[0]} ${job[1]} ${job[2]} ${job[3]} ${job[4]} ${job[5]}" >&2
  if [ ${job[3]} = "r" ]; then
    if [ ${job[0]} -le ${job[1]} ]; then
      if [ ${i} -eq 0 ]; then
        echo ${job[1]}
        break
      fi
      replace ${job[4]} ${job[5]} ${job[1]}
    else
      stack[i]="${job[0]} ${job[1]} ${job[2]} ${job[3]} ${job[4]} ${job[5]}"
      stack[i+1]="x y z r ${i} r"
      stack[i+2]="$(( ${job[0]} - 1 )) ${job[1]} ${job[2]} r $(( ${i} + 1 )) x"
      stack[i+3]="$(( ${job[1]} - 1 )) ${job[2]} ${job[0]} r $(( ${i} + 1 )) y"
      stack[i+4]="$(( ${job[2]} - 1 )) ${job[0]} ${job[1]} r $(( ${i} + 1 )) z"
    fi
  else
    if [ ${job[4]} -eq -1 ]; then
      echo ${job[3]}
      break
    else
      replace ${job[4]} ${job[5]} ${job[3]}
    fi
  fi
done

これで処理が速くなったか試してみます。
まず、通常の再帰版

$ time sh tarai02.sh 8 4 0 2>/dev/null
8

real    0m7.462s
user    0m4.598s
sys     0m2.849s

通常版は7.5秒くらいでした。次に今回のスタック版

$ time sh tarai03.sh 8 4 0 2>/dev/null
8

real    0m22.137s
user    0m14.284s
sys     0m7.808s

22秒? あれ?

次回、竹内関数のキャッシュと遅延評価をお楽しみに。

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
ユーザーは見つかりませんでした