Неисправности скорости подсчета списка Haskell
Я пытаюсь оптимизировать скорость выполнения своей программы, и я натолкнулся на некоторые интересные результаты, и я надеюсь, что кто-то сможет ответить. Кажется, что внесение небольших изменений в одно из моих понятий списка резко меняет скорость выполнения, но я не знаю почему.
Вот моя программа, как сейчас.
import Data.Ord
import Control.Monad
import Data.Array
import Data.Ix
import qualified Data.Map as M
import qualified Data.Set as S
import Data.List (minimumBy, foldl')
arrayMatrix lists = let rlen = length lists
clen = length $ head lists
r = ((1,1), (rlen, clen))
in array r . zip (range r) $ concat lists
a_star start goal h m = search S.empty (S.singleton start)
(M.singleton start (m ! start))
$ M.singleton start (m ! start + h ! start)
where neighbors (r,c) = filter (inRange $ bounds m) [ (r-1,c), (r,c+1), (r+1,c) , (r,c-1)]
search closed open gs fs
| S.null open = 0
| current == goal = gs M.! goal
| otherwise = let open' = S.delete current open
closed' = S.insert current closed
neighbs = [(n, ts) | n <- neighbors current, S.notMember n closed
, let ts = gs M.! current + m ! n ]
actionable = filter (\(n,ts) -> S.notMember n open' || ts < (gs M.! n)) neighbs
(op',gs',fs') = foldl' (\(o,ng,nf) (n,ts) -> (S.insert n o, M.insert n ts ng, M.insert n (ts + h ! n) nf)) (open',gs,fs) actionable
in search closed' op' gs' fs'
where current = minimumBy (comparing (fs M.!)) $ S.toList open
main = do
matrix <- liftM (arrayMatrix . map (read . ('[':) . (++"]")) . lines)
$ readFile "matrix.txt"
let bds = bounds matrix
ulim = snd bds
heuristic = let m = minimum $ elems matrix
in listArray bds . map (\(r,c) -> (uncurry (+) ulim)-r-c) $ range bds
print $ a_star (1,1) ulim heuristic matrix
Сейчас программа работает на моем компьютере ~ 350 мс (скомпилирована с GHC 7.8.2-O2) с matrix.txt, предоставленным Проект Эйлера.
Если я изменю соседи из
neighbs = [(n, ts) | n <- neighbors current, S.notMember n closed
, let ts = gs M.! current + m ! n ]
к
neighbs = [(n, gs M.! current + m ! n) | n <- neighbors current, S.notMember n closed]
время выполнения увеличивается до более 1сек.
Другие незначительные изменения, такие как перемещение фильтра на следующей строке в понимание списка, дают тот же результат: ~ 1 с.
Может ли кто-нибудь объяснить, почему это происходит?
EDIT: похоже, этого не происходит в более ранних версиях GHC. Я пробовал GHC 7.6.3, и каждый из них выполнял примерно то же самое.
Я включил дампы из ghc -O2 -ddump-simpl -dsuppress-all, как это было предложено cdk. Я действительно не знаю, на что я смотрю, поэтому, если кто-то сможет интерпретировать, это будет большой помощью, спасибо.
Ссылка на обе дампы
EDIT2 (Ответ на Прийатам): Я не думаю, что дело. Я изменил
neighbs = [(n, ts) | n <- neighbors current, S.notMember n closed
, let ts = gs M.! current + m ! n ]
actionable = filter ((n,ts) -> S.notMember n open' || ts < (gs M.! n)) neighbs
к
neighbs = [(n, gs M.! current + m ! n) | n <- neighbors current, S.notMember n closed ]
actionable = filter ((n,!ts) -> S.notMember n open' || ts < (gs M.! n)) neighbs
с помощью BangPatterns, и это все еще работает чуть больше секунды. Фактически, изменение neigbs из
neighbs = [(n, ts) | n <- neighbors current, S.notMember n closed
, let ts = gs M.! current + m ! n ]
к
neighbs = [(n, ts) | n <- neighbors current, S.notMember n closed
, let !ts = gs M.! current + m ! n ] -- Added bang before ts
увеличивает время выполнения до более чем 1сек.
Ответы
Ответ 1
Здесь можно догадаться, что произошло с let ts = vs. let !ts =. я
получил его от просмотра вывода -ddump-stranal (который выгружает
аннотации анализа строгости) и чтение Анализатор спроса в
GHC.
Разница между let !ts = и let ts = заключается в том, что если ts равно
внизу (т.е. undefined), то n не будет оцениваться вообще
потому что ts будет оценен первым, и оценка остановится. Это
что разница между двумя программами заключается в том, что пара
целые числа n строгие и распакованные в одной версии, но не в
другой (см. вывод -ddump-stranal и -ddump-simpl; ссылка
выше описывает выход).
Как !ts или не !ts влияет на строгость n? Я думаю, что если
ts является нижней, тогда программа должна завершиться с ошибкой перед оценкой n или
любой из его элементов (я не уверен, что он сам n :: (Int, Int) или
его элементы). Поэтому ghc, похоже, делает правильные вещи, чтобы сохранить n
нестрогий, когда ts требуется быть строгим, поскольку оценка n
первая и, возможно, неудача в другом месте может быть ошибкой.
Далее, как вы вынуждаете !ts не влиять на n? Обратите внимание, что ts
не может быть дном без n, являющимся нижним, если либо gs, current,
или m, как известно, не являются дном (это все элементы выражения, кроме n) и уже были оценены (я думаю, что M.! и ! могут
никогда не дно, не оценивая их аргументы в первую очередь). Поэтому нам нужно наложить условие "ts - это дно
n является нижней и уже оценен ", так что ghc знает, что сначала можно оценить n.
Мое решение: добавьте шаблоны ударов в current, gs и m. С моим ghc
7.8.2, это, похоже, решает проблему. Также кажется, что нужно принудительно выполнить только current.
Я не слишком уверен в первоначальном вопросе о перемещении выражения
ts в кортеж, но похожее решение работает.
P.S. Обратите внимание, что
filter (\x -> x > 5) [x | x <- [1..10]] == [x | x <- [1..10], x > 5]
поэтому в ваших списках neighbs и
actionable было бы проще привнести предикат фильтра в
представление самого списка так:
[(n, ts)
| n <- neighbors current
, S.notMember n closed
, let ts = gs M.! current + m ! n
, S.notMember n open' || ts < (gs M.! n)
]
Ответ 2
Это не полный ответ, так как мне не хватает информации о том, как let и контексты списка реализуются внутри.
Каждый элемент в neighbs является кортежем, а в WHNF сумма не оценивается строго. Это оставляет необоснованные громы, которые могут увеличить время выполнения.
Я предлагаю переписать второе определение с помощью seq без использования let, если возможно, посмотреть, падает ли время выполнения (в этом случае этот ответ, вероятно, будет правильным).
Прочитайте этот, чтобы понять, что такое WHNF.
