Warum verlangsamt das Reduzieren dieser Lazy-Sequenz dieses Clojure-Programm 20x?

Question

Ich habe ein Clojure-Programm, das die Summe einer faulen Folge von even Fibonacci-Zahlen unter n zurück:

(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" 

Es ist nicht sehr effizient. Aber wenn ich nicht die Sequenz reduzieren und einfach eine Liste von den Werten (0 2 8 34 144...) kann es seine Aufgabe 20x schneller tun:

(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" 

Warum ist reduce so teuer zu dieser faulen Fibonacci-Folge, und wie kann ich beschleunigen es auf, ohne idiomatische Clojure zu verlassen?

Answer 1

Der Unterschied in der Ausführungszeit ist ein Ergebnis der Faulheit. In sum-of-even-fibonaccis-below-2 produzieren Sie nur eine faul Seq von Fibonacci-Nummern, die nicht realisiert wird (dotimes ruft nur sum-of-even-fibonaccis-below-2 auf, um eine Lazy-Sequenz zu erstellen, aber bewertet nicht den gesamten Inhalt). Ihr zweiter time Ausdruck gibt also keine Liste von Werten zurück, sondern einen faulen Seq, der seine Elemente nur dann erzeugt, wenn Sie danach gefragt werden.

Zur Realisierung der faulen Sequenz zwingen Sie dorun, wenn Sie es als Wert oder doall zu bewahren brauchen nicht verwenden können, wenn Sie die realisiert seq (Vorsicht mit inifinite ASTA) erhalten möchten.

Wenn Sie den zweiten Fall mit sum-of-even-fibonaccis-below-2 in dorun verpackt messen, erhalten Sie Zeit vergleichbar mit sum-of-even-fibonaccis-below-1.

Ergebnisse von meiner Maschine:

(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" 

Ich habe auch bemerkt, dass Sie mit defn innerhalb eines anderen defn Ihre fib Funktion definiert. Das sollten Sie nicht tun, da defn die Funktion immer auf der obersten Ebene in Ihrem Namensraum definiert. Also sollten Sie den Code wie folgt aussehen:

(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)))) 

Wenn Sie eine lokal scoped Funktion definieren möchten Sie einen Blick auf letfn nehmen.

Answer 2

Kommentar

Sie Ihre Funktionen Refactoring können - und ihnen bessere Namen geben - also:

(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))) 

Dies ist leichter zu verstehen und daher zu beantworten.