0votos

La sucesión de Golomb en Haskell

por josejuan hace 5 años

Siguiendo la estrategia de mi anterior solución sin optimizar en Haskell se consiguen los mejores tiempos (de momento) para la búsqueda Golomb exacta (sin aproximación). El algoritmo es O(log n).

Cálculo eficiente de los términos de la sucesión de Golomb: 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, ...

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
{- 
 
    podemos reconstruir los intervalos para cada 
 
        n = 1, 2, 3, ... 
 
    el número de elementos alcanzados es exponencial y 
    la generación de cada intervalo es logaritmico, por 
    lo que el algoritmo final es logaritmico (algo como 
    O(log n)) 
 
    La forma de generar los intervalos es 
 
        (_, h) -> z 
        (h + 1, h + g(z + 1)) -> z + 1 
 
    en C (por ejemplo) será mucho más fácil optimizar, 
    porque se puede predimensionar el array de búsqueda 
    binaria. 
 
-} 
 
import qualified Data.Map as M 
import System.Environment 
import Data.Int 
 
goloms :: Int64 -> Int64 
goloms n = g (2, 3) 2 M.empty 
  where g (d, h) z t = 
          if d <= n && n <= h then z                            -- si lo hemos alcanzado es éste 
                              else g dh' z' t'                  -- sino, calculamos siguiente intervalo 
          where z' = z + 1                                      -- para cada z = 1, 2, 3, ... 
                dh' = (h + 1, h + binSearchIntervalMap t' z')   -- el intervalo que se repiten z' veces 
                t' = M.insert (d, h) z t 
 
 
 
 
 
-- Es una búsqueda binaria sobre los índices (no claves) de Data.Map 
-- sería MUCHO más eficiente hacer la búsqueda directamente o usar 
-- mutable. 
binSearchIntervalMap t h = bs 0 (M.size t) 
  where bs a b = 
          if b < a 
            then error "Argh!!!!!" 
            else 
              if h < md 
                then bs a (m - 1) 
                else 
                  if mh < h 
                    then bs (m + 1) b 
                    else mz 
          where m = (a + b) `div` 2 
                ((md, mh), mz) = M.elemAt m t 
 
main = getArgs >>= print . goloms . read . head 
 
 
{- 
 
Por ejemplo, en un AMD Phenom(tm) II X6 1045T 2.7GHz 
 
$ time -f "%E, %M" ./gs 7e8 
351950 
0:01.02, 81176 
 
 
En la misma máquina, para valores grandes 
 
    12500000000     7,45 
   125000000000    36,98 
   250000000000    60,49 
   500000000000    97,41 
  1000000000000   158,85        1e12 
 
 
Con algo de optimización debería poderse bajar bastante la constante. 
 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.