Scala domanda prestazioni

Question

Nel article written by Daniel Korzekwa, ha detto che la performance del seguente codice:

list.map(e => e*2).filter(e => e>10) 

è molto peggiore rispetto alla soluzione iterativa scritto utilizzando Java.

Qualcuno può spiegare perché? E qual è la migliore soluzione per tale codice in Scala (spero che non sia una versione iterativa di Java che è scalata)?

Answer 1

La ragione che particolare codice è lento è perché sta lavorando su primitive, ma sta usando operazioni generiche, per cui i primitivi devono essere inscatolato. (Questo potrebbe essere migliorato se List e i suoi antenati fossero specializzati.) Questo probabilmente rallenterà le cose di un fattore 5 o giù di lì.

Inoltre, dal punto di vista algoritmico, tali operazioni sono alquanto costose, perché si crea un'intera lista e quindi si crea una lista completamente nuova che allontana alcuni componenti della lista intermedia. Se lo facessi in un colpo solo, staresti meglio. Si potrebbe fare qualcosa di simile:

list collect (case e if (e*2>10) => e*2) 

ma cosa succede se il calcolo e*2 è molto costoso? Poi si potrebbe

(List[Int]() /: list)((ls,e) => { val x = e*2; if (x>10) x :: ls else ls } 

solo che questa sembrerebbe all'indietro. (Si potrebbe invertire se necessario, ma ciò richiede la creazione di un nuovo elenco, che di nuovo non è l'algoritmo ideale.)

Naturalmente, si ha lo stesso tipo di problemi algoritmici in Java se si utilizza un singolo lista collegata - la tua nuova lista finirà all'indietro, oppure dovrai crearla due volte, prima in senso inverso e poi in avanti, oppure devi costruirla con ricorsione (non-coda) (che è facile in Scala, ma sconsigliabile per questo genere di cose in entrambe le lingue dato che esaurirai la pila), o devi creare una lista mutabile e poi fingere dopo che non è mutabile. (Che, per inciso, si può fare in Scala anche - vedi mutable.LinkedList.)

Answer 2

Fondamentalmente sta attraversando una lista due volte. Una volta per moltiplicare ogni elemento con due. E poi un'altra volta per filtrare i risultati.

Pensatelo come uno mentre il ciclo produce un LinkedList con i risultati intermedi. E poi un altro ciclo che applica il filtro per produrre i risultati finali.

Questo dovrebbe essere più veloce:

list.view.map(e => e * 2).filter(e => e > 10).force 

Answer 3

Rex Kerr afferma giustamente il problema principale: Funzionamento a liste immutabili, il pezzo dichiarato di codice crea liste intermedi in memoria. Si noti che questo non è necessariamente più lento del codice Java equivalente; non usi mai solo le strutture dati immutabili in Java.

Wilfried Springer ha una bella soluzione idomatica di Scala. Usando view, non vengono create copie (manipolate) dell'intero elenco.

Si noti che l'utilizzo della vista potrebbe non essere sempre l'ideale. Ad esempio, se la prima chiamata è filter che si prevede di eliminare la maggior parte dell'elenco, potrebbe essere utile creare la versione più breve in modo esplicito e utilizzare view solo successivamente per migliorare la località di memoria per le iterazioni successive.

Answer 4

L'approccio Scala è molto più astratto e generico.Pertanto è difficile ottimizzare ogni singolo caso.

Potrei immaginare che il compilatore JIT HotSpot possa applicare stream e fusion al codice in futuro se vede che i risultati immediati non vengono utilizzati.

Inoltre, il codice Java fa molto di più.

Se si desidera realmente effettuare la mutazione su una struttura dati, prendere in considerazione transform. Sembra un po 'come map ma non crea una nuova collezione, e. g .:

val array = Array(1,2,3,4,5,6,7,8,9,10).transform(_ * 2) 
// array is now WrappedArray(2, 4, 6, 8, 10, 12, 14, 16, 18, 20) 

Spero davvero che si aggiungeranno alcune operazioni aggiuntive in-place ioni il futuro ...

Answer 5

Per evitare l'attraversamento della lista due volte, penso che la sintassi for è una buona opzione qui:

val list2 = for(v <- list1; e = v * 2; if e > 10) yield e 

Answer 6

La soluzione si trova principalmente con JVM. Sebbene Scala abbia una soluzione alternativa nella figura di @specialization, ciò aumenta enormemente le dimensioni di qualsiasi classe specializzata e risolve solo metà del problema, mentre l'altra metà è la creazione di oggetti temporanei.

La JVM in realtà fa un buon lavoro ottimizzandone un sacco, o le prestazioni sarebbero ancora più terribili, ma Java non richiede l'ottimizzazione di Scala, quindi JVM non le fornisce. Mi aspetto che cambi in una certa misura con l'introduzione di SAM non-real-closures in Java.

Ma, alla fine, si tratta di bilanciare i bisogni. Lo stesso ciclo while che Java e Scala eseguono molto più velocemente dell'equivalente della funzione di Scala può essere eseguito più velocemente in C. Tuttavia, nonostante ciò che ci dicono i microbenchmark, le persone usano Java.

Answer 7

List.filter (e => e * 2> 10) .map (e => e * 2)

Questo tentativo riduce primo elenco. Quindi il secondo attraversamento è su meno elementi.