2

Clojure は私が Lisp の世界に足を踏み入れた最初の試みです。数値を整数乗する単純な再帰関数を試すことにしました。十分に単純です。

(defmulti pow #(compare %2 0))
(defmethod pow 0 [a n] 1)
(defmethod pow 1 [a n] (* a (pow a (dec n))))
(defmethod pow -1 [a n] (/ 1 (pow a (* -1 n))))

整数の累乗のみを渡すとうまく機能します。しかし、それを使用して十分な大きさの累乗に上げると、(予想どおり) スタック オーバーフローが発生します。

問題は、関数が終了する前に再帰がどの程度深いかを正確に知るにはどうすればよいかということです。再帰の深さを大まかに把握する 1 つの方法は、次のようにすることです。

(defn max-depth [n] 
    (try
        (max-depth (inc n))
    (catch StackOverflowError err (do
        (printf "%s at %d\n" err n)
        n)
)))

(Clojure は私にとって Lisp への最初の試みなので、コードを読みやすくする方法がよくわかりません。) このコードは、スタックがオーバーフローするまで無限に再帰し、その後、爆発する前に行われた再帰の回数を返します。これは、私がどれだけの深さまで行くことが許されているかの概算図を私に与えるだけです.このアプローチには多くの問題があります.

私ができるもう1つのことは、例外をキャッチして自分でスタックを巻き戻そうとすることです...しかし、例外から必要な情報を取得する方法が実際にはわかりません。http://docs.oracle.com/javase/6/docs/api/java/lang/StackOverflowError.htmlで StackOverflowError の javadoc を見ると、有望に見えるメソッドがいくつか見られますが、できる限りうまくいきませんでした。見る。

エラーがキャッチしたスタックオーバーフローである (count (.getStackTrace エラー)) を実行しようとしましたが、「状況によってはスタックフレームが省略される可能性がある」ため、結果はわずか 1024 でした。それでうまくいきませんでした。

私が考えることができる唯一の他のことは、連続して大きな指数に対して pow を実行することです.関数が他の関数を呼び出す場合、2 つの答えは同じではありません)。

Javaでそれを行う方法もわかりませんが、もしあれば、その答えもおそらく役立つでしょう。

何か案は？ありがとう、 -- スコット

4

2 に答える 2

2

私はそれ(.getStackTrace error)があなたの最善の策だと思っていました - なぜそれがうまくいかないと思いますか?

単純な関数のスタックを吹き飛ばす前の 1024 の再帰の深さは、私が期待することについて聞こえます。

単一の Clojure 関数が複数の JVM メソッド呼び出しに変換されることが多いため、実際の JVM スタックの深さは、再帰変数よりもかなり深くなる可能性があることに注意してくださいn。スタック トレースから に変換したい場合はn、マルチメソッドへの再帰呼び出しがスタック トレースに現れる回数を数える必要があるでしょう。

于 2013-06-02T09:30:09.017 に答える
0

したがって、私は実際にあなたの質問に答えるつもりはありません.コールスタックの深さをデバッグしようとすることは、この問題を解決するための間違った方法だと思うからです. 代わりに、Clojure での再帰へのより効果的なアプローチを提案します。これは、コール スタックを吹き飛ばす危険を冒しません。

重要な概念は「末尾呼び出しの除去」です。これは基本的に、関数 F が再帰関数であり、関数 F が最後に自分自身を呼び出す場合、それを最適化できることを意味します。F の n 番目の再帰呼び出しでは、F の n+1 番目の再帰呼び出しを呼び出し、その値を F の n-1 番目の呼び出しに返すことが最後に行われるため、n 番目の呼び出しに関連するすべてのスタック データを上書きできます。 F を呼び出し、n+1 番目の呼び出しでその値を n-1 番目の呼び出しに直接返すようにします。したがって、これは基本的に、スタックに数百または数千ではなく、1 つの場所だけが必要であることを意味します。

JVM は、関数呼び出しのこの最適化をネイティブにサポートしていません。それ以外の場合、例はおそらく機能します。代わりに、Clojure は recur 演算子を提供します。これは、スタックを増やすのではなく、現在のループまたは関数呼び出しを再利用します。これを使用して、関数を次のように書き直します (簡単にするために、負の指数のサポートを省略しました)。

user=> (defn pow
  #_=>   ([base exp] (pow base exp base)) ; default the accumulator argument to the base of the power
  #_=>   ([base exp acc] (if (= exp 1)
  #_=>                         acc ; base case - return the accumulated power
  #_=>                         (recur base (dec exp) (* base acc))))) ; recur, decrementing the power
#'user/pow
user=> 

user=> (pow 1 10000000) ; stack not blown
1
user=> (pow 2 10)
1024

参照: http://clojure.org/functional_programming#Functional%20Programming--Recursive%20Loopingおよびhttp://en.wikipedia.org/wiki/Tail_call

もちろん、この pow の実装は再帰の例にすぎません。これを読んでいる人は、実際の作業では代わりに Math/pow を使用する必要があります。

user=> (time (Math/pow 1 10000000))
"Elapsed time: 0.166723 msecs"
1.0
user=> (time (pow 1 10000000))
"Elapsed time: 2991.321703 msecs"
1
user=> (time (pow 2 1000))

ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1388)
user=> (time (Math/pow 2 1000))
"Elapsed time: 0.069109 msecs"
1.0715086071862673E301
于 2013-06-06T00:23:11.437 に答える