Почему уменьшение этой ленивой последовательности замедляет эту программу Clojure 20x?

Question

У меня есть программа Clojure, которая возвращает сумму ленивой последовательности чисел Фибоначчей even ниже n:

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

Это не очень эффективное. Но если я не уменьшить последовательность и просто возвращает список значений (0 2 8 34 144...) он может выполнять свою работу 20x быстрее:

(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 так дорого этой ленивой последовательности Фибоначчи, и как я могу ускорить это без отказа от идиоматического Clojure?

Answer 1

Разница во времени выполнения - результат ленивости. В sum-of-even-fibonaccis-below-2 вы создаете только ленивый ряд чисел Фибоначчи, который не реализован (dotimes только вызывает sum-of-even-fibonaccis-below-2, чтобы создать ленивую последовательность, но не оценивает все ее содержимое). Поэтому на самом деле ваше второе выражение time не возвращает список значений, а ленивый seq, который будет создавать его элементы только тогда, когда вы их попросите.

Чтобы принудительно реализовать ленивую последовательность, вы можете использовать dorun, если вам не нужно сохранять ее как значение или doall, если вы хотите получить реализованный seq (будьте осторожны с inifinite seqs).

Если вы измеряете второй случай с sum-of-even-fibonaccis-below-2, обернутым в dorun, вы получите время, сравнимое с 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" 

Я также заметил, что вы определили свою fib функцию с defndefn внутри другого. Вы не должны этого делать, так как defn всегда будет определять функцию на верхнем уровне в вашем пространстве имен. Так что ваш код должен выглядеть следующим образом:

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

Если вы хотите определить локально контекстную функцию вы можете взглянуть на letfn.

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

Это легче понять и, следовательно, чтобы ответить.