我正在使用动态规划解决Haskell中的背包问题。我的第一次尝试是构建一个二维表。但是当输入很大时(例如100 * 3190802表),内存很容易耗尽。
由于任何给定行i只依赖于行(i-1),因此我编写了一个函数,希望利用尾递归的优势:
代码中是否存在任何内容,会防止编译器为尾递归生成优化代码?
代码和数据请参考以下链接: code data
由于任何给定行i只依赖于行(i-1),因此我编写了一个函数,希望利用尾递归的优势:
import Data.Vector (Vector, (!))
import qualified Data.Vector as V
-- n items, k capacity, vs values, ws weights
ans:: Int -> Int -> Vector Int -> Vector Int -> Int
ans n k vs ws =
let row = initRow k vs ws
in row ! k
initRow :: Int -> Vector Int -> Vector Int -> Vector Int
initRow k vs ws = itbl 1 $ V.replicate (k + 1) 0
where n = V.length vs
itbl i row
| i > n = row
| otherwise = itbl (i + 1) $ V.generate (k + 1) gen
where gen w =
let w_i = ws ! (i - 1)
no_i = row ! w
ok_i = row ! (w - w_i) + (vs ! (i - 1))
in
if w < w_i then no_i
else max no_i ok_i
如代码所示,itbl
递归调用自身并且在其返回值上不再进行任何计算。然而,我仍然看到 top
中内存无休止地增长:
VIRT PID USER PR NI RES SHR S %CPU %MEM TIME+ COMMAND
1214m 9878 root 20 0 424m 1028 S 40.8 85.6 0:16.80 ghc
代码中是否存在任何内容,会防止编译器为尾递归生成优化代码?
代码和数据请参考以下链接: code data
itbl (i + 1) $ V.generate (k + 1) gen
的调用中移除$
运算符,使其看起来像这样:itbl (i + 1) (V.generate (k + 1) gen)
。我猜测$
使得该调用不是尾递归。 - Marius Danila$
似乎没有起到作用。内存使用量仍在不断增长。 - cfchou