Scala：在一次迭代中进行过滤和映射的最佳方法

Question

我是新手Scala，正在尝试找出过滤和映射集合的最佳方法。这里有一个玩具示例来解释我的问题。 方法一： 这很糟糕，因为我要两次迭代列表，并在每次迭代中计算相同的值。

val N = 5
val nums = 0 until 10
val sqNumsLargerThanN = nums filter { x: Int => (x * x) > N } map { x: Int => (x * x).toString }

方法2：这个方法稍微好一些，但我仍需要计算(x * x)两次。

val N = 5
val nums = 0 until 10
val sqNumsLargerThanN = nums collect { case x: Int if (x * x) > N => (x * x).toString }

那么，有没有可能在不重复计算的情况下只遍历一次集合来计算这个值呢？

- Can Bal

Answer 1

可以使用 foldRight

。

nums.foldRight(List.empty[Int]) {
  case (i, is) =>
    val s = i * i
    if (s > N) s :: is else is
  }

一个 foldLeft 也可以实现类似的目标，但结果列表将是反向排序的（由于 foldLeft 的结合性）。另外，如果您想尝试 Scalaz。

import scalaz.std.list._
import scalaz.syntax.foldable._

nums.foldMap { i =>
  val s = i * i
  if (s > N) List(s) else List()
}

- adelbertc

---

请注意，默认的 foldRight 在列表长度超过一千个元素时会导致堆栈溢出。此外，Scalaz 版本与 flatMap 相比没有任何优势。 - Rex Kerr

Answer 2

传统的做法是使用iterator（如果可以）或者view（如果iterator不可用）。这并没有完全避免两次遍历，但它确实避免了创建一个完整大小的中间集合。然后你可以先map，之后再进行filter，如果需要的话再次map：

xs.iterator.map(x => x*x).filter(_ > N).map(_.toString)

这种方法的优点是非常易于阅读，而且由于没有中间集合，效率也相当高。

如果您之所以询问是因为这是性能瓶颈，那么通常的答案是编写一个尾递归函数或使用旧的 while 循环方法。例如，在您的情况下。

def sumSqBigN(xs: Array[Int], N: Int): Array[String] = {
  val ysb = Array.newBuilder[String]
  def inner(start: Int): Array[String] = {
    if (start >= xs.length) ysb.result
    else {
      val sq = xs(start) * xs(start)
      if (sq > N) ysb += sq.toString
      inner(start + 1)
    }
  }
  inner(0)
}

您也可以在inner中传递参数，而不是使用外部构建器（对于总和特别有用）。

- Rex Kerr

---

嗨 Rex - 你说的"它并没有完全避免两次遍历"是什么意思？ - sourcedelica

@sourcedelica - 每个迭代器在遍历列表时，也必然会遍历先前的迭代器。因此，它们都以锁步方式遍历，但如果您进行映射，然后过滤，然后再映射，实际上会嵌套三层next/hasNext调用。 - Rex Kerr

Answer 3

我还没有确认这是否真的是单次通行，但是：

  val sqNumsLargerThanN = nums flatMap { x =>
    val square = x * x
    if (square > N) Some(x) else None
  }

- triggerNZ

---

我想问一下，对于 Option Layer 中每个元素进行包装的加载，是否比两次计算 x * x 要轻微？可以忽略 Option 对象创建的成本吗？（我从 C++ 刚学 Scala。） - Chen OT

直接回答你的问题，选项分配并不是免费的。但它很便宜。多年来，JVM GC 在循环中分配和收集小对象方面已经变得非常出色。因此，虽然不是免费的，但这几乎从不是我开始优化的地方。 - triggerNZ

此外，我应该提到，在函数式编程世界中，尽管这是一个有趣的难题，但试图最小化对集合的遍历次数通常不是获得性能的最佳方式。这些问题在C/C++世界中很常见，在JVM上则不太常见。话虽如此，假设您的集合非常庞大，比如8GB。那么您确实只想遍历一次，并且我会坚持使用collect或懒惰集合的使用。双重乘法将被JIT优化掉。 - triggerNZ

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Rex Kerr

是的，感觉像作弊一样 :) - triggerNZ

Answer 4

一个非常简单的方法只执行一次乘法运算。它还是懒惰的，因此只在需要时才执行代码。

nums.view.map(x=>x*x).withFilter(x => x> N).map(_.toString)

点击这里查看filter和withFilter之间的区别。

- marios

---

这非常有趣。在你提供的线程中，有一个评论：“我认为你不应该自己使用withFilter（除了在for表达式中隐含使用）”。不使用withFilter有什么原因吗？ - Can Bal

我只在想要创建一个新的集合以供后续使用时才使用filter。如果我只是想要将过滤器作为管道操作的中间步骤，我总是使用withFilter。 - marios

Answer 5

您可以使用collect函数，该函数对集合中每个定义了的值应用部分函数。您的示例可重写为以下内容：

val sqNumsLargerThanN = nums collect {
    case (x: Int) if (x * x) > N => (x * x).toString
}

- Gavin Schulz

---

为什么有人给这个答案点了踩？collect似乎是一种非常惯用的方法。 - Michael Zajac

这难道不就是和我的“方法2”完全一样吗？ - Can Bal

是的，它与上面的第二种方法相同，并且根据“收集”的定义，这种方法对我来说似乎非常合理；它确切地说明了它所做的事情。这并不意味着上面阐述的其他方法更好或更差。 - Nirmalya

Answer 6

考虑以下内容，

  for (x <- 0 until 10; v = x*x if v > N) yield v.toString

这段代码使用 flatMap 对范围进行展开，然后使用 (惰性的) withFilter 对计算出的平方值进行筛选，最终返回一个包含过滤结果的集合。需要注意的是，这里只需要进行一次迭代和一次平方计算（除了创建范围之外）。

- elm

Answer 7

你可以使用 flatMap。

val sqNumsLargerThanN = nums flatMap { x =>
  val square = x * x
  if (square > N) Some(square.toString) else None
}

或者使用 Scalaz，

import scalaz.Scalaz._

val sqNumsLargerThanN = nums flatMap { x =>
  val square = x * x
  (square > N).option(square.toString)
}

---

这个解决了如何在一次迭代中完成此操作的问题。当处理流式数据时，比如使用迭代器时，这非常有用。

然而...如果你想要最快的实现方式，那么这不是最佳选择。事实上，我怀疑你会使用可变的ArrayList和while循环。但只有在进行性能分析之后，你才能确定。无论如何，这是另一个问题。

- Paul Draper

Answer 8

使用for推导式会起作用：

val sqNumsLargerThanN = for {x <- nums if x*x > N } yield (x*x).toString

另外，我不确定，但我认为scala编译器在map前进行过滤时很聪明，并且只会尽可能做一次遍历。

- Ramón J Romero y Vigil

Answer 9

我也是初学者，我按照以下步骤实现了它

 for(y<-(num.map(x=>x*x)) if y>5 ) { println(y)}

- gauri