SPOILERS: Estoy trabajando en http://www.spoj.pl/problems/KNAPSACK/, así que no se asome si no quiere una posible solución para usted.¿Cómo es que esta tabla DP memorada es demasiado lenta para SPOJ?
El repetitivo:
import Data.Sequence (index, fromList)
import Data.MemoCombinators (memo2, integral)
main = interact knapsackStr
knapsackStr :: String -> String
knapsackStr str = show $ knapsack items capacity numItems
where [capacity, numItems] = map read . words $ head ls
ls = lines str
items = map (makeItem . words) $ take numItems $ tail ls
Algunos tipos y ayudantes para preparar el escenario:
type Item = (Weight, Value)
type Weight = Int
type Value = Int
weight :: Item -> Weight
weight = fst
value :: Item -> Value
value = snd
makeItem :: [String] -> Item
makeItem [w, v] = (read w, read v)
Y la función primaria:
knapsack :: [Item] -> Weight -> Int -> Value
knapsack itemsList = go
where go = memo2 integral integral knapsack'
items = fromList $ (0,0):itemsList
knapsack' 0 _ = 0
knapsack' _ 0 = 0
knapsack' w i | wi > w = exclude
| otherwise = max exclude include
where wi = weight item
vi = value item
item = items `index` i
exclude = go w (i-1)
include = go (w-wi) (i-1) + vi
Y funciona este código; Intenté conectar el caso de prueba de muestra SPOJ y produce el resultado correcto. Pero cuando envío esta solución a SPOJ (en lugar de importar los MemoCombinators de Luke Palmer, simplemente copio y pego las partes necesarias en la fuente enviada), excede el límite de tiempo. =/
No entiendo por qué; I asked earlier acerca de una forma eficiente de realizar la mochila 0-1, y estoy bastante convencido de que esto es lo más rápido posible: una función memorada que solo calculará recursivamente las subentradas que absolutamente necesita para producir la resultado correcto ¿Metí la memoria de alguna manera? ¿Hay algún punto lento en este código que me falta? ¿Es SPOJ simplemente parcial en contra de Haskell?
Incluso puse {-# OPTIONS_GHC -O2 #-} en la parte superior de la presentación, pero, por desgracia, no sirvió de nada. He intentado con una solución similar que utiliza una matriz 2D de Sequence s, pero también se rechazó por ser demasiado lenta.
¿Has probado el perfilado? En general, no he encontrado que la memorización sea tan útil para la mayoría de las tareas. Además, usar una secuencia no parece ser de mucha ayuda aquí, ¿tal vez un 'Mapa' en su lugar? – ivanm
¿Puede mostrarnos el código completo con los bits necesarios de memotries? Eso haría más fácil diagnosticar el problema. –
La operación 'index' es' O (log (min (i, n-i))) '(según eglefino). Tal vez deberías usar una matriz o vector. –