对于SPOJ,这个memoized DP表的速度有多慢？

Question

SPOILERS:我正在http://www.spoj.pl/problems/KNAPSACK/上工作,所以如果你不想为你破坏可能的解决方案,请不要偷看.

样板:

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

设置舞台的一些类型和帮助:

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)

主要功能:

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

这段代码有效; 我已经尝试插入SPOJ样本测试用例,它会产生正确的结果.但是当我向SPOJ提交此解决方案(而不是导入Luke Palmer的MemoCombinators,我只是将必要的部分复制并粘贴到提交的源中)时,它超出了时间限制.= /

我不明白为什么; 我之前问过一个有效的方法来执行0-1背包,我相信它的速度和它一样快:一个memoized函数,它只会递归地计算它生成的绝对需要的子条目正确的结果.我是否以某种方式弄乱了备忘录？我错过了这段代码的慢点吗？SPOJ是否只是偏向于Haskell？

我甚{-# OPTIONS_GHC -O2 #-}至提到了提交的顶部,但唉,它没有帮助.我尝试了一个类似的解决方案,它使用了Sequences 的2D数组,但它也因为速度太慢而被拒绝了.

Answer 1

有一个主要问题确实减慢了这一速度。这也太多态了吧 函数的类型专用版本可以比多态变体快得多，并且无论出于何种原因，GHC 都没有内联此代码到可以确定所使用的确切类型的程度。当我将 的定义更改integral为：

integral :: Memo Int
integral = wrap id id bits

我得到了大约 5 倍的加速；我认为它的速度足够快，可以被 SPOJ 接受。

然而，这仍然比 gorlum0 的解决方案慢得多。我怀疑原因是因为他使用数组而你使用自定义特里类型。使用 trie 会占用更多内存，并且还会由于额外的间接、缓存未命中等而使查找速度变慢。如果您在 IntMap 中严格化和取消装箱字段，您可能能够弥补很多差异，但我不确定这是可能的。尝试严格限制字段会BitTrie导致运行时崩溃。

纯粹的 haskell 记忆代码可能很好，但我认为它不如做不安全的事情（至少在幕后）那么快。您可以应用Lennart Augustsson 的技术来看看它是否在记忆方面效果更好。