In che modo questa tabella DP memoizzata è troppo lenta per SPOJ?

Question

SPOILERS: Sto lavorando su http://www.spoj.pl/problems/KNAPSACK/ quindi non sbirciare se non vuoi una soluzione possibile viziata per te.

Il boilerplate:

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 

Alcuni tipi e aiutanti di preparare il terreno:

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) 

E la funzione 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 

E funziona questo codice; Ho provato a collegare il caso di prova SPOJ e produce il risultato corretto. Ma quando invio questa soluzione a SPOJ (invece di importare MemoCombinator di Luke Palmer, semplicemente copio e incollo le parti necessarie nell'origine inviata), eccede il limite di tempo. =/

Non capisco perché; I asked earlier su un modo efficiente per eseguire lo zaino 0-1, e sono abbastanza convinto che questo sia il più veloce possibile: una funzione memoizzata che calcolerà solo ricorsivamente le sotto-voci di cui ha assolutamente bisogno per produrre il risultato corretto Ho incasinato la memoizzazione in qualche modo? C'è un punto lento in questo codice che mi manca? SPOJ è appena prevenuto contro Haskell?

Ho persino inserito {-# OPTIONS_GHC -O2 #-} nella parte superiore dell'invio, ma purtroppo non è stato d'aiuto. Ho provato una soluzione simile che utilizza una matrice 2D di Sequence s, ma è stata anche rifiutata come troppo lenta.

Answer 1

C'è uno dei problemi principali che rallenta davvero questo aspetto. È troppo polimorfico. Le versioni specializzate di tipo delle funzioni possono essere molto più veloci delle varietà polimorfiche e, per qualsiasi ragione, GHC non sta mettendo in riga questo codice fino al punto in cui può determinare i tipi esatti in uso. Quando cambio la definizione di integral a:

integral :: Memo Int 
integral = wrap id id bits 

ottengo un aumento di velocità di circa 5 volte; Penso che sia abbastanza veloce da essere accettato su SPOJ.

Questo è ancora significativamente più lento della soluzione di gorlum0 tuttavia. Sospetto che il motivo sia perché usa gli array e usi un tipo di trie personalizzato. L'utilizzo di un trie richiederà molta più memoria e renderà anche più lente le ricerche a causa di riferimenti aggiuntivi, errori di cache, ecc. Potresti essere in grado di fare molta differenza se i campi di unbox sono stati modificati in IntMap, ma non sono sicuro è possibile Cercando di correggere i campi in BitTrie si creano arresti anomali del runtime per me.

Il codice di memoizzazione haskell puro può essere buono, ma non penso sia veloce come fare cose non sicure (almeno sotto il cofano). È possibile applicare Lennart Augustsson's technique per vedere se è più conveniente durante la memoizzazione.

Answer 2

L'unica cosa che rallenta Haskell è IO, il tipo String in Haskell fornisce il supporto UTF8 che non è necessario per SPOJ. Le ByteStrings sono incredibilmente veloci, quindi potresti prendere in considerazione la possibilità di utilizzarle.