Clojure中seq返回函数与直接使用'seq'的'def'之间的区别

Question

新手Clojure问题。以下两种实现/表示斐波那契数列的方式有什么优缺点？（特别是，有没有任何东西完全排除其中一个作为坏主意的可能性。）

(ns clxp.fib
  (:gen-class))

; On the one hand, it seems more natural in code to have a function that
; returns 'a' Fibonacci sequence.
(defn fib-1
  "Returns an infinite sequence of Fibonnaci numbers."
  []
  (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

; > (take 10 (fib-1))
; (0 1 1 2 3 5 8 13 21 34)

; On the other hand, it seems more mathematically natural to define 'the'
; Fibonacci sequence once, and just refer to it.
(def fib-2
  "The infinite sequence of Fibonnaci numbers."
  (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

; > (take 10 fib-2)
; (0 1 1 2 3 5 8 13 21 34)

a) 定义无限序列的这两种方法各有利弊。需要注意的是，这个特定序列不需要提供任何参数，与例如“n”的倍数无限序列不同，后者需要使用第一种方法以指定“n”的值。

b) 有没有什么总体原因更倾向于其中一种实现方式？（内存消耗、作为参数时的适用性等）

- Paul

---

我会定义 fib-1，只是为了有它的存在，如果你决定需要一个不可垃圾回收实例，你可以通过 (def fib-2 (fib-1)) 来定义 fib-2。 - Dax Fohl

可能与此重复：https://dev59.com/MnE95IYBdhLWcg3wp_un - ClojureMostly

Answer 1

fib-2 是更优选的选择，如果需要多次查找其元素，因为在惰性序列中它们只需要被计算一次。

由于全局绑定，该序列不太可能被垃圾回收，因此如果您的程序需要遍历一百万个斐波那契数列来进行某些计算，尤其是如果不需要保存序列的头部，则在本地上下文中调用 fib-1 可以更好地提高空间性能。

- Leon Grapenthin

---

只是为了澄清一下。您的意思是fib-1可能更好，因为它不会保留比所需更长的序列（可能会节省内存，但需要重新计算不同调用fib-1的序列）。但是fib-2通过不进行垃圾回收来保存重新计算的开销（可能永远不会），这是正确的吗？ - Paul

这里我有点模糊。我曾认为序列中所有已计算的元素都会一直保留，直到整个序列被垃圾回收。但你似乎在说这是错误的。 - Paul

@Paul，这通常被称为“保留头部”，有些函数将在内存中保存整个序列，而其他函数只会保留它们当前使用的部分。doall和dorun是每种类型的示例。 - Daniel Compton

如果你正在迭代，通常不会保留头部。这意味着在一步之后，你将当前序列留给垃圾回收器，但继续使用当前序列的“rest”进行下一步。因此，每一步都放弃了序列的当前头元素。如果seq是惰性的，则头部是按需计算的，因此内存中所需的仅是当前元素。(由于分块序列的实现略有不同，但在概念上和性能期望上，这个解释是成立的) - Leon Grapenthin

谢谢解释。但是在变量fib-2的情况下，不会一直保留（全部）头部吗？否则，稍后使用fib-2时将没有最初的元素进行迭代？ - Paul

Answer 2

这取决于您的使用情况以及不必多次重新计算斐波那契序列的关键性。然而，根据我的下面的实验，当使用长序列时，使用def会出现问题。

如果您要引用大量元素，则需要注意头部保留，就像Leon所提到的那样。

可以如下图所示（这些是从Clojure编程中扩展出来的几个示例）：

(let [[t d] (split-with #(< % 10) (take 1e6 (fib-1)))]
  [(count d) (count t)])
=> OutOfMemoryError Java heap space

(let [[t d] (split-with #(< % 10) (take 1e6 (fib-1)))]
  [(count t) (count d)])
=> [7 999993]

注意，我不得不更改你的实现，使用初始向量[0 1N]来避免在获取大量斐波那契数列时出现算术异常整数溢出。

有趣的是，改为使用fib-2仍会导致OOM错误以保持头部情况，但非头部保持版本会中断：

(let [[t d] (split-with #(< % 10) (take 1e6 fib-2))]
  [(count t) (count d)])
=> [7 270036]

后一个数字应该是999993。

两种情况都发生OOM的原因如Clojure Programming所述：

由于t的最后一个引用出现在d的处理之前，因此没有保留对范围序列头的引用，也不会出现内存问题。

- Mark Fisher

---

很有趣。我原本预期会有性能特征上的差异，但没想到选择其中一种方式会导致结果在逻辑/计算方面产生任何差异！ - Paul

我还没有尝试弄清楚它出了什么问题，如果有人知道的话，那会很有趣。 - Mark Fisher

我无法使用 fib-2 重现无效结果。 - Leon Grapenthin

非常奇怪。即使对于fib-2，我的程序现在也会OOM（内存溢出），但是对于fib-1却不会，尽管我已经使用了更大的JVM堆栈。我认为这可能与环境有关，但是似乎使用函数可以减少内存问题。 - Mark Fisher

如果你想在内存中保存一百万个斐波那契数列，你需要大量的内存。请注意，增长是指数级的，而1e6附近的数字每个都有超过200k位数。对于仅依赖于较小样本的程序来说，这可能是一个不错的策略。 - Leon Grapenthin