なぜこのレイジーシーケンスを減らすと、このClojureプログラム20xが遅くなるのですか？

Question

私はn以下evenフィボナッチ数の遅延シーケンスの合計を返すClojureのプログラムを持っている：

(defn sum-of-even-fibonaccis-below-1 [n] 
    (defn fib [a b] (lazy-seq (cons a (fib b (+ b a))))) 
    (reduce + (take-while (partial >= n) (take-nth 3 (fib 0 1))))) 

(time (dotimes [n 1000] (sum-of-even-fibonaccis-below-1 4000000))) ;; => "Elapsed time: 98.764msecs" 

それは非常に効率的ではありません。

(defn sum-of-even-fibonaccis-below-2 [n] 
    (defn fib [a b] (lazy-seq (cons a (fib b (+ b a))))) 
    (take-while (partial >= n) (take-nth 3 (fib 0 1)))) 


(time (dotimes [n 1000] (sum-of-even-fibonaccis-below-2 4000000))) ;; => "Elapsed time: 5.145msecs" 

はなぜ、この怠惰なフィボナッチ数列にreduceとても高価であり、そして私はどのように高速化することができます：私はシーケンスを削減し、単に値(0 2 8 34 144...)のリストが返されない場合しかし、それは20倍の高速化にその仕事をすることができますそれは慣用的なClojureを放棄しないで？

Answer 1

実行時間の違いは、怠惰の結果です。 sum-of-even-fibonaccis-below-2では、フィボナッチ数の怠惰なseqしか生成されません（dotimesは、遅延シーケンスを作成するのにsum-of-even-fibonaccis-below-2を呼び出すだけですが、すべての内容は評価しません）。したがって実際には、2番目のtime式は値のリストを返すのではなく、要求したときにのみその要素を生成する遅延セグメントです。

遅延シーケンスを実現するには、を値として保存する必要がない場合はdoallを使用し、実現seqを取得する場合は（inifinite seqsに注意してください）。

sum-of-even-fibonaccis-below-2がdorunにラップされた2番目のケースを測定すると、sum-of-even-fibonaccis-below-1に匹敵する時間が得られます。私のマシンから

結果：

(time (dotimes [n 1000] (sum-of-even-fibonaccis-below-1 4000000))) ;; => "Elapsed time: 8.544193 msecs" 

(time (dotimes [n 1000] (dorun (sum-of-even-fibonaccis-below-2 4000000)))) ;; => "Elapsed time: 8.012638 msecs" 

私はまた、あなたが別のdefn内部defnであなたのfib機能を定義したことに気づきました。 defnは常に名前空間のトップレベルで関数を定義するので、これを行うべきではありません。あなたはletfnを見てみることができますローカルスコープの関数を定義したい場合は

(defn fib [a b] (lazy-seq (cons a (fib b (+ b a))))) 

(defn sum-of-even-fibonaccis-below-1 [n] 
    (reduce + (take-while (partial >= n) (take-nth 3 (fib 0 1))))) 

(defn sum-of-even-fibonaccis-below-2 [n] 
    (take-while (partial >= n) (take-nth 3 (fib 0 1)))) 

：だからあなたのコードは次のようになります。

Answer 2

コメント

あなたの機能をリファクタリングすることができます - そしてそれらをより良い名前を与える - ので：

(defn fib [a b] (lazy-seq (cons a (fib b (+ b a))))) 

(defn even-fibonaccis-below [n] 
    (take-while (partial >= n) (take-nth 3 (fib 0 1)))) 

(defn sum-of-even-fibonaccis-below [n] 
    (reduce + (even-fibonaccis-below n))) 

これは理解するので、お答えすることが容易です。