Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Haskell - Domanda su performance
Forum - Haskell - Domanda su performance

Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 23:40
Giovedì, 01/01/2015
Sono impressionato dall'implementazione di un semplice quicksort menzionato nel libro che sto leggendo, però ho qualche perplessità sull'impatto delle performance.

Codice sorgente - presumibilmente Haskell

  1. quicksort :: (Ord a) => [a] -> [a]
  2. quicksort [] = []
  3. quicksort (x:xs) =
  4.      let menoUguale = [a | a <- xs, a <= x]
  5.           piu = [a | a <- xs, a > x]
  6.      in quicksort menoUguale ++ [x] ++ quicksort piu



Questo quicksort alloca delle nuove liste ad ogni iterazione o c'è qualche "magia" del compilatore che permette di riutilizzare lo spazio della lista esistente?

Un altra curiosità che vorrei capire è l'impatto delle funzioni curried che creano una catena di chiamate per ogni parametro.

Codice sorgente - presumibilmente Haskell

  1. > :t max
  2. max :: Ord a => a -> a -> a
  3. > let b = max 1
  4.  
  5. > b 0
  6. 1
  7. > max 0 1
  8. 1



Va bene che la maggior parte delle funzioni avra' raramente piu' di 4,5 argomenti, ma qual'e' l'impatto sulle performance? C'e' qualche testo/articolo che spiega qual'e' la penalizzazione per quest'approccio (se c'e' una penalizzazione)?

Ultima modifica effettuata da pierotofy il 01/01/2015 alle 23:44


Il mio blog: https://piero.dev
PM Quote
Avatar
ZioCrocifisso (Member)
Pro


Messaggi: 135
Iscritto: 06/03/2013

Segnala al moderatore
Postato alle 0:15
Venerdì, 02/01/2015
Pe quanto riguarda il quicksort, sì, vengono allocate delle nuove liste. GHC è molto avanzato per quanto riguarda le ottimizzazioni, ma in casi come questi non credo possa fare molto. È possibile scrivere l'algoritmo usando la monade ST, con la quale si possono raggiungere performances comparabili a quelle del C, tuttavia essa si usa solo quando è realmente necessaria, perché non è nello "stile" funzionale. Per il currying, non credo che ci sia un impatto rilevante, alla fine si tratta di qualche call/jmp in più. Non conosco comunque nessun articolo che lo spiega.
In generale, considerando il fatto che è un linguaggio funzionale e che usa la lazy evaluation, è inevitabile che Haskell sia inefficiente rispetto a linguaggi come C/C++. Si può programmare quasi imperativamente con IO/ST e senza lazyness con i bang patterns, ma non avrebbe senso, in quel caso sarebbe meglio usare direttamente C. Comunque, i benchmark generalmente mostrano che Haskell è al livello di Java, sopra Python e PHP e sotto C e C++, ma non è realmente possibile quantificare la velocità di Haskell rispetto agli altri. Andrebbero fatti tutti i programmi in tutti i modi possibili.

Ultima modifica effettuata da ZioCrocifisso il 02/01/2015 alle 0:17
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 0:29
Venerdì, 02/01/2015
Grazie, proprio quello che pensavo.


Il mio blog: https://piero.dev
PM Quote