Tabla eficiente para programación dinámica en Haskell

Question

He codificado 0-1 Knapsack problem en Haskell. Estoy bastante orgulloso de la pereza y el nivel de generalidad alcanzado hasta ahora.

Empiezo brindando funciones para crear y manejar una matriz 2d diferida.

mkList f = map f [0..] 
mkTable f = mkList (\i -> mkList (\j -> f i j)) 

tableIndex table i j = table !! i !! j 

Entonces hago una tabla específica para un problema de la mochila dada

knapsackTable = mkTable f 
    where f 0 _ = 0 
      f _ 0 = 0 
      f i j | ws!!i > j = leaveI 
       | otherwise = max takeI leaveI 
       where takeI = tableIndex knapsackTable (i-1) (j-(ws!!i)) + vs!!i 
        leaveI = tableIndex knapsackTable (i-1) j 

-- weight value pairs; item i has weight ws!!i and value vs!!i 
ws = [0,1,2, 5, 6, 7] -- weights 
vs = [0,1,7,11,21,31] -- values 

y terminar con una función par de ayuda para mirar la tabla

viewTable table maxI maxJ = take (maxI+1) . map (take (maxJ+1)) $ table 
printTable table maxI maxJ = mapM_ print $ viewTable table maxI maxJ 

Esta cantidad fue bastante fácil . Pero quiero dar un paso más.

Quiero una mejor estructura de datos para la tabla. Idealmente, debería ser

• Sin Embalaje (inmutable) [editar] No importa este
• Lazy
• ilimitada
• O(1) tiempo para construir
• O(1) complejidad de tiempo para buscar una determinada entrada,
  (más realista, en el peor O(log n), donde n es i*j para buscar la entrada en r ow i, columna j)

Puntos de bonificación si puede explicar por qué/cómo su solución cumple estos ideales.

También puntos de bonificación si puede generalizar más knapsackTable, y demostrar que es eficiente.

En la mejora de la estructura de datos que debe tratar de cumplir los siguientes objetivos:

• Si pido la solución cuando el peso máximo es 10 (en mi código actual, que sería indexTable knapsackTable 5 10, los 5 medios incluye los puntos del 1 al 5) solo se debe realizar la cantidad mínima de trabajo necesaria. Idealmente, esto significa que no O(i*j) funcionan para forzar el lomo de cada fila de la tabla a la longitud necesaria de la columna. Podría decir que esto no es "verdadero" DP, si cree que DP significa evaluar la totalidad de la tabla.
• Si solicito que se imprima toda la tabla (algo así como printTable knapsackTable 5 10), los valores de cada entrada deben calcularse una sola vez.Los valores de una celda dada deben depender de los valores de otras células (estilo DP: el ser idea, nunca se vuelve a calcular el mismo subproblema dos veces)

---

Ideas:

