Q&A
URLは https://teratail.com/help/question-tips#questionTips3-7 の [リンク] で [リンク先のタイトル](http...) に修正してください。
詳細
今回、AtCoderでナップサック問題を解いている際にこのエラーが出ました。入力ケースが大きいときにのみ起こるので、VectorやArrayのメモリ確保の際に必要なメモリの量が膨大になってしまっているのかもしれません。一応Unboxed Vectorを使っているのですが、今回初めて触ったのでどこかで非効率的な処理をしているのだと思います。Unboxed Arrayは遅延評価できなくなるため使用していません。
解いている問題
ソースコード
Haskell
1import Control.Monad 2import qualified Data.ByteString.Char8 as BS 3import Data.List 4import Data.Char 5import Data.Maybe 6import Data.Ord 7import Data.Time 8import qualified Data.Vector as V 9import qualified Data.Vector.Mutable as VM 10import qualified Data.Vector.Unboxed as VU 11import qualified Data.Array as A 12import qualified Data.Array.Unboxed as AU 13 14readIntegers :: IO [Integer] 15readIntegers = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine 16 17readIntegerLists :: Int -> IO [[Integer]] 18readIntegerLists n = 19 replicateM n (map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine) 20 21readInts :: IO [Int] 22readInts = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine 23 24readIntLists :: Int -> IO [[Int]] 25readIntLists n = 26 replicateM n (map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine) 27 28readStrings :: IO [String] 29readStrings = map BS.unpack . BS.words <$> BS.getLine 30 31readStringLists :: Int -> IO [[String]] 32readStringLists n = replicateM n (map BS.unpack . BS.words <$> BS.getLine) 33 34toPair :: [a] -> (a, a) 35toPair [x, y] = (x, y) 36 37main :: IO () 38main = do 39 [n, w] <- readInts 40 vw <- readIntLists n 41 print $ solve n w (map toPair vw) 42 return () 43 44solve n w vw = f 0 w 45 where 46 items = VU.fromList vw 47 f i cap 48 | i == n = 0 49 | snd (items VU.! i) > cap = f (i + 1) cap 50 | otherwise = max 51 (memo A.! (i + 1, cap)) 52 (memo A.! (i + 1, cap - snd (items VU.! i)) + fst (items VU.! i)) 53 memo = A.array ((0, 0), (n, w)) 54 [ ((n', w'), f n' w') | n' <- [0 .. n], w' <- [0 .. w] ] 55 56
標準入力と出力
入力値が小さい時
input
13 10 215 9 310 6 46 4
output
116
入力値が大きいとき
input
130 499887702 2128990795 137274936 3575374246 989051853 4471048785 85168425 5640066776 856699603 6819841327 611065509 7704171581 22345022 8536108301 678298936 9119980848 616908153 10117241527 28801762 11325850062 478675378 12623319578 706900574 13998395208 738510039 14475707585 135746508 15863910036 599020879 16340559411 738084616 17122579234 545330137 18696368935 86797589 19665665204 592749599 20958833732 401229830 21371084424 523386474 22463433600 5310725 23210508742 907821957 24685281136 565237085 25619500108 730556272 2688215377 310581512 27558193168 136966252 28475268130 132739489 29303022740 12425915 30122379996 137199296 31304092766 23505143
output
1AtCoder-exe: internal error: Unable to commit 124093726720 bytes of memory 2 (GHC version 8.6.5 for x86_64_unknown_linux) 3 Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug 4fish: 'stack run' terminated by signal SIGABRT (Abort)
字下げはわかり易くするために、4桁毎に字下げする人が多いようです。無理にとは言いませんが。
回答1件
0
ベストアンサー
Haskell
1 memo = A.array ((0, 0), (n, w)) 2 [ ((n', w'), f n' w') | n' <- [0 .. n], w' <- [0 .. w] ]
制約がややこしいですが n <= 200, w <= 10 ^ 9 なので、メモしてる状態数が多すぎます。
遅延評価がどこまで賢く評価してくれるのかわかりませんが、いずれにしても今のやり方では重さが同じになる組み合わせが少ないケースでは、 max(w, 2 ^ n) レベルの重さの違う組み合わせが存在するのでどれだけ効率が良くても難しいかもしれません。(wi <- 2^(i-1)のケースを考えてみてください)
Haskell
1 f i cap 2 | i == n = 0 3 | snd (items VU.! i) > cap = f (i + 1) cap 4 | otherwise = max 5 (f (i + 1) cap) 6 ((f (i + 1) (cap - snd (items VU.! i))) + fst (items VU.! i))
上記のように書き直してメモ化をやめると、サンプルのテストケースはエラーを出さずにすべて通りました。
もちろんメモ化をやめたせいで時間制限を超えやすくなってるので、そのまま提出してもACにはならないでしょう。根本的なアルゴリズムの見直しが必要です。
投稿2020/02/01 16:47
総合スコア2047
なるほど。C++などの言語では、ForループでN+1*Wの二次元配列を作ってそれぞれの要素に対して測っていたので、同じ方針で行きましたが、メモ化する配列のサイズが大きくなりすぎているのですね。
この問題をHaskellで得ならば、やはりMArrayなどを使ったほうが良いのでしょうか？
これは言語やデータ構造でどうにかなるものではなくて、この問題の制約に対してこのアルゴリズムではうまくいかないということです。
Wの最大値が10億ととても大きいことに注意してください。
あなたの回答
tips
プレビュー
