0votos

Encuentra el Punto Óptimo en Haskell

por josejuan hace 3 años

En la solución anterior, se realizaban tantas ordenaciones de listas de coordenadas X como coordenadas Y hubiera. Un speedup importante es mantener ya ordenada una única lista de coordenadas X.

Buscar el punto dentro de un mapa que cumpla con los siguientes requerimientos.

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
{- 
 
  En la versión anterior, las coordenadas X se revisaban y ordenaban para cada Y nueva. 
 
  Una optimización sensiblemente mayor y que reduce enormemente el efecto del radio de 
  búsqueda es mantener una única estructura ordenada con las X y los incrementos respectivos 
  cuando comienza o termina una caja. 
 
  Por ejemplo, si una caja empieza en x1 y termina en x2, entonces se produce un +1 en x1 y 
  un -1 en x2 en el contador de cajas "activas". 
 
  Así, únicamente hay que ir actualizando la lista de +1 y -1 en las X activas. 
 
  Como las cajas son cerradas, a la hora de contabilizar, primero se hace el +n, se contabiliza 
  y luego se hace el -n. 
 
  Por ejemplo, si tenemos las cajas siguientes, en cada fila los incrementos son 
 
      +--------------------+    (1,0), (0,-1) 
      |        +------+    |    (1,0), (1,0), (0,-1), (0,-1) 
      +----+   |      |    |    (2,0), (0,-1), (1,0), (0,-1), (0,-1) 
      |    |---|      |----+    idem 
      +----+   +------+         (1,0), (0,-1), (1,0), (0,-1) 
 
  Así, en la fila que se repite, el contador iría pasando sucesivamente 
 
      0, 2, 1, 2, 1, 0 
 
  Ahora, en mi humilde Atom, obtiene en tiempo razonable el resultado sobre 500.000 cajas 
  en un rando de 1.000 x 1.000 
 
    centroide$ time -f "%E, %M" /home/josejuan/.local/bin/centroide-exe 1000 30 500000 
    Máx agregado size: 2027, núm óptimos: 1 
    0:17.65, 240348 
 
  Incluso con millones de cajas (puntos), este pobre Atom obtiene el resultado en tiempo razonable 
 
    centroide$ time -f "%E, %M" /home/josejuan/.local/bin/centroide-exe 1000 15 2000000 
    Máx agregado size: 2112, núm óptimos: 1 
    1:15.16, 1007436 
 
  Usando Array se obtendría un speedup muy importante, al quedar indizados los incrementos +1/-1 pero 
  se perdería la capacidad de usar cajas sobre cualquier dominio (tamaños muy grandes, números reales, ...) 
 
-} 
data J = J { x1 :: !Int, x2 :: !Int } deriving Show 
óptimos :: Int → [(Int, Int)] → (Int, [(Int, Int)]) 
óptimos d ps = 
    let caja (x, y) = let j = J (x - d) (x + d) 
                      in  [(y - d, [(𝐹, j)]), (y + d, [(𝑇, j)])] -- Entrada y salida 
    in  optimosY 0 [] ∅ $ assocs $ fromListWith (⧺) $ concatMap caja ps 
 
optimosY :: Int → [(Int, Int)] → IntMap (Int, Int) → [(Int, [(𝔹, J)])] → (Int, [(Int, Int)]) 
optimosY sN sT  _ [] = (sN, sT) 
optimosY sN sT mD ((iY, iS): cs) = 
    let upMD i md f = foldr fus md $ concat [[(x1, (i, 0)), (x2, (0, -i))] | (t, J x1 x2) ← iS, f t] 
        fus (x, (u, v)) m = alter a x m -- incrementa y elimina si queda 0 
                            where a 𝑁          = 𝐽 (u, v) 
                                  a (𝐽 (r, s)) = case (u + r, v + s) of 
                                                   (0, 0) → 𝑁 
                                                   n      → 𝐽 n 
        mD' = upMD 1 mD ¬-- las entradas 
        (xN, xT) = optimosX 0 [] 0 $ assocs mD' 
        mD'' = upMD (-1) mD' id -- las salidas 
        sT' = (, iY) ↥ xT 
    in  case sN `compare` xN of 
          EQ → optimosY sN (sT' ⧺ sT) mD'' cs 
          LT → optimosY xN  sT'       mD'' cs 
          GT → optimosY sN        sT  mD'' cs 
 
optimosX :: Int → [Int] → Int → [(Int, (Int, Int))] → (Int, [Int]) 
optimosX xN xT _ [] = (xN, xT) 
optimosX xN xT c ((x, (u, v)):ds) = 
   let c' = c + u 
   in  case xN `compare` c' of 
         EQ → optimosX xN (x:xT) (v + c') ds 
         LT → optimosX c' [x]    (v + c') ds 
         GT → optimosX xN    xT  (v + c') ds 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.