なぜシェルスクリプトではメモ化再帰を使ってフィボナッチ数を求めることができないのか？

はじめに

この記事は最終的にシェルスクリプトでメモ化再帰を使ってフィボナッチ数を求めるコードを提示しますが、この記事の趣旨は他の言語と同じようなコードではシェルスクリプトでメモ化再帰ができない理由とそれを回避するためのテクニックを紹介することです。再帰を使わない実装や awk や bc 等のシェルスクリプト以外のコマンドを使って実装する話はこの記事の対象外です。またフィボナッチ数やメモ化再帰そのものについては詳しく解説しないので他のサイトなどで調べてください。

JavaScript による実装

参考として JavaScript でフィボナッチ数を求めるコードを提示します。

まずはメモ化を行わない通常の再帰を使ったコードです。私の環境では 45 番目 のフィボナッチ数 1134903170 を求めるのにおよそ 10 秒ぐらいかかりました。（ちなみに以下のコードは n = 0 を考慮していません。）

function fib(n) {
  if (n < 3) return 1;
  return fib(n - 1) + fib(n - 2);
}

console.log(fib(45))

これをメモ化（要するに計算済みの値をメモリにキャッシュしておいて再利用すること）を使って実装すると 0.4 秒で結果を求めることができ計算処理を高速化することが出来ます。

const memo = [null, 1, 1];
function fib(n) {
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1) + fib(n - 2);
  return memo[n];
}

console.log(fib(45))

これと同じことをシェルスクリプトでやろうという話です。

シェルスクリプトによる実装

シェルスクリプトの戻り値（終了ステータス）は 0 〜 255 の範囲しか返すことが出来ないので求めたフィボナッチ数を返すことが出来ません。そのため標準出力を使って値を返すのが定番パターンです。

メモ化を行わないコードです。遅いので 15 番目のフィボナッチ数 610 に変更しています。JavaScript 版より少し見づらいと思いますがやっている処理自体は変わりません。実行時間は 16 秒程度でした。

fib() {
 [ "$1" -lt 3 ] && echo 1 && return 0
 echo $(( $( fib $(($1 - 1)) ) + $( fib $(($1 - 2)) ) ))
}

fib 15

メモ化してるのに速くならない

このコードは遅いので JavaScript と同様にメモ化を行います。私は普段 POSIX シェル準拠のコードを書いているのですが、今回はわかりやすさ優先で配列が使える bash コードです。配列部分を eval を使って memo_N（N は任意の数字）変数に入れるようにすれば POSIX シェルにも対応させることが出来ます。

memo=(0 1 1)
fib() {
  [ "${memo[$1]}" ] && echo "${memo[$1]}" && return 0
  memo[$1]=$(( $( fib $(($1 - 1)) ) + $( fib $(($1 - 2)) ) ))
  echo "${memo[$1]}"
}

fib 15

実行時間は・・・およそ 16 秒で全く変わりません。つまりメモ化が行われていないということです。さてなぜなのでしょうか？

原因はサブシェル

メモ化が出来ない原因は $( fib $(($1 - 1)) ) の部分です。fib 関数は標準出力に計算した結果を出力しますが、それを受け取るためにコマンド置換$(...) を使用します。コマンド置換はサブシェルを生成します。サブシェルは現在のシェルと同じ環境を作り出すもので、多くのシェルの実装では現在のプロセスをコピー（fork）した子プロセスとして実装されています。つまりコマンド置換の中で呼び出した fib 関数は別プロセスで実行されているのです。別プロセスでメモ化（メモリに計算結果をキャッシュ）したとしても、残念ながら呼び出し元のプロセスには反映されません。またサブシェルが使用する fork はとても遅い処理なので、コマンド置換を多用することはシェルスクリプトを遅くする原因にもなります。

「出力引数パターン」で解決

これを解決するには「出力引数パターン」を使用します。「出力引数パターン」というのはシェルスクリプト用語ではなく MATLAB や他の言語を参考に私がつけた名前で（他にもっといい名前があれば教えて下さい） read コマンドや getopts コマンドと同じように引数で指定した変数に戻り値を返すテクニックです。つまり fib ret 15 という形で関数を呼び出し、戻り値を ret 変数に返します。以下はその実装例です。（以下の例では POSIX シェルでも使える eval を用いて実装していますが、eval はサブシェルよりはかなりマシとはいえ遅い処理の一つです。bash 等ではeval を使わない方法もあります。）

memo=(0 1 1)
fib() {
  [ "${memo[$2]}" ] && eval "$1=\${memo[\$2]}" && return 0
  fib i $(($2 - 1))
  fib j $(($2 - 2))
  memo[$2]=$((i + j))
  eval "$1=\${memo[\$2]}"
}

fib ret 45
echo "$ret"

書き換えたコードを実行してみるとすぐに分かると思いますが 0.1 秒未満で結果が返ってきます。おっと上のコードをよく見て下さい。JavaScript と同じく 45 番目に戻していますよ。JavaScript では 0.4 秒でした。なんとシェルスクリプトの方が速く結果が返ってくるようになってしまいました。まあこれは bash の処理速度が速いわけではなく node 起動のオーバーヘッドが大きいってだけなのですが。処理速度自体は JavaScript の方が速いです。

まとめ

サブシェルというのは他の言語にはないシェルスクリプト特有の概念です。その動きを正しく理解していないと予想していないところでハマったり大幅なパフォーマンス低下を引き起こします。シェルスクリプトを使う上で正しく知っておかなければいけないことの一つです。