Почему фильтр перед foldLeft работает медленно в Scala?

Я написал ответ на первый вопрос Project Euler:

Добавьте все натуральные числа меньше тысячи, кратные 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

Источник

5 ответов

Решение

Проблема, как говорили другие, заключается в том, что filter создает новую коллекцию. Альтернатива withFilter нет, но это не имеет foldLeft, Кроме того, используя .view, .iterator или же .toStream Все они избегали бы создания новой коллекции различными способами, но все они здесь медленнее, чем первый использованный вами метод, который я сначала считал несколько странным.

Но тогда... Видите, 1 until 1000 это Range, чей размер на самом деле очень маленький, потому что он не хранит каждый элемент. Также, Range"s 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"
}
Источник

Попробуйте сначала сделать коллекцию ленивой, так

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

вместо

(1 until 1000).filter...

Это должно избежать затрат на создание промежуточной коллекции. Вы также можете получить лучшую производительность от использования sum вместо foldLeft(0)(_ + _)всегда возможно, что у некоторого типа коллекции может быть более эффективный способ суммирования чисел. Если нет, это все еще чище и более декларативно...

Источник

Просматривая код, выглядит filter действительно строит новый Seq, на котором foldLeft называется. Второй пропускает этот бит. Это не так много памяти, хотя это не может не помочь, но что отфильтрованная коллекция никогда не создается вообще. Вся эта работа никогда не делается.

Диапазон использования TranversableLike.filter, который выглядит так:

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

Я думаю, что это += в строке 4 это разница. Фильтрация в foldLeft устраняет это.

Источник

Теперь проблема в том, можете ли вы придумать еще более эффективный способ? Не то, чтобы ваше решение было слишком медленным в этом случае, но насколько хорошо оно масштабируется? Что если вместо 1000 это будет 1000000000? Существует решение, которое может вычислить последний случай так же быстро, как и первый.

Источник

filter создает совершенно новую последовательность, на которой затем foldLeft называется. Пытаться:

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

Это предотвратит указанный эффект, просто оборачивая оригинальную вещь. Обменявшись foldLeft с reduceLeft это только косметика (в данном случае).

Источник
Другие вопросы по тегам