0votos

Floyd-Warshall en Haskell

por josejuan hace 6 años

Leer matriz, calcular distancias mínimas, calcular ruta mínima entre nodos y escribir matriz.

Dada una matriz de costes, implementar el algoritmo Floyd-Warshall.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
{-# LANGUAGE FlexibleContexts #-} 
import Control.Monad (forM, forM_) 
import Data.Array.MArray (MArray) 
import Data.Array.IO (IOUArray, newArray, writeArray, getBounds, readArray) 
import Data.Maybe (isNothing, fromJust) 
import System.Time (getClockTime, diffClockTimes) 
 
-- Define la representación de un coste infinito en la matriz: 
infiniteWeight :: Int 
infiniteWeight = 1000000 
 
isInfWeight :: Int -> Bool 
isInfWeight x = x > 500000 
 
-- Alias para una matriz eficiente en memoria: 
type Matrix = IOUArray (Int, Int) Int 
 
 
-- Dada una lista de nºs en el formato adecuado, genera una matriz de costes: 
readMatrix :: [String] -> IO Matrix 
readMatrix xs = do 
  let (n':_:xs') = xs 
      n = read n' 
  m <- newArray ((1, 1), (n, n)) infiniteWeight 
  forM_ [1..n] $ \x -> writeArray m (x, x) 0 
  wr m xs' 
  return m 
  where wr _ [] = return () 
        wr m (a':b':z':abz) = writeArray m (read a', read b') (read z') >> wr m abz 
 
 
-- Dada una matriz, la reduce a distancias mínimas entre nodos y 
-- genera la matriz de reconstrucción: 
reduceMatrix :: MArray IOUArray Int m => Matrix -> m Matrix 
reduceMatrix m = do 
  ((_, _), (n, _)) <- getBounds m 
  z <- newArray ((1, 1), (n, n)) 0 
  forM_ [1..n] $ \k -> do 
    forM_ [1..n] $ \x -> do 
      forM_ [1..n] $ \y -> do 
        xk <- readArray m (x, k) 
        ky <- readArray m (k, y) 
        xy <- readArray m (x, y) 
        let xky = xk + ky 
        if xy > xky 
          then writeArray m (x, y) xky >> writeArray z (x, y) k 
          else return () 
  return z 
 
-- Busca la ruta más corta entre dos nodos (si existe) 
minPath :: MArray IOUArray Int m => Matrix -> Matrix -> Int -> Int -> m (Maybe [Int]) 
minPath m z a b = path a b 
  where path u v = do 
          uv <- readArray m (u, v) 
          i <- readArray z (u, v) 
          if isInfWeight uv 
            then return Nothing 
            else if i == 0 
                   then return $ Just [] 
                   else do 
                          ui <- path u i 
                          iv <- path i v 
                          if isNothing ui || isNothing iv 
                            then return Nothing 
                            else return $ Just $ fromJust ui ++ [i] ++ fromJust iv 
 
 
 
-- Dada una matriz, la formatea a una cadena 
showMatrix ::  MArray IOUArray Int m => Matrix -> m String 
showMatrix m = do 
  ((_, _), (n, _)) <- getBounds m 
  ms <- forM [1..n] $ \y -> do 
          rs <- forM [1..n] $ \x -> readArray m (x, y) >>= return.show 
          return $ join ", " rs 
  return $ "|" ++ join "|\n|" ms ++ "|" 
  where join :: String -> [String] -> String 
        join _ [] = [] 
        join _ [x] = x 
        join s (x:xs) = x ++ s ++ join s xs 
 
 
main = do 
 
  putStrLn "Reading matrix..." 
  t0 <- getClockTime 
 
  m <- getContents >>= readMatrix.words 
   
  t1 <- getClockTime 
  putStrLn ("Time: " ++ show (diffClockTimes t1 t0)) 
   
  putStrLn "Computing minimum distances..." 
  t2 <- getClockTime 
 
  z <- reduceMatrix m 
 
  t3 <- getClockTime 
  putStrLn ("Time: " ++ show (diffClockTimes t3 t2)) 
   
  {-- si se quiere imprimir 
  ((_, _), (n, _)) <- getBounds m 
  if n < 20 
    then showMatrix m >>= putStrLn 
    else readArray m (2, 1) >>= putStrLn.show 
  --} 
   
  {-- si se quiere calcular una ruta mínima 
  r <- minPath m z 3 4 
  print $ fromJust $ r 
  --} 
   
 
{-- 
 
floyd$ ghc -O2 -fforce-recomp floyd.hs 
[1 of 1] Compiling Main             ( floyd.hs, floyd.o ) 
Linking floyd ... 
 
floyd$ ./floyd < floyd.1000.matrix 
Reading matrix... 
Time: TimeDiff {tdYear = 0, tdMonth = 0, tdDay = 0, tdHour = 0, tdMin = 0, tdSec = 4, tdPicosec = -510075000000} 
Computing minimum distances... 
Time: TimeDiff {tdYear = 0, tdMonth = 0, tdDay = 0, tdHour = 0, tdMin = 0, tdSec = 75, tdPicosec = 130354000000} 
 
--} 
12 comentarios
0votos

Escrito por jneira hace 6 años

Joe pues con este codigo a mi me salen tiempos muy diferentes. Modificando solo el descomentar el sacar el path minimo y poniendo el tiempo despues de ese calculo me sale:
>fwjj2 < g3.txt
Reading matrix...
Time: TimeDiff {tdYear = 0, tdMonth = 0, tdDay = 0, tdHour = 0, tdMin = 0, tdSec
 = 5, tdPicosec = -294000000000}
Computing minimum distances...
-5
[318,268,186,228]
Time: TimeDiff {tdYear = 0, tdMonth = 0, tdDay = 0, tdHour = 0, tdMin = 0, tdSec
 = 14507, tdPicosec = -475000000000}

El dataset es el siguiente:
https://dl.dropbox.com/u/51632130/data/g3.txt
0votos

Escrito por jneira hace 6 años

El anterior era en un centrino, en un intel core duo:
Reading matrix...
Time: TimeDiff {tdYear = 0, tdMonth = 0, tdDay = 0, tdHour = 0, tdMin = 0, tdSec
 = 1, tdPicosec = -188046000000}
Computing minimum distances...
-5
[318,268,186,228]
Time: TimeDiff {tdYear = 0, tdMonth = 0, tdDay = 0, tdHour = 0, tdMin = 0, tdSec
 = 1742, tdPicosec = 630376000000}

Mucho mejor pero alejado de los 75 segundos de tu prueba
0votos

Escrito por josejuan hace 6 años

¿Has verificado que tienes suficiente memoria física?

El dataset no importa (si despreciamos el coste de "writeArray", claro) porque se ejecutan todos los loops siempre.

Cuando tenga a mano el equipo pruebo tus datos.
0votos

Escrito por jneira hace 6 años

Pues la verdad que no lo he cmprobado, pero en este ultimo equipo tengo 3 Gb, en el centrino 2, deberia valer no? Supongo que lo comentas por que el coste vendria por usar el disco duro. Tal vez tenga que ver con ser windows mis so's?
0votos

Escrito por josejuan hace 6 años

Ah! pues los tiempos que publiqué deben ser los de mi ATOM (y no los del Phenom X6), porque me da tiempos similares:

Haskell$ wget https://dl.dropbox.com/u/51632130/data/g3.txt -O flo.txt
...
Haskell$ time -f "%E, %M" ./flo < flo.txt
Reading matrix...
Time: TimeDiff {tdYear = 0, tdMonth = 0, tdDay = 0, tdHour = 0, tdMin = 0, tdSec = 4, tdPicosec = -549590000000}
Computing minimum distances...
Time: TimeDiff {tdYear = 0, tdMonth = 0, tdDay = 0, tdHour = 0, tdMin = 0, tdSec = 73, tdPicosec = 434261000000}
[318,268,186,228]
1:16.89, 27912


como ves, los tiempos son clavados aun con otro dataset (73 seg. VS 75 seg.).

La memoria total consumida son 28Mbytes y mi ATOM va a 1,66GHz.

Realmente, deberías ver como estás compilando (plataforma, etc...), en mi caso:

Haskell$ ghc -O2 -fforce-recomp flo.hs


(y el código he hecho copy/paste del de esta solución).
0votos

Escrito por jneira hace 6 años

Pues si la diferencia esta en el so voy a flipar bastante.
En mis windows (vista el centrino y xp el core duo) he compilado tu codigo con un simple:
> ghc -o fwjj2 Main

Siendo Main
module Main where 
import qualified FloydWarshallJJ2 as FW
Probare a compilarlo en el linux

Arrrrgh me voy a tener que pasar a c o que oxtias
main=FW.main
0votos

Escrito por josejuan hace 6 años

¡¿Pero qué cosas raras estás haciendo?! XD XD XD

¿No puedes sin más copiar y pegar mi código (ej. en "floyd.hs") y luego ejecutar TAL CUAL

C:\..> ghc -O2 -fforcerecomp floyd.hs


¿y obtener el resultado "floyd.exe" (o similar)?
0votos

Escrito por jneira hace 6 años

Ainns no se si has tenido que compilar en güindos (al menos xp y vista) pero no es exactamente igual:
>ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.4.1
>ghc -02 --fforcerecomp FloydWarshallJJ2.hs
ghc: unrecognised flags: -02 --fforcerecomp
>ghc -02 -fforce-recomp FloydWarshallJJ2.hs
ghc: unrecognised flags: -02

Si compilas un fichero que no sea Main.hs no te genera ningun .exe. O yo no he conseguido hacerlo por mucho que por ahi te dicen que si. Esto ocurre pongas -o o no lo pongas pero si pones -o (que solamente renombra el ultimo fichero de las fases de compilacion) te pone un warning
>ghc -o fwjj2 FloydWarshallJJ2.hs
Warning: output was redirected with -o, but no output will be generated because there is no Main module.

Si cojo tu codigo y le pongo el modulo como Main en un archivo Main.hs
ghc -o fwjj2 -fforce-recomp  Main.hs

Tarda lo mismo que mi prueba original
1votos

Escrito por josejuan hace 6 años

No es -02 sino -O2 (O de Oviedo XD), prueba a usar ésta opción y luego para poder compilar directamente mira a ver opciones como "-make", etc...

Al menos parece que el problema es una incorrecta compilación...
0votos

Escrito por jneira hace 6 años

Aaaaams joer, ademas con llamar al modulo Main internamente ya te hace el linkeo al .exe
>ghc -O2 -fforce-recomp FloydWarshallJJ2.hs

Ahora me crea el FloydWarshallJJ2.exe y me tarda lo que a ti, debido al -O2 claro (lo del Main o no Main no afecta segun mis pruebas)

Me parece muy mal lo de -O1 y -O2, joer, optimizame el codigo por defecto a no ser que afecte de forma sustancial al tiempo de compilacion, y en ese caso dejame "quitar" las optimizaciones. ¿O hay algo que se me escapa para hacerlo al reves?
0votos

Escrito por josejuan hace 6 años

"¿O hay algo que se me escapa para hacerlo al reves?"

Sí, cuantas más optimizaciones haga el compilador más alejado está el código resultante de la intención del código escrito.

Es decir, si yo escribo

a = 0; for i = 1 to 10; a++; next i
print a


él puede convertir sin optimizar el bucle o bien generar el equivalente a

print 10


como ves, la optimización máxima no se parece EN NADA a lo que ha escrito el programador.

Además, ciertas optimizaciones hacen suposiciones sobre la forma en que se escribió el código, por lo que según que código no va a tener el mismo comportamiento bajo una optimización u otra (ésto se ve mucho más claro en C con gcc).

De ahí que por defecto, no haya optimizaciones.
0votos

Escrito por jneira hace 6 años

Bueno tras la Big-O cagada (anda que -02 sea un argumento valido tiene huevos) superada gracias a vos mis tiempos son decentes:
Usando llamadas recursivas
>FloydWarshallM.exe g3.txt
Computing minimum distances...
Just (-19)
Time: TimeDiff {tdYear = 0, tdMonth = 0, tdDay = 0, tdHour = 0, tdMin = 0, tdSec
 = 25, tdPicosec = -828609000000}
()

Usando forM
>FloydWarshallForM.exe g3.txt
Computing minimum distances...
Just (-19)
Time: TimeDiff {tdYear = 0, tdMonth = 0, tdDay = 0, tdHour = 0, tdMin = 0, tdSec
 = 23, tdPicosec = 233929000000}
()


Gracie mile!

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.