3

我有一个 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 的情况下加快它的速度？

4

2 回答 2

7

执行时间的差异是懒惰的结果。在sum-of-even-fibonaccis-below-2您只生成一个未实现的 Fibonacci 数的惰性序列（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函数。你不应该这样做，因为总是在你的命名空间的顶层定义函数。所以你的代码应该是这样的：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.

于 2016-04-06T07:11:19.177 回答
-1

评论

你可以重构你的函数 - 并给他们更好的名字 - 因此：

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

这更容易理解，因此也更容易回答。

于 2016-04-06T15:50:24.353 回答