performance - 对于SPOJ来说，这个存储的DP表如何太慢？

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，我只是将必要的部分复制并粘贴到提交的源中)，它超出了时间限制。 = /

我不明白为什么；我asked earlier讲述了一种执行0-1背包的有效方法，我相当确信这差不多可以做到:记忆函数，它将仅递归地计算出产生它所必需的子条目。正确的结果。我是否以某种方式弄乱了备忘录？我缺少此代码中的慢点吗？ SPOJ是否只是对Haskell有偏见？

我什至把{-# OPTIONS_GHC -O2 #-}放在提交的顶部，但是，这没有帮助。我尝试了使用二维数组Sequence的类似解决方案，但由于速度太慢而被拒绝。

最佳答案

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

integral :: Memo Int
integral = wrap id id bits

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

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

纯粹的haskell记忆代码可能很好，但是我认为它不如做不安全的事情(至少在幕后)那样快。您可以应用Lennart Augustsson's technique来查看它在记忆方面是否更好。

关于performance - 对于SPOJ来说，这个存储的DP表如何太慢？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7509245/