Qual è il modo più veloce per sommare una collezione in Scala

Question

Ho provato diverse raccolte in Scala per sommare i suoi elementi e sono molto più lenti di quanto Java sommi agli array (con ciclo for). C'è un modo per Scala di essere veloce quanto gli array Java?

Ho sentito dire che in Scala 2.8 array sarà uguale in Java, ma sono molto più lento in pratica

Answer 1

L'indicizzazione in array in un ciclo while è veloce sia in Scala che in Java. (Scala del ciclo "for" non è il costrutto di basso livello che Java è, in modo che non funziona nel modo desiderato.)

Così se in Java si vede

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

a Scala si dovrebbe scrivere

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

e se fate i vostri punti di riferimento in modo appropriato, troverete alcuna differenza in termini di velocità.

Se si hanno gli iteratori in ogni caso, quindi Scala è veloce come Java nella maggior parte delle cose. Ad esempio, se si dispone di un ArrayList di doppie e in Java si aggiunge utilizzando

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

poi a Scala sarai circa più veloce - se si utilizza una struttura di dati equivalente come ArrayBuffer - con

arraybuffer.foreach(sum += _) 

e non troppo lontano il marchio con uno dei

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

tenere a mente, però, che c'è un rigore per la miscelazione di alto livello e di basso livello costrutti. Ad esempio, se decidi di iniziare con un array ma di utilizzare "foreach" su di esso invece di indicizzarlo, Scala deve avvolgerlo in una raccolta (ArrayOps in 2.8) per farlo funzionare e spesso dovrà anche i primitivi.

In ogni caso, per il test di riferimento, queste due funzioni sono i tuoi amici:

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

Per esempio:

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 Arraysono array JVM/Java e come tali hanno caratteristiche di prestazioni identiche. Ma questo significa che non possono avere direttamente metodi extra che li uniscano con il resto delle collezioni Scala. Per fornire l'illusione che gli array abbiano questi metodi, ci sono conversioni implicite nelle classi wrapper che aggiungono tali capacità. Se non si presta attenzione, si verificheranno sovraccarichi eccessivi con tali funzioni.

Nei casi in cui iterazione sovraccarico è critica, è possibile ottenere in modo esplicito un iteratore (o mantenere un indice intero, per strutture sequenziali indicizzati come Array o altro IndexedSeq) e utilizzare un ciclo while, che è un costrutto di livello lingua non è necessario operare su funzioni (letterali o altro) ma è possibile compilare blocchi di codice in linea.

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

Tale codice verrà eseguito essenzialmente veloce come una controparte Java.

Answer 3

E 'molto difficile spiegare il motivo per cui un certo codice non è stato mostrato risultati peggiori di qualche altro codice che non hai mostrato in alcuni benchmark che non hai mostrato.

Potreste essere interessati a this question e la sua risposta accettata, per una cosa. Ma il benchmarking del codice JVM è difficile, perché la JIT ottimizzerà il codice in modi difficili da prevedere (ecco perché il JIT supera l'ottimizzazione tradizionale in fase di compilazione).

Answer 4

Lo scala adeguata o funzionale è stato quello di fare questo sarebbe:

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

controlla questo link per la spiegazione completa della sintassi: http://www.codecommit.com/blog/scala/quick-explanation-of-scalas-syntax

Dubito che questo sarebbe stato più veloce di farlo nei modi descritti nelle altre risposte ma non l'ho provato, quindi non ne sono sicuro. Secondo me questo è il modo corretto di farlo anche se Scala è un linguaggio funzionale.

Answer 5

Ora è possibile utilizzare semplicemente la somma.

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

val sumOfValues = values.sum 

Answer 6

Il tempismo non è l'unica preoccupazione. Con sum si potrebbe trovare un problema di overflow:

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

in questo caso semina foldLeft con un Long è preferibile

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