Haskell: lista/vector/matriz de ajuste del rendimiento

Question

Estoy probando Haskell para calcular las funciones de partición de los modelos en física estadística. Esto implica atravesar listas bastante grandes de configuraciones y sumar varios observables, lo que me gustaría hacer de la manera más eficiente posible.

La versión actual de mi código está aquí: https://gist.github.com/2420539

Algunas cosas extrañas suceden cuando se trata de elegir entre las listas y vectores para enumerar las configuraciones; en particular, para truncar la lista, usando V.toList . V.take (3^n) . V.fromList (donde V es Data.Vector) es más rápido que simplemente usar take, lo que se siente un poco contrario a la intuición. En ambos casos, la lista se evalúa perezosamente.

La lista en sí está construida usando iterate; si en vez utilizo Vector s tanto como sea posible y construir la lista mediante V.iterateN, de nuevo se vuelve más lenta ...

Mi pregunta es, ¿hay alguna manera (que no sea de empalme V.toListV.fromList y en lugares al azar en el código) para predecir cuál será el más rápido? (Por cierto, I compilar todo usando ghc -O2 con la versión estable actual.)

Answer 1

vectores son estrictas, y tienen O (1) subconjuntos (por ejemplo toman). También tienen una inserción y eliminación optimizadas. Por lo tanto, a veces verá mejoras de rendimiento al cambiar las estructuras de datos sobre la marcha. Sin embargo, por lo general es el enfoque equivocado, es mejor mantener todos los datos en una forma u otra. (Y también está usando UArrays, lo que confunde aún más el problema).

reglas generales:

• Si los datos son grandes y se transforma sólo en la moda a granel, utilizando una densa estructuras, eficientes como vectores tienen sentido.

• Si los datos son pequeños y se atraviesan linealmente, rara vez, las listas tienen sentido.

Recuerde que las operaciones en las listas y vectores tienen distinta complejidad, por lo que mientras iterate . replicate en las listas es O (n), pero perezoso, lo mismo en vectores no necesariamente será tan eficiente (se debe preferir la construcción en métodos en vectores para generar matrices).

En general, los vectores siempre deberían ser mejores para las operaciones numéricas. Es posible que tengas que usar diferentes funciones que haces en las listas.

Me limitaría a los vectores solamente. Evite UArrays y evite las listas, excepto como generadores.