Утечка пространства вверх по DP в Haskell

Question

Извиняюсь, если это слишком конкретно, я новичок здесь и не совсем уверен, что является разумным. Я часами бьюсь над этой проблемой, и мне нечего показать. Следующий код - моя реализация задачи конкурентного программирования.

module Main where

import Data.List (foldl', groupBy)
import Debug.Trace

type Case = (Int, [(Int, Int)])
type Soln = Int

main = interact handle

handle :: String -> String
handle = fmt . solve . parse

fmt :: Soln -> String
fmt s = (show s) ++ "\n"

parse :: String -> Case
parse s = (l, fs)
  where
    (l:_:fs') = (map read) $ words s
    fs = pairs fs'

pairs :: [a] -> [(a, a)]
pairs [] = []
pairs (a:b:s) = (a, b):(pairs s)

solve :: Case -> Soln
solve c@(l, fs) = last $ foldl' run [0..l] f
  where
    f = concat $ map rep $ map combine $ groupBy samev fs
    samev a b = (snd a) == (snd b)
    combine a = (sum $ map fst $ a, snd $ head $ a)
    rep (n, v) = replicate (min n (l `div` v)) v

run :: [Int] -> Int -> [Int]
run b v = (take v b) ++ (zipWith min b (drop v b))
-- run b v = (take v b) ++ (zipMin b (drop v b))

zipMin :: [Int] -> [Int] -> [Int]
zipMin [] _ = []
zipMin _ [] = []
zipMin (a:as) (b:bs) = (min a b):(zipMin as bs)

Намерение состоит в том, что это работает как восходящее динамическое программирующее решение, генерирующее каждую строку таблицы DP из предыдущей с использованием сгиба в execute Теоретически GHC должен иметь возможность оптимизировать все старые строки таблицы. Тем не менее, запуск этой программы на умеренно большом входе с примерно l = 2000 а также length f = 5000Я получаю это:

> time ./E < E.in 
0
1.98user 0.12system 0:02.10elapsed 99%CPU (0avgtext+0avgdata 878488maxresident)k
0inputs+0outputs (0major+219024minor)pagefaults 0swaps

Это использует 878 МБ памяти на пике! Таблица, которую я генерирую, составляет всего 10000 Ints, и теоретически мне нужна только одна строка за раз! Кажется очевидным, что это какая-то утечка грома или другая утечка пространства. Профилирование показывает, что run потребляет 99% общего времени выполнения и памяти. Копание далее показало, что 98% этого было в zipWith вызов. Интересно, что замена звонка на zipWith min с моим обычаем zipMin Функция дает значительное улучшение:

> time ./E < E.in 
0
1.39user 0.08system 0:01.48elapsed 99%CPU (0avgtext+0avgdata 531400maxresident)k
0inputs+0outputs (0major+132239minor)pagefaults 0swaps

Это всего лишь 70% времени работы и 60% памяти! Я пробовал все виды, чтобы сделать эту работу. я знаю (++) это вообще плохая идея, поэтому я заменил списки в run с Data.Sequence.Seq Int... и он стал медленнее и использовал больше памяти. У меня нет особого опыта работы с Хаскеллом, но я нахожусь в конце моего остроумия здесь. Я уверен, что ответ на эту проблему существует где-то на SO, но я слишком новичок в Haskell, чтобы найти его, кажется.

Любая помощь, которую вы можете предложить, очень ценится. Я хотел бы объяснить, что именно я сделал неправильно, как диагностировать это в будущем и как это исправить.

Заранее спасибо.

РЕДАКТИРОВАТЬ:

После следования превосходному совету Стивена и замены моих списков несвязанными векторами производительность... ну... значительно улучшилась:

> time ./E < E.in 
0
0.01user 0.00system 0:00.02elapsed 80%CPU (0avgtext+0avgdata 5000maxresident)k
24inputs+0outputs (0major+512minor)pagefaults 0swaps

Answer 1

Итак, используя foldl' Вы убедились, что аккумулятор будет в WHNF. Размещение списка в WHNF оценивает только первый элемент списка. Остальная часть списка существует в виде thunk, и будет передаваться как thunk для последующих вызовов вашей карты. Поскольку вас интересуют сразу несколько позиций в списке (то есть вы отбрасываете некоторые его части в zipWith) большие части списков сохраняются от предыдущих итераций.

Структура, которая вам нужна, - это распакованный вектор. Распакованный вектор гарантирует, что все максимально строго и будет работать в гораздо меньшем объеме памяти.