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

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...) он может делать свою работу в 20 раз быстрее:

(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 функция с defn внутри другого defn, Вы не должны делать это как 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)))

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