2010-07-25 24 views
7

Sono nuovo di Scala e stavo leggendo solo Scala By Example. Nel capitolo 2, l'autore ha 2 diverse versioni di Quicksort.Scala Performance: imperativo vs stile funzionale

uno in stile imperativo:

def sort(xs: Array[Int]) { 
    def swap(i: Int, j: Int) { 
     val t = xs(i); xs(i) = xs(j); xs(j) = t 
    } 
    def sort1(l: Int, r: Int) { 
     val pivot = xs((l + r)/2) 
     var i = l; var j = r 
     while (i <= j) { 
      while (xs(i) < pivot) i += 1 
      while (xs(j) > pivot) j -= 1 
      if (i <= j) { 
       swap(i, j) 
       i += 1 
       j -= 1 
      } 
     } 
     if (l < j) sort1(l, j) 
     if (j < r) sort1(i, r) 
    } 
    sort1(0, xs.length - 1) 
} 

Uno è stile funzionale:

def sort(xs: Array[Int]): Array[Int] = { 
    if (xs.length <= 1) xs 
    else { 
    val pivot = xs(xs.length/2) 
    Array.concat(
     sort(xs filter (pivot >)), 
      xs filter (pivot ==), 
     sort(xs filter (pivot <))) 
    } 
} 

Il vantaggio evidente lo stile funzionale ha più stile imperativo è concisione. Ma per quanto riguarda le prestazioni? Dal momento che usa la ricorsione, paghiamo la penalizzazione delle prestazioni proprio come facciamo in altre lingue imperative come la C? Oppure, essendo Scala un linguaggio ibrido, il "modo di Scala" (funzionale) è preferito, quindi più efficiente.

Nota: l'autore ha menzionato lo stile funzionale che utilizza più memoria.

+2

possibile duplicato di [La programmazione funzionale scala è più lenta della codifica tradizionale?] (Http://stackoverflow.com/questions/2794823/is-scala-functional-programming-slower-than-traditional-coding) – missingfaktor

+2

"Conciso" non è lo stesso di "leggibile". Prova: [il linguaggio di programmazione J] (http://en.wikipedia.org/wiki/J_ (programming_language)) –

+1

Penso di capire ora che l'autore di Scala per esempio sta cercando di mostrare un altro modo per risolvere il problema che è molto più conciso. Per riassumere: si programma il più conciso possibile in tutte le parti del codice, in modo da ottenere la massima concisione, produttività. Quindi esegui la tua applicazione e, se è troppo lenta, configurala e ottimizza le parti del collo di bottiglia. – sivabudh

risposta

11

Dipende. Se guardi nelle fonti di Scala, spesso c'è uno stile imperativo usato "sotto il cofano" per essere performante - ma in molti casi esattamente questi tweaks permettono a di di eseguire il codice funzionale. Di solito, puoi trovare una soluzione funzionale abbastanza veloce, ma devi stare attento e sapere cosa fai (specialmente riguardo alle tue strutture dati). Per esempio. l'array concat nel secondo esempio non è bello, ma probabilmente non è male - ma usare gli elenchi qui e concatenarli con ::: sarebbe eccessivo.

Ma questo non è altro che una supposizione istruita se in realtà non si misura la prestazione. Nei progetti complessi è molto difficile prevedere le prestazioni, soprattutto perché le cose come la creazione degli oggetti e le chiamate ai metodi diventano sempre più ottimizzate dal compilatore e dalla JVM.

Suggerirei di iniziare con lo stile funzionale. Se è troppo lento, profilalo. Di solito c'è una soluzione funzionale migliore. In caso contrario, è possibile utilizzare lo stile imperativo (o un mix di entrambi) come ultima risorsa.

+0

Ma questo tipo di sconfitte lo scopo giusto? Voglio dire, Scala è salutato come la prima lingua che collega la programmazione funzionale e degli oggetti. Ma se non puoi essere sicuro che la programmazione del modo funzionale sarà efficiente, allora le persone che si interessano alle prestazioni finiranno per fare di Scala il modo "Java"? – sivabudh

+5

Guarda gli esempi. Quale sembra più facile da comprendere? Lo stile funzionale in realtà ti dice cosa fa l'algoritmo: "scegli un elemento pivot, ordina gli elementi più piccoli, ordina gli elementi più grandi e metti tutto insieme". Questo è un enorme vantaggio rispetto all'esempio imperativo, che riguarda principalmente le variabili di loop e gli indici di array. Quindi, se lo stile funzionale funziona bene, di solito siamo d'oro, ma abbiamo ancora lo stile imperativo come soluzione di ripiego. Tuttavia non impostare == imperativo orientato agli oggetti. Le classi e gli oggetti possono funzionare alla grande in un contesto funzionale. – Landei

+9

In qualsiasi progetto di grandi dimensioni, troverete che pochissimo del codice in realtà deve essere estremamente efficiente. In questi casi, è vero che spesso dovrai ricorrere ai costrutti imperativi. Scala lo supporta.Per il resto del tempo, è meglio programmare in modo che il tuo design sia il più chiaramente evidente nel tuo codice. Questo può essere funzionale, procedurale, orientato agli oggetti o una combinazione di questi. Scala supporta tutti questi. –

Problemi correlati