gpt4 book ai didi

performance - 这个内存的 DP 表对 SPOJ 来说太慢了吗?

转载 作者:行者123 更新时间:2023-12-03 22:39:47 25 4
gpt4 key购买 nike

剧透:我正在处理 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 的二维数组。 s,但也因为太慢而被拒绝。

最佳答案

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

integral :: Memo Int
integral = wrap id id bits

我得到了大约 5 倍的加速;我认为它的速度足以被 SPOJ 接受。

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

纯 haskell 内存代码可能很好,但我认为它不如做不安全的事情快(至少在引擎盖下)。您可以申请 Lennart Augustsson's technique看看它是否在内存方面表现更好。

关于performance - 这个内存的 DP 表对 SPOJ 来说太慢了吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7509245/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com