对于SPOJ，这个备忘录DP表太慢了怎么办？

SPOILERS：我正在研究http://www.spoj.pl/problems/KNAPSACK/，所以如果你不想为你宠坏一个可能的解决方案，请不要偷看。对于SPOJ，这个备忘录DP表太慢了怎么办？

的样板：

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时，我只需将所需的部分复制并粘贴到提交的源代码中），它就超出了时间限制。 =/

我不明白为什么; I asked earlier关于执行0-1背包的有效方法，并且我相当确信它的速度和它获得的一样快：一个memoized函数，它只会递归地计算它绝对需要的子条目，以便生成正确的结果。莫名其妙地搞乱了记忆吗？这段代码中有一个缓慢的地方，我错过了？ SPOJ是否对Haskell有偏见？

我甚至把{-# OPTIONS_GHC -O2 #-}放在提交的顶部，但唉，它没有帮助。我试过了一个类似的解决方案，它使用了一个二维数组Sequence s，但它也被拒绝太慢。

来源

2011-09-22 Dan Burton

您是否尝试过分析？总的来说，我还没有发现memoisation对于大多数任务来说是一个很大的帮助。另外，使用序列在这里似乎没有多大的帮助，也许是一个'Map'呢？ – ivanm

你能告诉我们所提供的memotries的必要位的完整代码吗？这将使诊断问题更容易。 –

'索引'操作是'O（log（min（i，n-i）））'（根据haddock）。也许你应该使用一个数组或向量。 –

有一个主要问题真的会减缓这一点。它太多态了。类型专用版本的函数可能比多态变种更快，并且无论出于什么原因，GHC都没有将此代码内联到可以确定使用的确切类型的程度。当我改变的integral的定义：

integral :: Memo Int 
integral = wrap id id bits

我得到一个约5倍的加速比;我认为这个速度足以被SPOJ接受。

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

纯haskell记忆代码可以很好，但我认为它不如做不安全的事情（至少在引擎盖下）。你可以申请Lennart Augustsson's technique看看它是否更好地记录。

来源

2011-10-18 14:02:02

减缓Haskell的一件事就是IO，Haskell中的String类型提供了对于SPOJ我们不需要的UTF8支持。 ByteStrings正在快速发展，因此您可能需要考虑使用它们。

来源

2016-10-22 17:43:30

对于SPOJ，这个备忘录DP表太慢了怎么办？

回答

相关问题