为什么减少这个懒惰的序列会减慢这个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这个懒惰的Fibonacci序列成本太高,如何在不放弃惯用的Clojure的情况下加快速度呢？

Answer 1

执行时间的差异是懒惰的结果.在sum-of-even-fibonaccis-below-2你只产生一个懒惰的斐波那契数字序列没有实现(dotimes只调用sum-of-even-fibonaccis-below-2创建一个懒惰的序列,但不评估其所有内容).所以实际上你的第二个time表达式不会返回一个值列表,而是一个懒惰的seq,它只会在你要求它们时产生它的元素.

要强制实现延迟序列,您可以使用,dorun如果您不需要将其保留为值,或者doall如果您想获得已实现的seq(请注意无限的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功能.您不应该这样做,因为它总是在命名空间的顶层定义函数.所以你的代码应该是这样的:defndefndefn

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