from - haskell insert element into list

Haskell List Comprehension Speed Inconsistencies

Question

Estoy tratando de optimizar la velocidad de ejecución de mi programa, y ​​encontré algunos resultados interesantes que espero que alguien pueda responder. Parece que hacer pequeños cambios en una de mis listas de comprensión cambia drásticamente la velocidad de ejecución, pero no sé por qué.

Aquí está mi programa tal como está ahora.

import Data.Ord
import Control.Monad
import Data.Array
import Data.Ix
import qualified Data.Map as M
import qualified Data.Set as S
import Data.List (minimumBy, foldl'')


arrayMatrix lists = let rlen = length lists
                        clen = length $ head lists
                        r    = ((1,1), (rlen, clen))
                    in array r . zip (range r) $ concat lists

a_star start goal h m = search S.empty (S.singleton start) 
                        (M.singleton start (m ! start)) 
                        $ M.singleton start (m ! start + h ! start)
    where neighbors (r,c) = filter (inRange $ bounds m) [ (r-1,c), (r,c+1), (r+1,c) , (r,c-1)]
          search closed open gs fs
              | S.null open     = 0
              | current == goal = gs M.! goal
              | otherwise       = let open''   = S.delete current open
                                      closed'' = S.insert current closed
                                      neighbs = [(n, ts) | n <- neighbors current, S.notMember n closed
                                                , let ts = gs M.! current + m ! n ]
                                      actionable = filter (/(n,ts) -> S.notMember n open'' || ts < (gs M.! n)) neighbs
                                      (op'',gs'',fs'') = foldl'' (/(o,ng,nf) (n,ts) -> (S.insert n o, M.insert n ts ng, M.insert n (ts + h ! n) nf)) (open'',gs,fs) actionable
                                  in search closed'' op'' gs'' fs''
              where current = minimumBy (comparing (fs M.!)) $ S.toList open

main = do
  matrix <- liftM (arrayMatrix . map (read . (''['':) . (++"]")) . lines) 
            $ readFile "matrix.txt"
  let bds       = bounds matrix
      ulim      = snd bds
      heuristic = let m   = minimum $ elems matrix
                    in listArray bds . map (/(r,c) -> (uncurry (+) ulim)-r-c) $ range bds
  print $ a_star (1,1) ulim heuristic matrix

En este momento, el programa se ejecuta en mi computadora ~ 350 ms (compilado con GHC 7.8.2 -O2) con el matrix.txt suministrado por el Proyecto Euler.

Si cambio de vecinos

neighbs = [(n, ts) | n <- neighbors current, S.notMember n closed
          , let ts = gs M.! current + m ! n ]

a

neighbs = [(n, gs M.! current + m ! n) | n <- neighbors current, S.notMember n closed]

el tiempo de ejecución aumenta a más de 1 seg.
Otros cambios menores, como mover el filtro en la siguiente línea a la lista de comprensión, producen el mismo resultado: ~ 1 seg.
¿Alguien puede explicar por qué sucede esto?

EDITAR: Parece que esto no sucede en las versiones anteriores de GHC. Intenté con GHC 7.6.3 y cada uno de ellos realizó lo mismo.

He incluido los volcados de la ejecución de ghc -O2 -ddump-simpl -dsuppress-all como lo sugiere cdk . Realmente no sé lo que estoy viendo, así que si alguien es capaz de interpretar, eso sería de gran ayuda, gracias.

Enlace a ambos vertederos

EDIT2 (Respuesta a Priyatham): No creo que ese sea el caso. Cambié

neighbs = [(n, ts) | n <- neighbors current, S.notMember n closed
          , let ts = gs M.! current + m ! n ]
actionable = filter ((n,ts) -> S.notMember n open'' || ts < (gs M.! n)) neighbs

a

neighbs = [(n, gs M.! current + m ! n) | n <- neighbors current, S.notMember n closed ]
actionable = filter ((n,!ts) -> S.notMember n open'' || ts < (gs M.! n)) neighbs

utilizando BangPatterns, y eso todavía se ejecuta en poco más de un segundo. De hecho, modificando neigbs desde

neighbs = [(n, ts) | n <- neighbors current, S.notMember n closed
          , let ts = gs M.! current + m ! n ]

a

neighbs = [(n, ts) | n <- neighbors current, S.notMember n closed
          , let !ts = gs M.! current + m ! n ]  -- Added bang before ts

aumenta el tiempo de ejecución a más de 1 seg también.

Answer 1

Aquí hay una conjetura acerca de lo que sucedió con let ts = vs. let !ts = . Lo obtuve al observar la salida de -ddump-stranal (que descarga las anotaciones de análisis de rigor) y al leer el analizador de demanda en GHC .

La diferencia entre let !ts = y let ts = es que si ts es bottom (es decir, undefined ), entonces n no se evaluará en absoluto porque ts se evaluará primero y la evaluación se detendrá. Parece que la diferencia entre dos programas es que el par de enteros n es estricto y no encuadrado en una versión, pero no en la otra (vea la salida de -ddump-stranal y -ddump-simpl ; el enlace anterior describe la salida) .

¿Cómo puede !ts o no !ts afectar el rigor de n ? Creo que si ts está en la parte inferior, entonces el programa debe fallar antes de evaluar n o cualquiera de sus elementos (no estoy seguro de que sea n :: (Int, Int) sí o sus elementos). Entonces, parece que ghc hace lo correcto para mantener n no estricto cuando se requiere que ts sea ​​estricto, porque evaluar n primero y posiblemente fallar en un lugar diferente podría ser un error.

A continuación, ¿cómo forzar !ts para no tener impacto en n ? Tenga en cuenta que ts no puede ser inferior sin que n sea ​​inferior si se sabe que gs , current o m no son inferiores (estos son todos los elementos de la expresión excepto n ) y ya se han evaluado (creo que M.! ! nunca podría ser inferior sin evaluar primero sus argumentos). Por lo tanto, debemos imponer la condición " ts es inferior implica que n es inferior y ya se ha evaluado", para que ghc sepa que es seguro evaluar primero n .

Mi solución: agregar patrones de bang a la current , gs y m . Con mi ghc 7.8.2, esto parece resolver el problema. También parece que solo la current necesita ser forzada.

No estoy muy seguro acerca de la pregunta original acerca de mover la expresión de ts a la tupla, pero la misma solución parece funcionar.

PS nota que

filter (/x -> x > 5) [x | x <- [1..10]] == [x | x <- [1..10], x > 5]

por lo tanto, en sus listas de neighbs y actionable sería más limpio incluir el predicado del filtro en la lista de comprensión de la misma manera:

[(n, ts)
| n <- neighbors current
, S.notMember n closed
, let ts = gs M.! current + m ! n
, S.notMember n open'' || ts < (gs M.! n)
]

Answer 2

Esta no es una respuesta completa, ya que me falta información sobre cómo se implementan internamente las comprensiones de listas y listas.

Cada elemento en neighbs es una tupla y en WHNF, la suma no se evalúa estrictamente. Esto deja thunks no evaluados que podrían aumentar el tiempo de ejecución.

Sugiero volver a escribir la segunda definición usando seq sin usar let , si es posible, para ver si cae el tiempo de ejecución (en cuyo caso es probable que esta respuesta sea correcta).

Lee this para entender lo que es WHNF.