力技版が、妙に遅くなってしまう問題について、コメント欄で結城さんにアドバイスを貰いました。ありがとうございます。

興味深いですね…。

段数を1段ずつ増やして、スピードやスペースがどういう変化をするかグラフを描いてみると、原因の一端がわかるかもしれませんね。

（リニアに増えているのか、二乗なのか、指数的に増えているのかという意味）

階段クイズのつづき – 週記くらい%28BTS開発記%29のコメント欄

1段から40段までの時間とスペースをグラフ化してみました。

計測に使ったコードは、以下です。

(defun answer-1 (step-count)
(let ((way-count 0))
(labels ((rec (n)
(if (zerop n)
(incf way-count) ;reached.
(loop for i from 1 to 2
until (< n i)
do (rec (- n i))))))
(rec step-count)
way-count)))
(defun answer-2 (step-count)
(or (plusp step-count)
(error 'step-count-msut-plus-value))
(case step-count
(1 1)
(2 2)
(otherwise (+ (answer-2 (- step-count 2))
(answer-2 (- step-count 1))))))
(defun bench (fn n)
(loop for i from 1 to n
do
(format t "= ~d steps~%" i)
(time (funcall fn i))))
(print "-- start answer-1 --")
(bench 'answer-1 40)
(print "-- end --")
(print "-- start answer-2 --")
(bench 'answer-2 40)
(print "-- end --")

分析

計測してみましたが、分析ってどうすればいいのか良くわかりません

時間について

力技版は、30段を越えたあたりで、爆発的に増加していました。模範解答版は、33段あたりから増加しています。

スペースについて

スペースについては、力技版の方だけ、35段くらいから、異常な増加をしています。

結局

この爆発の原因は、何かを調べるには、同じくらいのところで変化が起こるものを探さなければならないです。

再帰の回数

力技版と模範解答版は共に再帰を行なっていて、条件的には力技版の方が末尾再帰の最適化を期待できるので、良いはずです。それでもこれだけ差が出てしまうということは、再帰自体の回数に問題があるのではないかと考えて、再帰呼び出しの回数をカウントしてみました。

これも思った程、差がありませんでした。(模範解答の2倍程度)

再帰回数のグラフの形は、かかった時間と同じようなグラフの形なので、時間がかかってしまう一因ではあると思いますが、力技版のスペースの問題は証明できません。

あとは、力技版の書き方に問題があるかもしれません。

あと、できることとしたら、

• labelsで再帰してることが原因？ → labelsを辞めて別の関数で再帰を行なうようにする
• letの環境を再帰毎にコピーしてることが原因 → letを辞めて、スペシャル変数でカウントする。
• お手上げ → 諦めてCommon LispのLingrで質問する。

仕事が忙しいこともあるので、ゆっくり、解析していこうと思います。