为什么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 until 1000是一个Range,其大小实际上非常小,因为它不存储每个元素.此外,Range的foreach非常优化,并且甚至是specialized,这不是任何其他集合的情况下.既然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()) }

当然,这甚至不计算filter中间view和foldLeft:

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...

这应该避免建立中间集合的成本.您也可以通过使用sum而不是获得更好的性能foldLeft(0)(_ + _),某些集合类型总是可能有更有效的方法来对数字求和.如果没有,它仍然更清洁,更具声明性......