scala Stream 转换和评估模型

Question

考虑以下列表转换：

List(1,2,3,4) map (_ + 10) filter (_ % 2 == 0) map (_ * 3)

按以下方式计算：

List(1, 2, 3, 4) map (_ + 10) filter (_ % 2 == 0) map (_ * 3)
List(11, 12, 13, 14) filter (_ % 2 == 0) map (_ * 3)
List(12, 14) map (_ * 3)
List(36, 42)

因此共有三遍，每遍创建一个新的列表结构。

那么，第一个问题：Stream可以帮助避免它吗？如果可以——如何避免？是否可以在不创建额外结构的情况下一次性完成所有评估？

下面的 Stream 评估模型是否正确：

Stream(1, ?) map (_ + 10) filter (_ % 2 == 0) map (_ * 3)
Stream(11, ?) filter (_ % 2 == 0) map (_ * 3)
// filter condition fail, evaluate the next element
Stream(2, ?) map (_ + 10) filter (_ % 2 == 0) map (_ * 3)
Stream(12, ?) filter (_ % 2 == 0) map (_ * 3)
Stream(12, ?) map (_ * 3)
Stream(36, ?)
// finish

如果是，则与 List 情况下创建的遍数和新 Stream 结构的数量相同。如果不是——那么第二个问题：什么是Stream评估模型，特别是这种类型的转换链？

Answer 1

据我所知，如果你总是遍历整个集合 Stream 对你没有帮助。它将创建与新 Streams 和 List.

相同的数字

如有错误请指正，我的理解如下：

Stream 是一个惰性结构，所以当你这样做时：

val result = Stream(1, ?) map (_ + 10) filter (_ % 2 == 0) map (_ * 3)

结果是链接到先前转换结果的另一个流。因此，如果使用 foreach（或例如 mkString）

强制评估

result.foreach(println)

对于每次迭代，都会对上述链进行评估以获取当前项。

但是，如果将过滤器替换为 withFilter，则可以减少 1 次通过。然后使用 map 函数应用过滤器。

List(1,2,3,4) map (_ + 10) withFilter (_ % 2 == 0) map (_ * 3)

您可以使用 flatMap 将其减少到一次：

List(1,2,3,4) flatMap { x =>
  val y = x + 10
  if (y % 2 == 0) Some(y * 3) else None
}

Answer 2

不，您无法使用 Stream 来避免它。但是你确实可以通过使用方法 collect 来避免它，并且你应该保持每次在 filter 之后使用 map 的想法，你可能需要一个 collect。这是代码：

scala> def time(n: Int)(call : => Unit): Long = {
     |   val start = System.currentTimeMillis
     |   var cnt = n
     |   while(cnt > 0) {
     |     cnt -= 1
     |     call
     |   }
     |   System.currentTimeMillis - start
     | }
time: (n: Int)(call: => Unit)Long

scala> val xs = List.fill(10000)((math.random * 100).toInt)
xs: List[Int] = List(37, 86, 74, 1, ...)
scala> val ys = Stream(xs :_*)
ys: scala.collection.immutable.Stream[Int] = Stream(37, ?)

scala> time(10000){ xs map (_+10) filter (_%2 == 0) map (_*3) }
res0: Long = 7182

//Note call force to evaluation of the whole stream.
scala> time(10000){ ys map (_+10) filter (_%2 == 0) map (_*3) force } 
res1: Long = 17408

scala> time(10000){ xs.view map (_+10) filter (_%2 == 0) map (_*3) force }
res2: Long = 6322

scala> time(10000){ xs collect { case x if (x+10)%2 == 0 => (x+10)*3 } }
res3: Long = 2339

Answer 3

避免中间集合的一种方法是使用 view.

List(1,2,3,4).view map (_ + 10) filter (_ % 2 == 0) map (_ * 3)

它不会避免 every 中间，但它可能很有用。 This page 有很多信息，值得花时间。

Answer 4

Scala 可以通过多种方式过滤和转换 collection。

首先你的例子：

List(1,2,3,4) map (_ + 10) filter (_ % 2 == 0) map (_ * 3)

可以优化：

List(1,2,3,4) filter (_ % 2 == 0) map (v => (v+10)*3)

或者，可以使用折叠：

List(1,2,3,4).foldLeft(List[Int]()){ case (a,b) if b % 2 == 0 => a ++ List((b+10)*3) case (a,b) => a }

或者，也许 for-expression:

for( v <- List(1,2,3,4); w=v+10 if w % 2 == 0 ) yield w*3

或者，也许是最容易理解的，collection:

List(1,2,3,4).collect{ case v if v % 2 == 0 => (v+10)*3 }

但是为了解决您关于 Streams 的问题；是的，可以使用流对于大的 collection 来说，通常很早就找到了想要的东西，a Stream是个不错的选择：

def myStream( s:Stream[Int] ): Stream[Int] = 
  ((s.head+10)*3) #:: myStream(s.tail.filter( _ % 2 == 0 ))

myStream(Stream.from(2)).take(2).toList  // An infinitely long list yields
                                         //   36 & 42 where the 3rd element
                                         //   has not been processed yet

对于这个 Stream 示例，过滤器仅在需要时应用于下一个元素，而不是整个列表——好事，否则它永远不会停止:)

scala Stream 转换和评估模型

scala Stream transformation and evaluation model

scala

stream

lazy-evaluation

lazy-sequences