当前位置：文江博客话题详情

使用 map/reduce 在 Clojure 中实现斐波那契

发布于 2024-10-06 06:57:23 字数 105 浏览 7 评论 0原文

是否可以使用reduce在Clojure中高效地实现斐波那契数列？ “累加器”包含什么？

我想它必须是懒惰的。很明显如何使用递归或循环/递归来做到这一点。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

天荒地未老 2024-10-13 06:57:23

您可以使用一对连续的斐波那契值作为累加器，如下所示：

(reduce 
  (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
  [0 1]                       ; initial pair of fibonnaci numbers
  (range 10))                 ; a seq to specify how many iterations you want

=> [55 89]

由于创建了大量中间对并使用多余的范围序列来驱动正确的迭代次数，这并不是特别有效，但它是 O( n) 从算法的角度来看（即与高效迭代解决方案相同，并且比朴素递归解决方案好得多）。

You could use a pair of successive fibonacci values as the accumulator, as follows:

(reduce 
  (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
  [0 1]                       ; initial pair of fibonnaci numbers
  (range 10))                 ; a seq to specify how many iterations you want

=> [55 89]

This is not particularly efficient due to the creation of lots of intermediate pairs and use of the superfluous range sequence to drive the right number of iterations, but it is O(n) from an algorithmic perspective (i.e. the same as the efficient iterative solution, and much better than the naive recursive one).

回复收藏 0 原文

∝单色的世界 2024-10-13 06:57:23

不使用map/reduce，但迭代也可以避免递归。

(defn iter [[x y]]
  (vector y (+ x y)))

(nth (iterate iter [0 1]) 10000)

在 Intel 2.4 Ghz 上这需要 21 毫秒

。在同一台机器上，reduce 需要 61 毫秒。不知道为什么迭代速度更快。

   (time (reduce 
     (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
     [0 1]                       ; initial pair of fibonnaci numbers
     (range 10000)))

Not using map/reduce, but iterate can avoid recursion too.

(defn iter [[x y]]
  (vector y (+ x y)))

(nth (iterate iter [0 1]) 10000)

This takes 21ms on an Intel 2.4 Ghz

On the same machine, reduce takes 61msec. Not sure why iterate is faster.

   (time (reduce 
     (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
     [0 1]                       ; initial pair of fibonnaci numbers
     (range 10000)))

回复收藏 0 原文

~没有更多了~