3

使用功能构造（map、foreach、flatMap 等）循环集合是否更好？作为一个虚拟问题，考虑我有一个字符串列表，我想按不同的标准过滤字符串，然后映射它们以获得一些值。考虑下面的代码：

val x1 = list.filter(criteria1).map(do_something)
val x2 = list.filter(criteria2).map(do_something)

假设我有 5 个这样不同的过滤条件，那么我将在列表（可能很大）上循环 10 次（一次使用过滤器，一次使用地图）。

但是，我可以将所有这些组合成一个 for 循环，并在一次迭代中返回/填充 5 个新列表，然后在每个列表上映射总共 6 个循环而不是 10 个。

for(i<- 0 to list.length-1){
  if(criteria1) //filter
  if(criteria2) //filter
}

这段代码可能会迫使我使用可变列表，但严格从性能的角度来看，在这种情况下使用函数构造是否有意义。哪种方法更好？

注意：上面的代码/问题只是作为一个例子，我希望它能解释我所指的那种情况

4

6 回答 6

7

如果您正在寻找过滤和映射，您可以使用withFilter而不是filter，这会使过滤器变得懒惰，这样您就不会多次遍历列表。for-表达式withFilter用于提高效率。您还可以查看views，它为其他操作提供了类似的惰性。

从你想要做什么的问题中并不完全清楚，但我认为你想根据不同的过滤器和映射操作输出 5 个新列表。如果性能至关重要，那么使用您建议的循环和可变构建器是一种合理的方法，这就是编程了多少收集方法（检查源代码）。不知道为什么你认为你需要过滤成 5 个列表，然后遍历每个列表来进行映射 - 为什么不通过将函数应用于每个元素来在构建新列表的同时进行映射? 例如

  def split[T](xs: Seq[T])(ops: (T => Boolean, T => T)*): Seq[Seq[T]] = {
    val (filters, maps) = ops.unzip
    val buffers = IndexedSeq.fill(ops.size)(ListBuffer.empty[T])
    for {
      x <- xs
      i <- buffers.indices
      if filters(i)(x)
    } buffers(i) += maps(i)(x)  
    buffers.map(_.toSeq)  // return to immutable-land
  }

  // demo: 
  val res = split(1 to 10)(
    (_ < 5, _ * 100),     // multiply everything under 5 by 100
    (_ % 2 == 1, 0 - _),  // negate all odd numbers
    (_ % 3 == 0, _ + 5)   // add 5 to numbers divisible by 3
  )

  println(res) 
  //Vector(List(100, 200, 300, 400), List(-1, -3, -5, -7, -9), List(8, 11, 14))

我不认为有一个内置的方法可以做（我认为）你想做的事情。请注意，如果您使用递归，您可以定义一个没有可变状态的构建器方法，但这曾经是局部可变状态更简洁/可读的地方。

您的问题实际上归结为性能，并且很容易过早优化。如果您确实遇到真正的性能问题，我建议您仅执行上述操作。如果惯用/简单不够好，那么您可能可以调整一些东西以优化您的特定用例。归根结底，您可能想做的所有事情都没有内置的优化方法。

于 2012-08-23T07:01:53.180 回答
5

你也可以这样做：

val x1 = for(x <- list if criteria1) yield do_something(x)

编译器实际上将其转换为val x1 = list.filter(criteria1).map(do_something)就像您在上面所做的那样。for理解只是一些很好的语法糖，它可以让你将一些序列上的复杂操作聚合变成更易读的东西。您可以阅读Odersky 书中的相关章节以获取更多详细信息。

回到你的问题。如果您尝试根据不同的过滤器和地图生成 5 个不同的列表，也许您应该创建一个列表列表。您可以使用for推导来遍历每对转换函数的输入列表。

这将帮助您使代码更简单一些，但实际上并不会降低问题的算法复杂性（即您仍然需要对列表进行 5 次迭代）。

在这种情况下，我认为你是对的，使用命令式循环会更有效率。推荐的用于构建列表的数据结构是，ListBuffer因为您可以在恒定时间内将元素添加到任一端 - 然后当您完成构建列表时，您可以将其转换为不可变列表（也是在恒定时间内）。在 Odersky 的书中还有一小节介绍了如何使用 ListBuffer 。这是我的做法：

import scala.collection.mutable.ListBuffer

val b1 = new ListBuffer[Int]
val b2 = new ListBuffer[Int]
// ... b3, b4, b5

