流find方法 - 让内存不足

有人可以帮助我，我可能会丢失在这里：流find方法 - 让内存不足

def isDivisibleByRange(n: Int, r: Range) = { 
    r.forall(n % _ == 0) 
} 

def from(n: Int): Stream[Int] = n #:: from(n + 1)

现在，下面给我的OOM：通过

val o = from(1).find(isDivisibleByRange(_, Range(2, 21)))

来源

2014-04-07 Biju Kunjummen

我的第一个猜测是，斯卡拉不够聪明，无法知道流中较早的条目不能再被访问并且可以被扔掉。也许这[问题]（http://stackoverflow.com/questions/16216774/）的答案将是有用的。 – dfan

它不够聪明。它很聪明。将它改为r.forall（n％_ == 0）为r.forall（_％n == 0） –

@dfan如果我正确地得到了它们，它们不应该被丢弃，这就是Stream和Iterator之间的区别。 –

让我们一步你的代码位：

from(1) // 2, 3, 4, 5, 6 ... 
isDivisibleByRange(1, Range(2, 21) 
Range(2, 21).forall(1 % _ == 0) // false 
isDivisibleByRange(2, Range(2, 21) 
Range(2, 21).forall(2 % _ == 0) // false 
isDivisibleByRange(3, Range(2, 21) 
Range(2, 21).forall(3 % _ == 0) // false 
... OOME

的第一个数字，以满足(2 to 21) mod == 0是232792560。因此，您在达到232792560之前获得OOME。

由于流只是一个懒惰的列表，你基本上创建了所有可能的正整数的列表，这需要你所有的内存。也许增加你的堆空间？请记住，在流容器周围有一些额外的分配，而不仅仅是int的4个字节，所以也许是-Xmx4G。

UPDATE

使用迭代的方法，你可以体面的时间和最小的内存（find上Range与一个Iterator实现）这样做：

Range(1, Int.MaxValue).find(r => Range(2, 21).forall(r1 => r % r1 == 0)) 
//Some(232792560)

来源

2014-04-07 01:26:25 Noah

没有什么不对您的代码，问题是与Stream.find，或在LinearSeqOptimized其中该方法是从继承：

override /*IterableLike*/ 
def find(p: A => Boolean): Option[A] = { 
    var these = this 
    while (!these.isEmpty) { 
    if (p(these.head)) return Some(these.head) 
    these = these.tail 
    } 
    None 
}

此方法已被编写为使用while循环运行，而不是使用递归。对于非惰性序列，这不会使用任何额外的内存，并且运行速度比递归解决方案快。不幸的是，Stream是懒惰的，当这种方法与大（特别是无限）序列一起使用时，会导致内存消耗的失控。发生这种情况是因为该方法始终将其指针保留在堆栈上，因此垃圾收集器从不收集开头或其他任何Stream。

这个问题可以通过固定写find的作品递归：

import annotation.tailrec 

@tailrec 
def betterFind[A](s: Stream[A], p: A => Boolean): Option[A] = { 
    if (s.isEmpty) 
    None 
    else if (p(s.head)) 
    Some(s.head) 
    else 
    betterFind(s.tail, p) 
}

在实践中，它可能是简单的使用Stream.iterator.find，而不是写你自己的方法。 Stream.iterator在Stream的元素上返回Iterator，即使对于无限数据流也是安全的。

来源

2014-04-07 05:58:55 wingedsubmariner

你为什么不贡献这种专业？ –

我正在考虑这样做。我可能会首先提交一个错误，Stream实际上不应该从'LinearSeqOptimized'继承。 – wingedsubmariner

谢谢@wingedsubmariner –

流find方法 - 让内存不足

回答

相关问题