为什么Scala中foldLeft前面的过滤器很慢？

Question

我写了第一个 Project Euler 问题的答案：

将所有 1000 以下并且是 3 或 5 的倍数的自然数相加。

我想到的第一件事是：

(1 until 1000).filter(i => (i % 3 == 0 || i % 5 == 0)).foldLeft(0)(_ + _)

但是它很慢（需要 125 毫秒），所以我重写了它，只是想到“另一种方式”与“更快的方法'

(1 until 1000).foldLeft(0){
    (total, x) =>
        x match {
            case i if (i % 3 == 0 || i % 5 ==0) => i + total // Add
            case _ => total //skip
        }
}

这要快得多（仅 2 毫秒）。为什么？我猜第二个版本仅使用 Range 生成器，并且没有以任何方式体现完全实现的集合，一次完成所有操作，既更快又占用更少的内存。我说得对吗？

这里是 IdeOne 上的代码： http://ideone.com/GbKlP

Answer 1

正如其他人所说，问题在于 filter 创建了一个新集合。替代的 withFilter 没有，但它没有 foldLeft。此外，使用 .view、.iterator 或 .toStream 都会避免以各种方式创建新集合，但它们在这里都比你使用的第一种方法，一开始我觉得有点奇怪。

但是，然后...看，1 到 1000 是一个 Range，它的大小实际上很小，因为它不存储每个元素。此外，Range 的 foreach 进行了极其优化，甚至是专门化，这是其他任何集合都没有的情况。由于 foldLeft 是作为 foreach 实现的，只要您继续使用 Range，您就可以享受其优化的方法。

(_: Range).foreach:

@inline final override def foreach[@specialized(Unit) U](f: Int => U) {
    if (length > 0) {
        val last = this.last
        var i = start
        while (i != last) {
            f(i)
            i += step
        }
        f(i)
    }
}

(_: Range).view.foreach

def foreach[U](f: A => U): Unit = 
    iterator.foreach(f)

(_: Range).view.iterator

override def iterator: Iterator[A] = new Elements(0, length)

protected class Elements(start: Int, end: Int) extends BufferedIterator[A] with Serializable {
  private var i = start

  def hasNext: Boolean = i < end

  def next: A = 
    if (i < end) {
      val x = self(i)
      i += 1
      x
    } else Iterator.empty.next

  def head = 
    if (i < end) self(i) else Iterator.empty.next

  /** $super
   *  '''Note:''' `drop` is overridden to enable fast searching in the middle of indexed sequences.
   */
  override def drop(n: Int): Iterator[A] =
    if (n > 0) new Elements(i + n, end) else this

  /** $super
   *  '''Note:''' `take` is overridden to be symmetric to `drop`.
   */
  override def take(n: Int): Iterator[A] =
    if (n <= 0) Iterator.empty.buffered
    else if (i + n < end) new Elements(i, i + n) 
    else this
}

(_: Range).view.iterator.foreach

def foreach[U](f: A =>  U) { while (hasNext) f(next()) }

当然，这甚至没有计算 view 和 foldLeft< 之间的 filter /代码>：

override def filter(p: A => Boolean): This = newFiltered(p).asInstanceOf[This]

protected def newFiltered(p: A => Boolean): Transformed[A] = new Filtered { val pred = p }

trait Filtered extends Transformed[A] {
  protected[this] val pred: A => Boolean 
  override def foreach[U](f: A => U) {
    for (x <- self)
      if (pred(x)) f(x)
  }
  override def stringPrefix = self.stringPrefix+"F"
}

Answer 2

首先尝试使集合变得惰性，所以

(1 until 1000).view.filter...

而不是

(1 until 1000).filter...

That 应该避免构建中间集合的成本。您还可能通过使用 sum 而不是 foldLeft(0)(_ + _) 获得更好的性能，某些集合类型总是可能有更有效的求和方法数字。如果没有，它仍然更干净、更具声明性......

Answer 3

查看代码，看起来 filter 确实构建了一个新的 Seq，在该 Seq 上调用了 foldLeft 。第二个跳过了这一点。与其说内存是有帮助的，不如说是过滤后的集合根本就没有被构建。所有这些工作都还没有完成。

Range 使用 TranversableLike.filter，它看起来像这样：

def filter(p: A => Boolean): Repr = {
  val b = newBuilder
  for (x <- this) 
    if (p(x)) b += x
  b.result
}

我认为区别在于第 4 行的 +=。 foldLeft 中的过滤消除了它。

Answer 4

filter 创建一个全新的序列，然后调用 foldLeft 。尝试：

(1 直到 1000).view.filter(i => (i % 3 == 0 || i % 5 == 0)).reduceLeft(_+_)

这将阻止所说的效果，只是包裹了原来的东西。将 foldLeft 与 reduceLeft 交换只是装饰性的（在本例中）。

Answer 5

现在的挑战是，你能想出一种更有效的方法吗？在这种情况下，并不是说您的解决方案太慢，而是它的扩展能力如何？如果不是 1000，而是 1000000000 呢？有一个解决方案可以像计算前者一样快速地计算后者。