¿Cuál es la forma más rápida de sumar una colección en Scala

Question

He intentado diferentes colecciones en Scala para sumar sus elementos y son mucho más lentos que Java suma sus matrices (con for ciclo). ¿Hay alguna manera de que Scala sea tan rápido como las matrices de Java?

He oído que en Scala 2.8 matrices serán iguales que en java, pero son mucho más lentos en la práctica

Answer 1

La indexación en matrices en un ciclo while es tan rápida en Scala como en Java. (Scala de bucle "for" no es la construcción de bajo nivel que Java es, por lo que no va a funcionar de la manera deseada.)

Así, si en Java que ver

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

en Scala que debiera escriba

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

y si realiza los puntos de referencia adecuadamente, no encontrará diferencia en la velocidad.

Si tiene iteradores de todos modos, entonces Scala es tan rápido como Java en la mayoría de las cosas. Por ejemplo, si usted tiene un ArrayList de dobles y en Java que añadirlos usando

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

después en Scala podrás aproximadamente tan rápido - si se utiliza una estructura de datos equivalente como ArrayBuffer - con

arraybuffer.foreach(sum += _) 

y no demasiado lejos de la marca con cualquiera de

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

Tenga en cuenta, sin embargo, que hay una penalización a la mezcla de construcciones de alto nivel y de bajo nivel. Por ejemplo, si decide comenzar con una matriz pero luego utiliza "foreach" en ella en lugar de indexarla, Scala debe envolverla en una colección (ArrayOps en 2.8) para que funcione, y con frecuencia tendrá que marcar los primitivos también.

De todos modos, para las pruebas de referencia, estas dos funciones son tus amigos:

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) } 

Por ejemplo:

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

Scala 2,8 Array son matrices JVM/Java y como tales tienen idénticas características de rendimiento. Pero eso significa que no pueden tener métodos adicionales que los unifiquen con el resto de las colecciones de Scala. Para proporcionar la ilusión de que las matrices tienen estos métodos, existen conversiones implícitas a las clases contenedoras que agregan esas capacidades. Si no tiene cuidado, incurrirá en una sobrecarga excesiva usando esas características.

En aquellos casos en overhead iteración es crítica, se puede obtener de forma explícita un iterador (o mantener un índice entero, para estructuras secuenciales indexadas como Array u otro IndexedSeq) y utilizar un bucle while, que es una construcción de nivel de lenguaje que no necesita operar en funciones (literales u otros) pero puede compilar bloques de código en línea.

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

Dicho código se ejecutará esencialmente tan rápido como una contraparte de Java.

Answer 3

Es muy difícil explicar por qué un cierto código no se ha demostrado un rendimiento inferior que ningún otro código que no haya mostrado en algún punto de referencia que no haya mostrado.

Puede que le interese this question y su respuesta aceptada, por un lado. Pero el código JVM de evaluación comparativa es difícil, porque el JIT optimizará el código de maneras que son difíciles de predecir (razón por la cual JIT supera la optimización tradicional en tiempo de compilación).

Answer 4

La Scala adecuado o funcional fue de hacer esto sería:

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

Salida este enlace para la explicación completa de la sintaxis: http://www.codecommit.com/blog/scala/quick-explanation-of-scalas-syntax

Dudo que esto sería más rápido que hacerlo de la forma descrita en las otras respuestas, pero no lo he probado, así que no estoy seguro. En mi opinión, esta es la forma correcta de hacerlo, ya que Scala es un lenguaje funcional.

Answer 5

Ahora puede simplemente usar sum.

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

val sumOfValues = values.sum 

Answer 6

El tiempo no es la única preocupación. Con sum es posible encontrar un problema de desbordamiento:

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

en este caso, la siembra foldLeft con un Long es preferible

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