6

我想要一种方便的方法来生成一个Iterable，给定一个初始对象和一个从当前对象生成下一个对象的函数，它消耗 O(1) 内存（即，它不缓存旧结果；如果你想迭代一个第二次，必须再次应用该功能）。

似乎没有对此的库支持。在 Scala 2.8 中，该方法scala.collection.Iterable.iterate具有签名

def iterate [A] (start: A, len: Int)(f: (A) ⇒ A) : Iterable[A]

因此它要求您提前指定您感兴趣的迭代函数应用程序的数量，而我对文档的理解是Iterable.iterate实际上会立即计算所有这些值。另一方面，该方法scala.collection.Iterator.iterate具有签名

def iterate [T] (start: T)(f: (T) ⇒ T) : Iterator[T]

看起来不错，但我们只得到一个Iterator不能提供map,filter和朋友的所有便利的。

有没有方便的库方法来生产我想要的东西？

如果不，

有人可以建议这样做的“口语”Scala代码吗？

总而言之，给定一个初始 objecta: A和一个 function f: A => A，我想要一个TraversableLike（例如，可能是一个Iterable），它生成a, f(a), f(f(a)), ...并使用 O(1) 内存， withmap等filter函数，它们也返回 O(1) in记忆。

4

4 回答 4

10

Stream会做你想做的，只是不要抓住细胞；只迭代值。

Streams 固有地缓存他们计算的每个值，这是一个可悲的普遍误解。

如果你这样写：

val s1: Stream[Thing] = initialValue #:: «expression computing next value»

那么确实保留了流产生的每个值，但这不是必需的。如果你写：

def s2: Stream[Thing] = initialValue #:: «expression computing next value»

如果调用者只是迭代流的值但不记得 Stream 值本身（特别是它的任何 cons 单元格），则不会发生不需要的保留。当然，在这个公式中，每次调用都会Stream从一个固定的初始值开始创建一个新的。这不是必需的：

def s3(start: Thing): Stream[Thing] = start #:: «expression computing next value»

您必须注意的一件事是将 a 传递Stream给方法。这样做将捕获方法参数中传递的流的头部。解决此问题的一种方法是使用尾递归代码处理流。

于 2010-09-24T05:43:56.473 回答
3

Iterator.iterate带过滤器的演示：

object I {
  def main(args:Array[String]) {
    val mb = 1024 * 1024
    val gen = Iterator.iterate(new Array[Int](10 * mb)){arr => 
      val res = new Array[Int](10 * mb)
      arr.copyToArray(res)
      println("allocated 10mb")
      res(0) = arr(0) + 1 // store iteration count in first elem of new array
      res
    }
    // take 1 out of 100
    val gen2 = gen filter (arr => arr(0) % 100 == 0) 
    // print first 10 filtered
    gen2.take(10).foreach { arr => println("filtered " + arr(0)) } 
  }
}

（这在 REPL 中可能不起作用，因为 PRINT 步骤可能会干扰内存管理）

JAVA_OPTS="-Xmx128m" scala -cp classes I将显示过滤有效并且是惰性的。如果它不是在常量内存中完成，则会导致堆错误（因为它分配了类似 900*10mb 的东西）。

用于JAVA_OPTS="-Xmx128m -verbose:gc" scala -cp classes I查看垃圾收集事件。

于 2010-09-24T06:40:06.290 回答
2

迭代器正是您想要的。并且迭代器确实有 map、filter、takeWhile 和许多其他在内存中为 O(1) 的方法。我认为内存中没有另一种 O(1) 的集合类型。

于 2010-09-24T06:48:32.073 回答
1 
val it = new Iterable[Int] {
  def iterator = Iterator.iterate(0)(_+1)
  override
  def toString: String = "Infinite iterable"
}

不要在 REPL 上尝试它（除非将它嵌入到对象或类中），因为 REPL 会尝试打印它，它不会使用toString.

于 2010-09-24T17:13:00.497 回答