1votos

El problema de Ullman en Haskell

por josejuan hace 6 años

Esta es la versión con coste O(n * |xs|) solo que me olvidé de añadir dos computaciones más y el coste final es O(n * |xs| + n + n^2) que puede reducirse a O(n * |xs| + n + n log n). Para n << |xs| es mucho más eficiente ésta que la anterior (pero más verbose, claro).

Decidir si existe un subconjunto de un tamaño dado y con su suma acotada

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
-- no se si hay algún algoritmo de inserción por ahí 
-- este mantiene el orden de mayor a menor 
i [] p = [p] 
i xxs@(x:xs) p = if x <= p then (p:xxs) else x:i xs p 
 
 
ullman xs n k = 
 
 -- Mantenemos una lista de 'n' elementos ordenada DESC 
 -- que es inicializada con los 1ºs 'n'. 
 -- Para cada elemento que queda, se mira si mejora la 
 -- suma hasta cumplir con True o fallar con False. 
 r l t $ sum h -- mantenemos precalculada la suma de 'l' 
 
 where 
  (h, t) = splitAt n xs -- en 'l' los 1ºs 'n' 
  l = foldl i [] h -- 'l' siempre de mayor a menor 
  r _ [] ss = ss < k -- si no hay más ¿cumple 'l'? 
  r aas@(a:as) (p:ps) ss = 
   if ss < k -- si ya cumple 'l' pues ok 
    then True 
    else -- si no cumple... 
     if a < p -- ¿el nº que viene mejora? 
      then r aas ps ss -- no, pues lo ignoramos 
      else r (i as p) ps (ss - a + p) -- sí, pues... 
                  -- insertamos en 'l' y ajustamos 'ss' 
1 comentario
0votos

Escrito por josejuan hace 6 años

Para comparar las implementaciones "sort" (sea ullman1) vs "acumulador" (sea ullman2), se puede hacer:

import Data.List
import System.Environment

...aquí ullman1 y ullman2...
ullman1 :: [Int] -> Int -> Int -> Bool
...
ullman2 :: [Int] -> Int -> Int -> Bool
...

test1 n m k = ullman1 [n,n-1..1] m k
test2 n m k = ullman2 [n,n-1..1] m k
test3 n m k = ullman1 [1..n] m k
test4 n m k = ullman2 [1..n] m k

main = do
 q <- getArgs
 let z = map read q
 print $ ([test1,test2,test3,test4]!!(z!!0)) (z!!1) (z!!2) (z!!3)



compilar (eg: ghc --make ul.hs) y entonces lanzar los test como:

tmp$ time -f '%E, %M' ./ul 0 30000000 3 7
True
0:41.92, 1861060
tmp$ time -f '%E, %M' ./ul 1 30000000 3 7
True
0:24.09, 2212
tmp$ time -f '%E, %M' ./ul 2 30000000 3 7
^C^C^C (lo maté de aburrimiento ¡qsort es n^2 en peor caso!
2:20.79, 1877340
tmp$ time -f '%E, %M' ./ul 3 30000000 3 7
True
0:00.06, 1736


Como se ve, esta última versión tiene un promedio mucho mejor (depende de los datos, claro).

XD XD

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.