Scala中的无限流

Question

假设我有一个函数，例如，旧的最爱

def factorial(n:Int) = (BigInt(1) /: (1 to n)) (_*_)

现在我想找出factorial(n)适合长整型的n的最大值。我能做到

(1 to 100) takeWhile (factorial(_) <= Long.MaxValue) last

这是可行的，但100是一个任意的大数字；我真正想要的是左侧的无限流，它会不断生成更高的数字，直到满足takeWhile条件。

我想出了一个

val s = Stream.continually(1).zipWithIndex.map(p => p._1 + p._2)

但是有没有更好的方法呢？

(我也知道我可以递归地得到一个解决方案，但这不是我想要的。)

Answer 1

Stream.from(1)

创建一个从1开始并以1递增的流。它都在API docs中。

Answer 2

使用迭代器的解决方案

您也可以使用Iterator而不是Stream。Stream保留所有计算值的引用。因此，如果您计划只访问每个值一次，迭代器是一种更有效的方法。不过，迭代器的缺点是它的可变性。

有一些很好的方法可以方便地创建在其companion object上定义的Iterator。

编辑

不幸的是，据我所知，没有短的(库支持的)方法来实现像这样的事情

Stream.from(1) takeWhile (factorial(_) <= Long.MaxValue) last

对于一定数量的元素，我采用drop(n: Int)或dropWhile方法来推进Iterator

Iterator.from(1).dropWhile( factorial(_) <= Long.MaxValue).next - 1

- 1可用于此特殊用途，但不是通用解决方案。但是使用pimp my library在Iterator上实现一个last方法应该没有问题。问题是取无限迭代器的最后一个元素可能是有问题的。因此，它应该作为集成takeWhile的lastWith方法来实现。

一种丑陋的解决方法是使用为Iterator实现的sliding

scala> Iterator.from(1).sliding(2).dropWhile(_.tail.head < 10).next.head
res12: Int = 9

Answer 3

正如@ziggystar指出的那样，Streams将先前计算的值列表保存在内存中，因此使用Iterator是一个很大的改进。

为了进一步改进答案，我认为“无限流”通常是基于预先计算的值来计算(或可以计算)的。如果是这样的话(在您的factorial流中肯定是这样)，我建议使用Iterator.iterate。

大致如下所示：

scala> val it = Iterator.iterate((1,BigInt(1))){case (i,f) => (i+1,f*(i+1))}
it: Iterator[(Int, scala.math.BigInt)] = non-empty iterator

然后，您可以执行以下操作：

scala> it.find(_._2 >= Long.MaxValue).map(_._1).get - 1
res0: Int = 22

或者使用@ziggystar sliding解决方案...

脑海中出现的另一个简单的例子是斐波那契数：

scala> val it = Iterator.iterate((1,1)){case (a,b) => (b,a+b)}.map(_._1)
it: Iterator[Int] = non-empty iterator

在这些情况下，你并不是每次都从头开始计算你的新元素，而是为每个新元素做O(1)的工作，这将进一步改善你的运行时间。