Haskell递归缓慢，有什么陷阱? [英] Haskell recursion slow, what's the pitfall?

问题描述

我是Haskell的初学者

I'm very much a beginner in 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天)的解决方案.该代码可产生正确的结果，但速度慢得令人发指.

The above piece of code is part of a recursion which I omitted. The addRecipes is called again and again in a recursive call. This is a solution to an advent of code problem (AoC 2018 day 14). The code produces the correct result but is cripplingly slow.

我只是想了解问题出在哪里，在上面的代码中什么效率低下?

I'm just trying to learn where the problem lies, what is horribly inefficient in the code above?

我试图优化掉 ++ -operator并将其替换为:并将其与数字调用结合在一起.我知道 ++ 比:慢，但这是真的吗?(请记住，我正在学习Haskell，所以我想尽可能修复此代码，并知道为什么我不能这样写)

I've tried optimizing away the ++-operator and replace it with a : and combining things with the digits call. I know the ++ is slower than the : but is that really it? (Remember, i'm learning Haskell so I want to fix this code if possible and know why I can't write it like this)

食谱"中的列表会增加并变大

The list in Recipes grows and becomes large

推荐答案

我遵循了评论中发布的建议；进行大量随机访问时，请勿使用列表数据结构.因此，我将列表替换为Sequence http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Sequence.html

I followed the advice posted in the comments; Do not use a the list data structure when you make a lot of random accesses. So I replaced the list with with 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个小时到几秒钟).谢谢评论者！

It worked and the run time is now reasonable (from 1 hour to seconds). Thanks commenters!

这篇关于Haskell递归缓慢，有什么陷阱?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！