再帰呼び出しで$c_{m,n}$を求める過程で,一度求めた$c_{i,j}$の値をメモリに保存しておき,再び必要になった時は再帰呼び出しを行わず,以前求めて保存してあった$c_{i,j}$の値を再利用し,処理を効率化することをメモ化(memoization)と呼ぶ.問題3-2で作ったプログラムにメモ化を導入し,メモ化により再帰関数の呼び出し回数が削減されることを確認したい.問題3-2のプログラムを,以下の仕様を満たすプログラムに改変し,メモ化を導入した再帰関数で編集距離を求めるとともに,メモ化の有り・無しのそれぞれの場合において再帰関数の呼び出し回数を計測せよ.

さらに,/opt/local/enshu/data/strings.txtを標準入力にリダイレクトしてこのプログラムを動かし,$m \times n$と再帰呼び出し回数の関係を,メモ化の有無を区別してグラフにプロットせよ.また,メモ化の有無によって呼び出し回数がどのようになるか考察すること.なお,グラフの作成にはgnuplotを使うとよい.

参考: /opt/local/enshu/data/strings.txtを標準入力にリダイレクトし,標準エラー出力だけをカレントディレクトリのcalls.txtというファイルに保存する方法

(./a.out < /opt/local/enshu/data/strings.txt > /dev/null) >& calls.txt

注意: 再帰関数の呼び出し方法は実装によって異なるため,投稿システムでは正しいかどうか検証しない.このため,再帰関数の呼び出し回数の妥当性を面接で確認することとする.

実行例

# eat ate
> 2
>> 3,3,9,94,28
# see seen
> 1
>> 3,4,12,193,37
# joti jobutu
> 3
>> 4,6,24,1933,73

#は標準入力,>は標準出力,>>は標準エラー出力を表す.