迭代过程的流与尾递归

Question

这是我之前的问题的后续问题。

我知道我们可以使用streams来生成“pi”（和其他数字）、n-th fibonacci等的近似值。但是我怀疑streams是否可以 是执行此操作的正确方法。

主要缺点（据我所知）是内存消耗：例如 stream 将保留 i stream 的所有斐波那契数。 n 而我只需要斐波那契第 n 次。当然，我可以使用 drop 但它使解决方案变得更加复杂。尾递归看起来是更适合此类任务的方法。

你怎么认为？

Answer 1

如果需要快速行驶，请轻装上阵。这意味着；避免分配任何不必要的内存。如果您需要内存，请使用可用的快速集合。如果您知道需要多少内存；预分配。对于计算而言，分配绝对是性能杀手。你的代码可能看起来不再好看，但它会运行得很快。

但是，如果您正在使用 IO（磁盘、网络）或任何用户交互，那么分配就显得苍白无力了。那么最好将优先级从代码性能转移到可维护性。

Answer 2

使用迭代器。它不保留中间值。

Answer 3

如果您想要第 n 个斐波那契数并使用流作为临时数据结构（如果您不保存对先前计算的流元素的引用），那么您的算法将在恒定空间中运行。
以前计算的 Stream 元素（不再使用）将被垃圾收集。由于它们是在最年轻的一代中分配并立即收集的，因此几乎所有分配都可能在缓存中。

更新：

看来 Stream 的当前实现并不像它可能的那样节省空间，主要是因为它继承了 LinearSeqOptimized 特征的 apply 方法的实现，它定义为

def apply(n: Int): A = {
   val rest = drop(n)
   if (n < 0 || rest.isEmpty) throw new IndexOutOfBoundsException("" + n)
   rest.head
}

Reference to a head of a stream is hold here by this and prevents the stream from being gc'ed. So combination of drop and head methods (as in f.drop(100).head) may be better for situations where dropping intermediate results is feasible. (thanks to Sebastien Bocq for explaining this stuff on scala-user).