Haskell: sintonizzazione delle prestazioni list/vector/array

Question

Sto provando Haskell per calcolare le funzioni di partizione dei modelli nella fisica statistica. Ciò comporta l'attraversamento di elenchi di configurazioni piuttosto grandi e la somma di vari osservabili - che vorrei fare nel modo più efficiente possibile.

La versione corrente del mio codice è qui: https://gist.github.com/2420539

Alcune cose strane accadono quando si cerca di scegliere tra liste e vettori per enumerare le configurazioni; in particolare, per troncare la lista, usando V.toList . V.take (3^n) . V.fromList (dove V è Data.Vector) è più veloce di usare semplicemente take, che sembra un po 'contro-intuitivo. In entrambi i casi l'elenco viene valutato pigramente.

L'elenco stesso viene creato utilizzando iterate; se invece io uso Vector s il più possibile e creare l'elenco utilizzando V.iterateN, ancora una volta diventa più lento ...

La mia domanda è: esiste un modo (diverso da splicing V.toList e V.fromList in luoghi casuali nel codice) per prevedere quale sarà il più veloce? (A proposito, ho compilare tutto utilizzando ghc -O2 con l'attuale versione stabile.)

Answer 1

vettori sono severe, e hanno O (1) sottoinsiemi (ad esempio prendono). Hanno anche un inserto ottimizzato ed eliminano. Quindi a volte vedrai miglioramenti delle prestazioni commutando le strutture dati al volo. Tuttavia, di solito è l'approccio sbagliato: mantenere tutti i dati in una forma o nell'altra è meglio. (E stai usando anche gli UArray - confondendo ulteriormente il problema).

Regole generali:

• Se i dati sono di grandi dimensioni e di essere trasformato solo in modo sfuso, con un denso, strutture efficienti come vettori di senso.

• Se i dati sono piccoli e attraversati linearmente, raramente, le liste hanno senso.

Ricordate che le operazioni sulle liste e vettori hanno complessità diversa, così mentre iterate . replicate sulle liste è O (n), ma pigro, lo stesso su vettori non saranno necessariamente più efficiente (si dovrebbe preferire il built in metodi in vettoriale per generare matrici).

In generale, i vettori dovrebbero sempre essere migliori per le operazioni numeriche. Potrebbe essere che devi usare diverse funzioni che fai negli elenchi.

Mi limiterei solo ai vettori. Evita gli UArray ed evita gli elenchi ad eccezione dei generatori.