代码之家 › 专栏 › 技术社区 › Adam

Haskell递归速度慢,有什么陷阱?

optimization haskell

1

Adam · 技术社区 · 6 年前

我是哈斯克尔的初学者

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,因此我想尽可能修复此代码,并知道为什么我不能这样编写它)

编辑:食谱中的列表变大

1 回复 | 直到 6 年前

1

Adam 6 年前

我遵循了评论中的建议;当您进行大量随机访问时,不要使用列表数据结构。所以我用序列替换了列表 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小时到秒)。感谢评论员!