2

プロジェクトオイラーの2番目の質問を解決しようとしています。以下のコードでスタック オーバーフローが発生するのはなぜですか? recur を使用しているため、すべての再帰呼び出しをスタックに格納するべきではありません。 

(defn sum
  [[a b]]
  [b (+ a b)])

(defn fib-r
  ([n] (fib-r n 0 [0 1]))
  ([n s [a b]]
     (if (= n 0)
       s
       (let [[c d] (sum [a b])
             e (if (even? c) c 0)
             f (+ s e)]
         (recur (dec n) f [c d])))))

(fib-r 4000000)
4

2 に答える 2

6

(スタック オーバーフローではなく) 整数オーバーフローが発生している

(defn fib-r                                                                                          
  ([n] (fib-r n 0N [0N 1N]))                                                                     
  ([n s [a b]]                                                                                     
     (if (= n 0N)                                                                            
       s                                                                            
       (let [[c d] (sum [a b])                                               
             e (if (even? c) c 0N)                               
             f (+ s e)]                             
         (recur (dec n) f [c d])))))
#'autotestbed.core/fib-r                                                                                               
autotestbed.core> (fib-r 40000)
1158997879999727672946417013062336891791160667328280503727448.... big number
于 2012-06-21T02:17:45.777 に答える
1

これは Clojure 1.3 で行われた大きな変更でした (詳細については、http://dev.clojure.org/display/doc/Enhanced+Primitive+Supportを参照してください)。プリミティブ型の自動昇格は自動的には行われません。

Arthur Ulfeldt が示唆するように、どこでも BigInts を使用する必要はありません。代わりに、auto-promoting plus operation を使用できます+'。

(defn sum [[a b]] [b (+' a b)])

これで十分です。

400 万のケースに関しては、はい、この計算は大規模です。fib-r次のように関数を変更できます。

(defn fib-r
  ([n] (fib-r n 0 [0 1]))
  ([n s [a b]]
     (if (and (< 0 n) (zero? (mod n 100000)))
       (println n))
     (if (= n 0) s
       (let [[c d] (sum [a b])
             e (if (even? c) c 0)
             f (+ s e)]
         (recur (dec n) f [c d])))))

これがどれだけ速いかを確認します。

于 2012-06-21T17:31:35.710 に答える