• Data.Array delimitadas :(
• UArray estricta :(
• Memoization techniques (SO pregunta sobre DP en Haskell) esto podría funcionar

Respuestas que hacen algunos compromisos a mis ideales declarados serán upvoted (por mí, de todos modos), siempre que sean informativos. La respuesta con los menores compromisos será probablemente la "aceptada".

Answer 1

En primer lugar, es probable que su criterio para una estructura de datos no empaquetados sea un poco engañoso. Los valores no incluidos deben ser estrictos, y no tienen nada que ver con la inmutabilidad. La solución que voy a proponer es inmutable, floja y en caja. Además, no estoy seguro de qué manera quieres que la construcción y las consultas sean O (1). La estructura que propongo está construida perezosamente, pero debido a que es potencialmente ilimitada, su construcción completa llevaría un tiempo infinito. Consultar la estructura tomará O (k) tiempo para cualquier clave particular de tamaño k, pero, por supuesto, el valor que está buscando puede tardar más tiempo en computarse.

La estructura de datos es un trie perezoso. Estoy usando la biblioteca MemoTrie de Conal Elliott en mi código. Para la genericidad, toma funciones en lugar de listas para los pesos y valores.

knapsack :: (Enum a, Num w, Num v, Num a, Ord w, Ord v, HasTrie a, HasTrie w) => 
      (a -> w) -> (a -> v) -> a -> w -> v 
knapsack weight value = knapsackMem 
    where knapsackMem = memo2 knapsack' 
     knapsack' 0 w = 0 
     knapsack' i 0 = 0 
     knapsack' i w 
      | weight i > w = knapsackMem (pred i) w 
      | otherwise = max (knapsackMem (pred i) w) 
         (knapsackMem (pred i) (w - weight i)) + value i 

Básicamente, se implementa como un trie con una espina perezoso y valores perezosos. Está limitado solo por el tipo de clave.Como todo es perezoso, su construcción antes de forzarlo con consultas es O (1). Cada consulta fuerza una sola ruta hacia abajo del trie y su valor, por lo que es O (1) para un tamaño de clave limitada O (log n). Como ya dije, es inmutable, pero no unboxed.

Compartirá todo el trabajo en las llamadas recursivas. En realidad, no le permiten imprimir directamente el trie, pero algo como esto no debe hacer ningún trabajo redundante:

mapM_ (print . uncurry (knapsack ws vs)) $ range ((0,0), (i,w)) 

Answer 2

¿Por qué no usará Data.Map poniendo el otro Data.Map en él? Hasta donde yo sé, es bastante rápido. No sería perezoso sin embargo.

Más que eso, se puede implementar Ord clase de tipos de datos para usted

data Index = Index Int Int 

y poner un índice bidimensional directamente como una clave. Puede lograr la pereza generando este mapa como una lista y luego simplemente use

fromList [(Index 0 0, value11), (Index 0 1, value12), ...] 

Answer 3

Unboxed implica estricto y limitado. Cualquier cosa 100% Unboxed no puede ser Lazy o Unbounded. El compromiso habitual se materializa en la conversión de [Word8] a Data.ByteString.Lazy donde hay trozos unboxed (estricto ByteString) que se unen perezosamente juntos de una manera ilimitada.

Un generador de tablas mucho más eficiente (mejorado para rastrear elementos individuales) se puede hacer usando "scanl", "zipWith" y mi "takeOnto". Este evitar efectivamente usando (!!), mientras que la creación de la tabla:

import Data.List(sort,genericTake) 

type Table = [ [ Entry ] ] 

data Entry = Entry { bestValue :: !Integer, pieces :: [[WV]] } 
    deriving (Read,Show) 

data WV = WV { weight, value :: !Integer } 
    deriving (Read,Show,Eq,Ord) 

instance Eq Entry where 
    (==) a b = (==) (bestValue a) (bestValue b) 

instance Ord Entry where 
    compare a b = compare (bestValue a) (bestValue b) 

solutions :: Entry -> Int 
solutions = length . filter (not . null) . pieces 

addItem :: Entry -> WV -> Entry 
addItem e wv = Entry { bestValue = bestValue e + value wv, pieces = map (wv:) (pieces e) } 

-- Utility function for improve 
takeOnto :: ([a] -> [a]) -> Integer -> [a] -> [a] 
takeOnto endF = go where 
    go n rest | n <=0 = endF rest 
      | otherwise = case rest of 
          (x:xs) -> x : go (pred n) xs 
          [] -> error "takeOnto: unexpected []" 

improve oldList wv@(WV {weight=wi,value = vi}) = newList where 
    newList | vi <=0 = oldList 
      | otherwise = takeOnto (zipWith maxAB oldList) wi oldList 
    -- Dual traversal of index (w-wi) and index w makes this a zipWith 
    maxAB e2 e1 = let e2v = addItem e2 wv 
       in case compare e1 e2v of 
        LT -> e2v 
        EQ -> Entry { bestValue = bestValue e1 
           , pieces = pieces e1 ++ pieces e2v } 
        GT -> e1 

-- Note that the returned table is finite 
-- The dependence on only the previous row makes this a "scanl" operation 
makeTable :: [Int] -> [Int] -> Table 
makeTable ws vs = 
    let wvs = zipWith WV (map toInteger ws) (map toInteger vs) 
     nil = repeat (Entry { bestValue = 0, pieces = [[]] }) 
     totW = sum (map weight wvs) 
    in map (genericTake (succ totW)) $ scanl improve nil wvs 

-- Create specific table, note that weights (1+7) equal weight 8 
ws, vs :: [Int] 
ws = [2,3, 5, 5, 6, 7] -- weights 
vs = [1,7,8,11,21,31] -- values 

t = makeTable ws vs 

-- Investigate table 

seeTable = mapM_ seeBestValue t 
    where seeBestValue row = mapM_ (\v -> putStr (' ':(show (bestValue v)))) row >> putChar '\n' 

ways = mapM_ seeWays t 
    where seeWays row = mapM_ (\v -> putStr (' ':(show (solutions v)))) row >> putChar '\n' 

-- This has two ways of satisfying a bestValue of 8 for 3 items up to total weight 5 
interesting = print (t !! 3 !! 5) 

Answer 4

Lazy vectores almacenables: http://hackage.haskell.org/package/storablevector tiempo

ilimitada, perezoso, O (chunksize) para construir, O (n/chunksize) indexación, donde Chunksize puede ser lo suficientemente grande para cualquier propósito. Básicamente es una lista perezosa con algunos beneficios significativos de factor constante.

Answer 5

Para memoize funciones, recomiendo una biblioteca como Lucas Palmer memo combinators. La biblioteca usa intentos, que no tienen límites y tienen una búsqueda O (tamaño de clave). (En general, no se puede hacer nada mejor que O (tamaño de la clave) de búsqueda, ya que siempre tiene que tocar todos los bits de la clave.)

knapsack :: (Int,Int) -> Solution 
knapsack = memo f 
    where 
    memo = pair integral integral 
    f (i,j) = ... knapsack (i-b,j) ... 

Internamente, el combinador integral probablemente construye una estructura de datos infinita

data IntTrie a = Branch IntTrie a IntTrie 

integral f = \n -> lookup n table 
    where 
    table = Branch (\n -> f (2*n)) (f 0) (\n -> f (2*n+1)) 

de búsqueda funciona así:

lookup 0 (Branch l a r) = a 
lookup n (Branch l a r) = if even n then lookup n2 l else lookup n2 r 
    where n2 = n `div` 2 

Hay otras maneras de construir intentos infinitos, pero éste es Población Arkansas.