为什么减少这个惰性序列会使这个 Clojure 程序减慢 20 倍？
Why does reducing this lazy sequence slow down this Clojure program 20x?
我有一个 Clojure 程序，它 return 是 n 以下 even 斐波那契数列的惰性序列的总和：
(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"
效率不高。但是，如果我不减少序列，而只是 return 一个值列表 (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 的情况下加快它的速度？
执行时间的差异是懒惰的结果。在 sum-of-even-fibonaccis-below-2 中，您只生成一个未实现的斐波那契数列惰性序列（dotimes 仅调用 sum-of-even-fibonaccis-below-2 来创建一个惰性序列，但不会评估其所有内容）。所以实际上你的第二个 time 表达式不是 return 一个值列表，而是一个惰性序列，只有当你要求它们时才会产生它的元素。
要强制实现惰性序列，如果不需要将其保存为值，则可以使用 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"
我还注意到您在另一个 defn 中用 defn 定义了 fib 函数。您不应该这样做，因为 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。
评论
您可以重构您的函数 - 并给它们更好的名字 - 因此：
(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)))
这个更容易理解，因此更容易回答。
我有一个 Clojure 程序，它 return 是 n 以下 even 斐波那契数列的惰性序列的总和：
(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"
效率不高。但是，如果我不减少序列，而只是 return 一个值列表 (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 的情况下加快它的速度？
执行时间的差异是懒惰的结果。在 sum-of-even-fibonaccis-below-2 中，您只生成一个未实现的斐波那契数列惰性序列（dotimes 仅调用 sum-of-even-fibonaccis-below-2 来创建一个惰性序列，但不会评估其所有内容）。所以实际上你的第二个 time 表达式不是 return 一个值列表，而是一个惰性序列，只有当你要求它们时才会产生它的元素。
要强制实现惰性序列，如果不需要将其保存为值，则可以使用 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"
我还注意到您在另一个 defn 中用 defn 定义了 fib 函数。您不应该这样做，因为 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。
评论
您可以重构您的函数 - 并给它们更好的名字 - 因此：
(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)))
这个更容易理解，因此更容易回答。