L'implementazione di ordinamento della libreria Haskell più veloce

Question

L'implementazione di ordinamento della libreria Haskell più veloce

#1 da (6 voti)

5

Sto implementando un'applicazione in Haskell e, per l'ordinamento, uso la funzione di libreria Data.List.sort . Tuttavia, mi chiedevo se questa è l'implementazione di ordinamento più veloce nella libreria standard Haskell (forse gli elenchi non sono la scelta migliore per l'ordinamento efficiente).

Ho trovato diverse alternative, ad es. ordinamento heap su matrici , < a href="http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequence.html#g:10"> ordina le sequenze (ma la documentazione non dì che tipo di algoritmo è usato).

La mia domanda è: qual è l'implementazione di ordinamento più veloce (tipo di contenitore + funzione di ordinamento) fornita dalla libreria standard Haskell? C'è qualche pagina di documentazione che elenca tutte le funzioni di ordinamento delle librerie e le confronta con le loro prestazioni?

Modifica

Per fornire un contesto più ampio, ho un punto di riferimento. Ho scritto un semplice programma in C, Java, Python e Haskell che

Legge 1000000 stringhe (linee) da un file di testo.
Ordina le stringhe utilizzando un algoritmo di ordinamento incorporato (libreria).
Scrive l'elenco ordinato di stringhe su un file.

Per ogni implementazione, misuro solo il tempo di smistamento (tralasciando il tempo necessario per l'IO del disco). Eseguendo il benchmark su Ubuntu 12.04, ottengo

C (gcc 4.6.3, qsort su char ** ): 0.890 s
Java (OpenJDK 64-Bit 1.7.0_09, Collections.sort() su java.util.LinkedList<String> ): 1.307 s
Python (Python 2.7.3, list.sort() ): 1.072 s
Haskell (GHC 7.4.1, Data.List.sort su [Data.ByteString.UTF8.ByteString] ): 11.864 s

Quindi mi chiedo se ci sia un altro tipo di dati / funzione di libreria in Haskell che possa offrire prestazioni migliori.

haskell sorting

posta Giorgio 23.12.2012 - 00:05

fonte

1 risposta

Leggi altre domande sui tag haskell sorting

Panoramica del processo agile che posso applicare ad un avvio MVC Pattern - Come ottenere errori dal modello al controller?

score 6 · Accepted Answer

Il problema con Data.List.sort è che usa l'ordinamento di fusione, che crea nuovi elenchi durante ogni passaggio. Quindi viene dedicato molto tempo all'assegnazione e alla liberazione della memoria.

Sorprendentemente, AFAIK non esiste una libreria di ordinamento per matrici mutevoli , che sono probabilmente più veloci. Così ho provato a crearne uno e metterlo su github: marray-sort . Richiede test rigorosi, lucidatura e ottimizzazione, ma finora sembra già essere significativamente più veloce di Data.List.sort .

Se fai qualche esperimento con esso, sarei felice di vedere i risultati. Ho messo il tuo benchmark (leggermente modificato) su src-test / Test.hs per comodità. Non dimenticare di compilare tutto con -O2 per attiva le necessarie ottimizzazioni del compilatore.

Modifica: ho scoperto che esiste un'implementazione se introsortale per vettori modificabili in vettore-algoritmi . Secondo le mie misurazioni, è leggermente più veloce (5-10%) del mio tentativo sopra per MArray s Vedi anche: Come si ordina con Data.Vector.Generic.Mutable? .