这个记忆化动态规划表为什么在SPOJ上太慢了？

Question

剧透警告：我正在解决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背包，并且我相信这是速度最快的方式：一个记忆化函数，只会递归计算绝对需要的子条目以产生正确的结果。我是否在记忆化中出错了？这段代码是否存在我所忽略的缓慢点？SPOJ是否对Haskell有偏见？

我甚至在提交的顶部放置了{-＃OPTIONS_GHC -O2＃-}，但遗憾的是，它没有起到帮助作用。我尝试了一个类似的解决方案，它使用了一个2D数组的Sequence，但也被拒绝，因为它太慢了。

- Dan Burton

---

能否展示完整的代码并提供必要的内存片段？这将有助于更轻松地诊断问题。 - Max Bolingbroke

"index" 操作的时间复杂度为 O(log(min(i,n-i))) (根据 haddock 文档)。也许您应该使用 Array 或 Vector。 - Thomas M. DuBuisson

hpaste of my precise SPOJ 0-1 knapsack submission 的翻译内容如下： - Dan Burton

如果我没记错的话，hlint 更喜欢使用 {-# LANGUAGE -O2 #-} 而不是 {-# OPTIONS_GHC -O2 #-}，所以你可以尝试使用它。 - Tyler

@DanBurton：当然，这并不是必须的，但如果没有它，你需要所有这些thunks或巨大的dp数组。至于时间 - 我的和你的在最大自定义输入上（重写了已经有的Haskell代码）的比较。 - gorlum0

Answer 1

有一个主要问题会严重拖慢速度。这个程序过于多态化了。类型专门化的函数版本比多态化的变体要快得多，但由于某些原因 GHC 没有将代码内联到可以确定正在使用的确切类型的程度。当我将 integral 的定义更改为：

integral :: Memo Int
integral = wrap id id bits

我获得了大约5倍的加速; 我认为这已经足够快，在SPOJ上应该被接受。

然而，与gorlum0的解决方案相比，这仍然慢得多。我怀疑原因是他使用的是数组，而你使用的是自定义trie类型。使用trie将占用更多的内存，并使查找变慢，因为有额外的间接寻址、缓存未命中等问题。如果你在IntMap中严格化和取消字段的封装，可能可以弥补很多差距，但我不确定是否可能实现。尝试在BitTrie中严格化字段会在运行时导致崩溃。

纯Haskell记忆化代码可能很好，但我认为它不如做不安全的事情快（至少在底层上）。您可以应用Lennart Augustsson的技术来看看它在记忆化方面表现如何。

- John L

Answer 2

唯一能减慢 Haskell 的是 IO，Haskell 中的 String 类型提供了我们在 SPOJ 中不需要的 UTF8 支持。ByteStrings 非常快速，因此您可能希望考虑使用它们。

- Vasantha Ganesh