Haskell：尽管使用（2D）数组，但仍会占用 DP 的内存

大佬教程收集整理的这篇文章主要介绍了Haskell：尽管使用（2D）数组，但仍会占用 DP 的内存，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

如何解决Haskell：尽管使用（2D）数组，但仍会占用 DP 的内存？

我正在尝试解决一场比赛中的动态编程问题，这自然会限制执行时间和内存。粗略地说，问题的剥离版本是首先按行生成一个表，然后处理每一列，这涉及将元素与其垂直相对的对应元素“配对”。这让我认为在内存中维护整个表是必要的。使用数组后，如建议的here，速度还可以，但程序仍然占用内存。

问题

给定两个整数 k 和 n，定义

dp[j][0] = dp[j][n+1] = 0               for j=0,...k,dp[0][m] = 1                            for m=1,...,n,dp[j][m] = dp[j-1][m-1] + dp[j-1][m+1]  for j=0,k and m=1,n.

让 vs[m] = sum [dp[j][m] * dp[k-j][m] | j<-[0..k]] 为所有 @H_135_7@m=1,n。

我需要计算 vs[1],vs[n]，下面是我的代码。 （即 solve 函数。由于结果可能是大数，我们对它们进行模 10^9+7 计算。）

{-# LANGUAGE Safe #-}
{-# OPTIONS_GHC -O2 #-}

import safe Control.Arrow ((>>>))
import qualifIEd Data.Text as T
import qualifIEd Data.Text.IO as TI
import qualifIEd Data.Map as M
import qualifIEd Data.Array as A
import Data.List
import Data.Function

main :: IO ()
main = TI.getContents >>= (T.lines >>> drop 0 >>> tcio >>> (mapM_ putStrLn)) where
    tcio :: [T.Text] -> [String]
    tcio [] = []
    tcio (nkq : rest) = ((:[]). istoline . solve . linetois) nkq  ++ tcio rest;
    linetoi t = f 0 t where f n t = if (T.null) t then n else f (10*n + (on (-) fromEnum (T.head t) '0') ) (T.tail t) ;
    linetois = (map linetoi).(T.words); linestoiss = map linetois;
    itoline = show; istoline = unwords . (map itolinE); isstolines = map istoline

solve :: [Int] -> [Int]
solve [n,k,_] = vs where
    dpf 0 m = if m==0 || m==n+1 then 0 else 1
    dpf j m = if m==0 || m==n+1 then 0 else (dp A.! (j-1) A.! (m-1)) `madd` (dp A.! (j-1) A.! (m+1))
    dp = A.ListArray (0,k)  [(A.ListArray (0,n+1) [dpf j m | m <- [0..(n+1)]]) | j<-[0..k]]
    vs = [foldl1' madd ([(dp A.! j A.! m) `mmult` (dp A.! (k-j) A.! m) | j<-[0..k]]) | m<-[0..(n+1)]]
    madd = modp (+)
    mmult a b = fromInteger $ modp (*) (toInteger a) (toInteger b)
    modp f a b = (f a b)`mod` (10^9+7)

问题

对于 k=5000 和 n=1000，它消耗了超过 2GB 的内存！考虑到比赛中的实际问题（限制设置为 1GB），这远高于 1 GB。

分析结果为 here。我想知道我是否有效地使用了数组结构。提供给 A.ListArray 的列表理解是否意味着在内部创建 2D 列表，有点违背了目的？如果有的话，我们还能如何优化内存？

解决方法

import Control.Monad

modulus :: Int
modulus = 10^9 + 7

plus :: Int -> Int -> Int
plus x y = (x + y) `rem` modulus

times :: Int -> Int -> Int
times x y = (x * y) `rem` modulus

initialize :: Int -> [Int]
initialize n = [0] ++ Replicate (n-2) 1 ++ [1]

step :: [Int] -> [Int]
step xs = [0] ++ zipWith plus xs (drop 2 xs) ++ [0]

v :: [Int] -> Int
v xs = sum (zipWith times xs (reverse xs))

main :: IO ()
main = forever $ do
    line <- getLine
    n:k:_ <- mapM readIO (words linE)
    putStrLn . unwords . map (show . v) . transpose . take k . iterate step $ initialize n

% ghc -O2 test && echo 5000 1000 | /usr/bin/time ./test >/dev/null
[1 of 1] Compiling Main             ( test.hs,test.o )
Linking test ...
test: <stdin>: hGetLine: end of file
Command exited with non-zero status 1
0.56user 0.01system 0:00.58elapsed 99%CPU (0avgtext+0avgdata 68924maxresident)k
0inputs+0outputs (0major+16524minor)pagefaults 0swaps

大佬总结

以上是大佬教程为你收集整理的Haskell：尽管使用（2D）数组，但仍会占用 DP 的内存全部内容，希望文章能够帮你解决Haskell：尽管使用（2D）数组，但仍会占用 DP 的内存所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。