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

Question

Я пробовал разные коллекции в Scala для суммирования его элементов, и они намного медленнее, чем Java суммирует свои массивы (с циклом for).Есть ли способ для Scala быть таким же быстрым, как Java-массивы?

Я слышал, что в Scala 2.8 массивы будут такими же, как в Java, но на практике они намного медленнее

Answer 1

Индексирование по массивам в цикле while в Scala происходит так же быстро, как и в Java. (Цикл for в Scala не является низкоуровневой конструкцией 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

Answer 2

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

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

val sumOfValues = values.sum

Answer 3

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

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

Answer 4

Правильный 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 - функциональный язык.

Answer 5

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

В тех случаях, когда накладные расходы на итерацию являются критическими, вы можете явно получить итератор (или поддерживать целочисленный индекс для индексированных последовательных структур, таких как 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.

Answer 6

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

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

, в этом случае предпочтительнее будет заполнение foldLeft с Long

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

РЕДАКТИРОВАТЬ: Long можно использовать с начала:

scala> Array(2147483647L,2147483647L).sum
res1: Long = 4294967294