12

我正在尝试阅读 Stuart Halloway 的《Programming Clojure》一书。这整个功能性的东西对我来说是非常新的。

我明白如何

(defn fibo[]
    (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

懒惰地生成斐波那契数列。我不明白为什么

(last (take 1000000 (fibo)))

工作，而

(nth (fibo) 1000000)

引发 OutOfMemoryError。有人可以解释一下这两种表达方式有何不同吗？(nth) 是否以某种方式抓住了序列的头部？

谢谢！

4

3 回答 3

4

我认为您正在谈论在google 小组中讨论的问题， Rich Hickey 提供了解决该问题的补丁。而后来出版的这本书并没有涵盖这个主题。

在clojure1.3 中，您的nth示例在fibo功能上略有改进。现在，由于 1.3 中的更改，我们应该明确标记M为使用任意精度，否则它属于throwIntOverflow.

(defn fibo[]
  (map first (iterate (fn [[a b]] [b (+ a b)]) [0M 1M])))

随着这些变化

(nth (fibo) 1000000)

成功（如果你有足够的内存）

于 2011-12-15T17:02:39.740 回答
1

您使用的是哪个 Clojure 版本？在 repl 上尝试（clojure-version）。对于 1.3.0 中的两个表达式，我得到相同的结果，即整数溢出。

为了

(defn fibo[]
    (map first (iterate (fn [[a b]] [b (+ a b)]) [(bigint 0) 1])))

我得到了两个表达式的正确结果（一个非常大的整数......）。

于 2011-12-15T17:00:05.427 回答
0

我认为您可能会达到您机器的特定内存限制，而不是功能上的真正差异。

查看https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java中 nth 的源代码， 看起来 nth 或 take 都没有保留头部。

但是，nth 使用从零开始的索引，而不是按项目编号计数。您的第 n 个代码选择序列的第 1000001 个元素（索引为 1000000 的元素）。您使用 take 编写的代码返回 1000000 个元素序列中的最后一个元素。那是索引为 999999 的项目。考虑到 fib 增长的速度，最后一个项目可能是压垮骆驼的那个。

另外，我正在检查 1.3.0 源。也许早期版本有不同的实现。为了让您的 fibo 在 1.3.0 中正常工作，您需要使用将数字提升为 bignums 的算术函数：

(defn fibo[]
    (map first (iterate (fn [[a b]] [b (+' a b)]) [0 1])))
于 2011-12-15T18:39:40.270 回答