Acelerar Data.Array extracción y filtrado de fila

Question

Tengo una función muy simple en mi aplicación que hace un montón de trabajo y ocupa más tiempo de cálculo:

f :: Int -> Array (Int,Int) Int -> [Int] 
f x arr = [v | v <- range (l,u), vv <- [g!(x,v)], vv /= 0] 
      where ((_,l), (_,u)) = bounds arr 

Lo que esto hace es: extraer una fila en índice x de la matriz arr y devuelve todos los índices de columnas con los elementos \= 0. Así, por ejemplo, dada la siguiente matriz con límites ((0,0),(2,2)):

arr = [[0, 0, 5], 
     [4, 0, 3], 
     [0, 3, 1]] -- for simplicity in [[a]] notation 

la salida esperada es

f 0 arr == [2] 
f 1 arr == [0,2] 
f 2 arr == [1,2] 

¿Cómo puedo acelerar f y el perfil con más detalle lo que realmente lleva la mayor parte del tiempo de cálculo en f (construcción de la lista, acceso a la matriz, etc.)?

¡Gracias!

Answer 1

f x arr = [v | v <- range (l,u), vv <- [g!(x,v)], vv /= 0] 

supongo g es un error, que debería ser arr.
En lugar de range (l,u) use [l .. u], el compilador puede optimizar tanto el primero como el último, pero [l .. u] es más idiomático (y tal vez el compilador no puede optimizar el primero también).
No crear una lista de un solo elemento de sentido, se puede utilizar la prueba directa,

f x arr = [v | v <- [l .. u], arr!(x,v) /= 0] 

El compilador podrá volver a ser capaz de volver a escribir la primera a la segunda, pero a) este último es mucho más claro, yb) no arriesga que el compilador no pueda.

para averiguar dónde se gasta el tiempo, puede insertar anotaciones centro de costos,

f x arr = [v | v <- {-# SCC "Range" #-} [l .. u], {-# SCC "ZeroTest" #-} (arr!(x,v) /= 0)] 

pero tales anotaciones desactivar muchas optimizaciones (compilación de perfiles siempre lo hace), para que la imagen que se obtiene de perfiles puede haber sesgado y difiere de lo que realmente sucede en el programa optimizado.

Answer 2

Aquí es documentación sobre perfiles:

http://www.haskell.org/ghc/docs/latest/html/users_guide/profiling.html

Y un capítulo de un libro:

http://book.realworldhaskell.org/read/profiling-and-optimization.html

Si el código resulta ser lenta debido a las actualizaciones de la matriz, utilice Data.Vector.* de vector paquete.