Каков самый быстрый способ суммирования коллекции в Scala

Ответ 1

Индексирование в массивы в цикле while так же быстро выполняется в Scala, как и в Java. (Scala "for" loop не является низкоуровневой конструкцией Java, поэтому она не будет работать так, как вы хотите.)

Таким образом, если в Java вы видите

for (int i=0 ; i < array.length ; i++) sum += array(i)

в Scala вам следует написать

var i=0
while (i < array.length) {
  sum += array(i)
  i += 1
}

и если вы выполните свои тесты соответствующим образом, вы не найдете никакой разницы в скорости.

Если у вас есть итераторы, то Scala так же быстро, как Java, в большинстве случаев. Например, если у вас есть ArrayList двойников и в Java вы добавляете их с помощью

for (double d : arraylist) { sum += d }

тогда в Scala вы будете примерно такими же быстрыми - если используете эквивалентную структуру данных, например ArrayBuffer - с

arraybuffer.foreach( sum += _ )

и не слишком далеко от знака с помощью

sum = (0 /: arraybuffer)(_ + _)
sum = arraybuffer.sum  // 2.8 only

Имейте в виду, что существует штраф за смешение конструкций высокого уровня и низкого уровня. Например, если вы решили начать с массива, но затем используйте вместо него "foreach" вместо индексации, Scala должен обернуть его в коллекцию (ArrayOps в 2.8), чтобы заставить ее работать, и часто также нужно будет прикрепить примитивы.

В любом случае, для тестового тестирования эти две функции - ваши друзья:

def time[F](f: => F) = {
  val t0 = System.nanoTime
  val ans = f
  printf("Elapsed: %.3f\n",1e-9*(System.nanoTime-t0))
  ans
}

def lots[F](n: Int, f: => F): F = if (n <= 1) f else { f; lots(n-1,f) }

Например:

val a = Array.tabulate(1000000)(_.toDouble)
val ab = new collection.mutable.ArrayBuffer[Double] ++ a
def adSum(ad: Array[Double]) = {
  var sum = 0.0
  var i = 0
  while (i<ad.length) { sum += ad(i); i += 1 }
  sum
}

// Mixed array + high-level; convenient, not so fast
scala> lots(3, time( lots(100,(0.0 /: a)(_ + _)) ) )
Elapsed: 2.434
Elapsed: 2.085
Elapsed: 2.081
res4: Double = 4.999995E11

// High-level container and operations, somewhat better
scala> lots(3, time( lots(100,(0.0 /: ab)(_ + _)) ) )    
Elapsed: 1.694
Elapsed: 1.679
Elapsed: 1.635
res5: Double = 4.999995E11

// High-level collection with simpler operation
scala> lots(3, time( lots(100,{var s=0.0;ab.foreach(s += _);s}) ) )
Elapsed: 1.171
Elapsed: 1.166
Elapsed: 1.162
res7: Double = 4.999995E11

// All low level operations with primitives, no boxing, fast!
scala> lots(3, time( lots(100,adSum(a)) ) )              
Elapsed: 0.185
Elapsed: 0.183
Elapsed: 0.186
res6: Double = 4.999995E11

Ответ 2

Теперь вы можете просто использовать сумму.

val values = Array.fill[Double](numValues)(0)

val sumOfValues = values.sum

Ответ 3

Очень сложно объяснить, почему какой-то код, который вы не показывали, хуже, чем какой-либо другой код, который вы не показывали в каком-то контрольном показателе, который вы не показывали.

Возможно, вас интересует этот вопрос и его принятый ответ, во-первых. Но сравнение JVM-кода сложно, потому что JIT будет оптимизировать код способами, которые трудно предсказать (вот почему JIT превосходит традиционную оптимизацию во время компиляции).

Ответ 4

Scala 2.8 Array являются массивами JVM/Java и, как таковые, имеют одинаковые характеристики производительности. Но это означает, что они не могут напрямую иметь дополнительные методы, которые объединяют их с остальными коллекциями Scala. Чтобы представить иллюзию, что массивы имеют эти методы, существуют неявные преобразования в классы-оболочки, которые добавляют эти возможности. Если вы не будете осторожны, вы будете нести чрезмерные издержки, используя эти функции.

В тех случаях, когда чрезмерные издержки итерации имеют решающее значение, вы можете явно получить итератор (или поддерживать индекс integer для индексированных последовательных структур, таких как Array или другой IndexedSeq), и использовать цикл while, который является языковой уровень, который не должен функционировать для функций (литералов или иначе), но может компилировать встроенные кодовые блоки.

val l1 = List(...) // or any Iteralbe
val i1 = l1.iterator
while (i1.hasNext) {
  val e = i1.next
  // Do stuff with e
}

Такой код будет выполняться практически так же быстро, как Java-копия.

Ответ 5

Правильный scala или функционал должен был сделать это:

val numbers = Array(1, 2, 3, 4, 5)
val sum = numbers.reduceLeft[Int](_+_)

Ознакомьтесь с этой ссылкой для полного объяснения синтаксиса: http://www.codecommit.com/blog/scala/quick-explanation-of-scalas-syntax

Я сомневаюсь, что это будет быстрее, чем делать это способами, описанными в других ответах, но я не проверял его, поэтому не уверен. На мой взгляд, это правильный способ сделать это, хотя scala является функциональным языком.

Ответ 6

Сроки - это не единственная проблема. С sum может возникнуть проблема с переполнением:

scala> Array(2147483647,2147483647).sum
res0: Int = -2

в этом случае предпочтительнее посев foldLeft с помощью Long

scala> Array(2147483647,2147483647).foldLeft(0L)(_+_)
res1: Long = 4294967294