Quanto è veloce Data.Sequence.Seq rispetto a []?

Question

Chiaramente Seq asymptotically esegue lo stesso o meglio come [] per tutte le operazioni possibili. Ma dal momento che la sua struttura è più complicata delle liste, per le piccole dimensioni il suo sovraccarico costante lo renderà probabilmente più lento. Mi piacerebbe sapere quanto, in particolare:

1. Quanto più lento è <| rispetto a :?
2. Quanto più lento si piega sopra/attraversando Seq rispetto al piegamento sopra/traverso [] (escluso il costo di una funzione di piegatura/movimento)?
3. Qual è la dimensione (approssimativamente) per cui \xs x -> xs ++ [x] diventa più lento di |>?
4. Qual è la dimensione (approssimativamente) per cui ++ diventa più lento di ><?
5. Qual è il costo della chiamata viewl e della corrispondenza del modello sul risultato rispetto alla corrispondenza del modello in un elenco?
6. Quanta memoria ha un -elemento Seq occupante rispetto a un elenco dielementi n? (Senza contare la memoria occupata dagli elementi, solo la struttura.)

So che è difficile da misurare, poiché con Seq si parla di complessità ammortizzato, ma mi piacerebbe sapere almeno alcuni numeri grezzi .

Answer 1

Questo dovrebbe essere un inizio - http://www.haskell.org/haskellwiki/Performance#Data.Sequence_vs._lists

Una sequenza utilizza tra 5/6 e 4/3 volte più spazio all'elenco equivalente (assumendo un sovraccarico di una parola per nodo, come in GHC). Se vengono utilizzate solo le operazioni di deque, l'utilizzo dello spazio sarà vicino all'estremità inferiore dell'intervallo, poiché tutti i nodi interni saranno ternari. L'uso intensivo di split e append si tradurrà in sequenze che utilizzano approssimativamente lo stesso spazio delle liste. In dettaglio:

• un elenco di lunghezza n è costituito da n nodi di cons, ciascuno dei quali occupa 3 parole.
• una sequenza di lunghezza n ha approssimativamente n/(k-1) nodi, dove k è l'arità media dei nodi interni (ciascuno 2 o 3). C'è un puntatore, una dimensione e un sovraccarico per ogni nodo, più un puntatore per ogni elemento, cioè n (3/(k-1) + 1) parole.

L'elenco è un fattore costante non banale più veloce per le operazioni in testa (contro e testa), rendendolo una scelta più efficiente per schemi di accesso tipo stack e stream. Data.Sequence è più veloce per ogni altro modello di accesso, come la coda e l'accesso casuale.

Answer 2

Ho ancora un risultato concreto da aggiungere alla risposta di cui sopra. Sto risolvendo un'equazione di Langevin. Ho usato List e Data.Sequence. In questa soluzione sono in corso numerosi inserimenti nella parte posteriore della lista/sequenza.

Per riassumere, non ho visto alcun miglioramento della velocità, infatti le prestazioni sono peggiorate con Sequenze. Inoltre con Data.Sequence, ho bisogno di aumentare la memoria disponibile per Haskell RTS.

Dal momento che io non sono assolutamente un'autorità per l'ottimizzazione; Inserisco entrambi i casi di seguito. Sarei felice di sapere se questo può essere migliorato. Entrambi i codici sono stati compilati con il flag -O2.

1. Solution with List, prende circa 13,01 sec
2. Solution with Data.Sequence, dura circa 15.13 sec