Рекурсия Haskell медленная, в чем подвох?

Я очень новичок в Haskell

data Recipes = Recipes Int Int Int [Int] deriving(Show) 

addRecipes :: Recipes -> Recipes
addRecipes (Recipes t e1 e2 list) = 
    let (e1c, e2c) = (list !! e1, list !! e2)
        newVal = e1c + e2c
        newList = list ++ (digits $ newVal)
        e1n = calcNewPos e1 e1c newList
        e2n = calcNewPos e2 e2c newList
    in Recipes t e1n e2n newList

calcNewPos :: Int -> Int -> [Int] -> Int    
calcNewPos i i2 list = (i + i2 + 1) `mod` (length list)

-- Borrowed:
-- https://stackoverflow.com/questions/3963269/split-a-number-into-its-digits-with-haskell
digits :: Int -> [Int]
digits = map (read . (:[])) . show

Приведенный выше фрагмент кода является частью рекурсии, которую я пропустил. addRecipes вызывается снова и снова в рекурсивном вызове. Это решение проблемы появления кода (AoC 2018, день 14). Код дает правильный результат, но ужасно медленный.

Я просто пытаюсь понять, в чем проблема, что ужасно неэффективно в приведенном выше коде?

Я попытался оптимизировать ++-оператор и заменить его на : и комбинировать вещи с цифровым вызовом. Я знаю, что ++ медленнее, чем :, но так ли это? (Помните, я изучаю Haskell, поэтому я хочу исправить этот код, если это возможно, и знаю, почему я не могу написать его так)

Редактировать: список в рецептах растет и становится большим


optimization haskell
person Adam    schedule 16.12.2018    source источник
comment
Если вам нужно много произвольного доступа, например list !! n или добавление list ++ something, базовый список не является подходящей структурой данных. Трудно подсказать, что использовать, не понимая общей картины. Возможно, достаточно массива или нужны Seq/Vector. Может быть, можно обойтись и без случайного доступа, и тогда со списками все в порядке.   -  person chi    schedule 16.12.2018
comment
Хм, хорошо, adventofcode.com/2018/day/14 вот головоломка, если интересно.. .Но это может быть полезно, я изучу !!, может быть, я смогу как-то удалить его.   -  person Adam    schedule 16.12.2018
comment
После того, как я закончил эту задачу, я понял, что вся работа выполняется в конце последовательности, и поэтому вы, вероятно, можете обойтись без использования только списка, если будете хранить его в обратном порядке. (И следите за длиной.) Но было бы легко ошибиться, и использование Seq будет намного проще.   -  person David Fletcher    schedule 16.12.2018
comment
Просто чтобы расширить комментарий @DavidFletcher, Seq относится к hackage .haskell.org/package/containers-0.6.0.1/docs/   -  person Paul Johnson    schedule 16.12.2018
comment
Это работало с Seq! 1ч -> 2 сек. Спасибо, однако я получаю: getMBlocks: Ошибка VirtualAlloc MEM_COMMIT: файл подкачки слишком мал для завершения этой операции. в моей рекурсии endCondition: Seq.take 6 (Seq.reverse seq) == part2Input = Seq.length seq - 5. Я сам отвечу, но если у вас есть указания на это последнее препятствие, я возьму их! :)   -  person Adam    schedule 16.12.2018

Ответы (1)


arrow_upward
1
arrow_downward

Я последовал совету, опубликованному в комментариях; Не используйте структуру данных списка, когда вы делаете много случайных доступов. Поэтому я заменил список на Sequence http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Sequence.html

import qualified Data.Sequence as Seq

data Recipes = Recipes Int Int Int (Seq.Seq Int) deriving(Show) 

addRecipes :: Recipes -> Recipes
addRecipes (Recipes t e1 e2 seq) = 
let (e1c, e2c) = (Seq.index seq e1, Seq.index seq e2)
    newVal = e1c + e2c
    newSeq = (Seq.><) seq (Seq.fromList (digits newVal))
    e1n = calcNewPos e1 e1c newSeq
    e2n = calcNewPos e2 e2c newSeq
in Recipes t e1n e2n newSeq

calcNewPos :: Int -> Int -> (Seq.Seq Int) -> Int    
calcNewPos i i2 seq = (i + i2 + 1) `mod` (Seq.length seq)

Это сработало, и время выполнения теперь разумно (от 1 часа до секунд). Спасибо комментаторам!

person Adam    schedule 16.12.2018
comment
Вы можете написать (Seq.><) seq (Seq.fromList (digits newVal)) как seq Seq.>< Seq.fromList (digits newVal). - person melpomene; 16.12.2018