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

У меня есть программа 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?


clojure reduce lazy-sequences fibonacci take
person alt    schedule 06.04.2016    source источник

Ответы (2)


arrow_upward
7
arrow_downward

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

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

Если вы измеряете второй случай с 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.

person Piotrek Bzdyl    schedule 06.04.2016
comment
Меня смущает твой ответ. Метод -1 был медленным с самого начала. Как вам удалось заставить его работать на вашем компьютере за 8,5 мсек? Просто более быстрая машина? - person alt; 06.04.2016
comment
Наверное. Вы пробовали запустить второй тест с dorun? Какие результаты вы получили? - person Piotrek Bzdyl; 06.04.2016
comment
ETA: добавление доруна возвращает его на 90 мсек. - person alt; 06.04.2016
comment
попробуйте этот и посмотрите, насколько быстро он работает: gist.github.com/anonymous/475ed4cdcbff303117b733dac4046d - person alt; 06.04.2016
comment
Этот на моей машине работает ‹5 мсек. - person alt; 06.04.2016
comment
РЕДАКТИРОВАТЬ: у меня была опечатка. На моей машине, если я использую dorun, снова потребуется ~ 90 мсек. Спасибо за разъяснения! Но почему лень намного медленнее, чем суть, которую я опубликовал? Я новичок в clojure: зачем мне использовать ленивую последовательность, если она в 20 раз медленнее, чем loop? - person alt; 06.04.2016
comment
lazy-seq (или нетерпеливый seq вместо простого looping) добавляет накладные расходы на перенос всех ваших чисел в структуру данных вместо использования простых чисел. lazy-seq полезно, если вы хотите иметь абстрактный способ создания элементов последовательности, но вы не знаете, сколько из них вам понадобится. Он также является составным (в отличие от вашего sum-of-even-fibonaccis-below-3, который просто умеет вычислять сумму n чисел Фибоначчи). Последовательность Фибоначчи может использоваться во многих различных сценариях: вы можете take только первые n элементы, drop первые n элементы, filter только even? элементы и т. Д. - person Piotrek Bzdyl; 06.04.2016

arrow_upward
-1
arrow_downward

Комментарий

Вы можете реорганизовать свои функции - и дать им более подходящие имена - таким образом:

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

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

person Thumbnail    schedule 06.04.2016