for (x <- list) {
  val y = do_something(x)
  if (criteria1(x)) b1 += y
  if (criteria2(x)) b2 += y
  // ... criteria3, criteria4, criteria5
}

val x1 = b1.toList
val x2 = b2.toList
// ... x3, x4, x5

由于它使用的是可变的，ListBuffer所以这段代码不再很“纯”——但它可能值得为长列表加速，因为你不再需要遍历整个列表 5 次。

在这种情况下，我真的不会说一种方法比另一种方法好得多。该ListBuffer方式使用突变，速度更快，但可能会使代码更难维护。相比之下，功能更强大的版本只是使用对原始列表的重复调用filter，map这可能更易于阅读（当然假设读者熟悉惯用的 Scala）并且更易于维护，但运行速度可能会慢一些。选择实际上取决于您的目标是什么。

于 2012-08-23T04:14:56.257 回答
1

我不太确定多次浏览列表会变慢。您必须m从长度列表中构建长度k列表n。所以你必须m*k对每n一种方式进行比较。如果它更慢，那么它是由某个恒定因素决定的。我不知道这个因素是小是大。

如果您真的想一次性完成，那绝对是可能的。列表上的任何操作都可以通过折叠一次完成。它可能有点复杂，并强调了为什么它可能不会更快。这当然更难阅读：

val cs = List((criteria1, f1), (criteria2, f2))
val xs = list.foldRight(cs.map(_ => Nil)) { (x, rs) =>
  (cs zip rs).map { case ((p, f), r) =>
    if (p(x)) f(x) :: r else r
  }
}

您可能需要比我在这里给出的更多的类型注释。

你也可以在这里利用懒惰来发挥你的优势：

list.toStream.filter(???).map(???)

这将遍历列表零次。在您请求结果的元素之前，这些元素实际上不会被过滤和映射。显然使用您的真实代码而不是???.

于 2012-08-23T04:17:16.813 回答
1

迭代部分真的与你的表现相关吗？在大多数情况下，我对此表示怀疑。只有在这种情况下，单个 for 循环才会更快。

但是，如果您必须使用可变数据类型，那么现在在多核上运行会变得更加困难，并且如果这确实是在性能关键的情况下，那么在 8-800 核上运行它所获得的收益将是巨大的。保存一个循环迭代几乎没有什么好处。

请注意，for 理解通常对于性能来说并不是最优的，因为它可能必须创建大量的闭包实例。

于 2012-08-23T04:24:48.580 回答
1

如果我理解正确，您想根据不同的标准从一个列表中创建多个列表。我觉得groupBy可以达到目的~

val grouped = list.groupBy{ item => {
    val c1 = criteria1(item)
    val c2 = criteria2(item)
    if (c1 && c2) 12
    else if (c1) 1
    else if (c2) 2
    else 0
}}
val excluded0 = grouped - 0
val result = excluded0 mapValues do_something
val x1 = result(1) ++ result(12)
val x2 = result(2) ++ result(12)

view正如 Apocalisp 提到的，您还可以通过使用和force喜欢来利用懒惰：

val grouped = list.view.groupBy{ ...
...
val x1 = (result(1) ++ result(12)).force
于 2012-08-23T04:34:19.247 回答
0

正如之前没有提到的，您可能还想考虑 和 的组合filter可以map通过collect. 所以你可以做这样的事情：

list.collect {
  case x if criteria1(x) => ...
  case x if criteria2(x) => ....
  case _ => ...
}

但是，对于同时满足criteria1和的列表元素，这是一个稍微改变的语义criteria2。与 Chris 提议的类似，您可以创建 first case x if criteria1(x) && criteria2(x)，但这当然不会扩展到多个此类标准。

不过，您不清楚的一点是，您是要构建实际结果列表（如在第一个示例中），还是仅执行一些副作用（如在第二个示例中）。后者也可以通过稍微不同的方法来实现，如以下示例所示：

// A list of criteria and corresponding effects
val criteriaEffects = List( 
  ( (x : Int) => x == 0, (x : Int) => { println("Effect 1: " + x) } ),
  ( (x : Int) => x == 1, (x : Int) => { println("Effect 2: " + x) } ) )

// now run through your values list
List(0,1,2).map(x => criteriaEffects.map( p => if (p._1(x)) p._2(x) ) )
于 2012-08-23T05:43:53.113 回答