1votos

La tela de araña en Haskell

por josejuan hace 6 años

Usando hashes como ha sugerido jneira es mucho más eficiente.

Un problema fácil de resolver imperativamente... ¿y funcionalmente? (inmutabilidad y transparencia referencial). Aun así (el enfoque funcional), creo que puede ser un buen kata para practicar punteros y/o TAD's.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import qualified Data.IntMap as H 
 
-- map structure to hash 
key (x, y) = 1000 * y + x 
 
-- get infinite steps... 
getSteps :: Int -> [(Int, Int)] -> H.IntMap Int -> [Int] -> [([(Int, Int)], H.IntMap Int)] 
getSteps size s g r = (s, g) : getSteps size s' g' r' 
  where s' = [v (s!!n) (m!!n) | n <- [0..size - 1]]  -- new spiders positions 
        g' = foldl a g s'                            -- new grid counter 
        (m, r') = splitAt size r                     -- using infinite randoms 
 
        -- recreate grid traversing coords 
        a h p = H.update (\n -> Just (n + 1)) (key p) h 
 
        -- move speeder to new position 
        v (x, y) r = if r `mod` 2 == 0 then (m x, y) else (x, m y) 
          where m z = q (z + if (r `div` 2) `mod` 2 == 0 then -1 else 1) 
                q z = if z <= 0 then 2 else if z > size then size -1 else z 
2 comentarios
0votos

Escrito por josejuan hace 6 años

Comparando las dos versiones tenemos:

size	deep	hash
10	1,29	0,68
30	8,15	2,44
50	20,26	4,33
70	39,06	6,21


Una gráfica de esos datos aquí.

Y efectivamente, el coste de la actualización viene a ser "casi" lineal (y en la versión "deep" como el coste promedio ya era lineal para cada araña tenemos cuadrático, efectivamente).
0votos

Escrito por josejuan hace 6 años

(1000 pasos de ejecución en cada test en un Atom D510)

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.