我的haskell代码中的堆栈溢出

Question

我想找到换币的所有组合.1,2,5,10,20,50,100和200.(1分,2分..)如果硬币超过500(5欧元),它应该给-1.My代码与那些测试用例完美配合:numOfSplits 10 (11)numOfSplits 20(41)numOfSplits 100(4563).当我尝试使用numOfSplits 200或500的测试用例时,它会产生C堆栈溢出错误.我怎样才能使我的代码更好？

numOfSplits :: Integer -> Integer  
numOfSplits a  
    | (abs a) > 500 = -1  
    | (abs a) == 0 = 0  
    | otherwise = intzahler (makeChange [200,100,50,20,10,5,2,1] (abs a) 200)  

intzahler :: [[Integer]] -> Integer  
intzahler array  
    | array == [] = 0  
    | otherwise = 1 + intzahler (tail array)  

makeChange :: [Integer] -> Integer -> Integer -> [[Integer]]  
makeChange coins amount maxCoins  
    | amount < 0  = []  
    | amount == 0 = [[]]  
    | null coins  = []  
    | amount `div` maximum coins > maxCoins = [] -- optimisation  
    | amount > 0  =  
        do x <- coins  
           xs <- makeChange (filter (<= x) coins)  
                            (amount - x)  
                            (maxCoins - 1)  
           guard (genericLength (x:xs) <= maxCoins)  
           return (x:xs)

我将代码更改为此代码,我不再出现堆栈溢出错误,但现在我的代码工作得太慢了.例如:对于numOfSplits 500,它超过30分钟,我怎样才能更快地完成？

     numOfSplits :: Integer -> Integer  
numOfSplits a
    | (abs a) > 500 = -1
    | (abs a) == 0 = 0
    | otherwise = fromIntegral . length $ makeChange [200,100,50,20,10,5,2,1] (abs a) 

makeChange :: [Integer] -> Integer ->  [[Integer]]
makeChange coins amount 
   | amount < 0  = []
   | amount == 0 = [[]]
   | null coins  = []
   | amount > 0  =
        do x <- coins
          xs <- makeChange (filter (<= x) coins) (amount - x)
           return (x:xs)

Answer 1

快速解决此问题,从而避免耗尽计算机的资源(如堆栈),需要重复使用先前计算的部分答案.

让我们假设我们想解决一个类似的问题,我们试图找出我们可以使用1,2或5美分硬币赚15美分的方式.我们将面临两个问题 - 第一个是正确解决问题.第二是快速解决问题.

正确解决问题

为了正确解决问题,我们需要避免重新计算我们已经计算过的硬币组合.例如,我们可以通过以下方式赚取15美分:

• 2个五分硬币,5个1美分硬币
• 1美分硬币,5美分硬币,1美分硬币
• 2个1美分硬币,1个5美分硬币,2个1美分硬币,1个5美分硬币,1个1美分硬币

所有上述例子都使用相同的硬币组合.他们都使用2美分硬币和5美分硬币,按照不同的顺序计算.

我们可以通过始终以相同的顺序发行我们的硬币来避免上述问题.这表明我们可以通过多少种方式从硬币列表中进行一定程度的更改.我们可以使用第一种硬币中的一种,或者我们可以承诺再也不使用那种类型的硬币.

waysToMake 0 _             = 1
waysToMake x _     | x < 0 = 0 
waysToMake x []            = 0
waysToMake x (c:cs)        = waysToMake (x-c) (c:cs) + waysToMake x cs

前面的案例涵盖了边界条件.假设没有有问题的零或负值硬币,就有1办法制作0.有很多0方法可以做出负面(< 0)的改变.如果你没有可以改变的硬币类型,就没有办法改变.

让我们看看如果我们试图评估会发生什么waysToMake 15 [1,2,5].我们将评估每个waysToMake步骤以保持简短.

waysToMake 15 [1,2,5]

waysToMake 14 [1,2,5] + waysToMake 15 [2,5]

waysToMake 13 [1,2,5] + waysToMake 14 [2,5] + waysToMake 13 [2,5] + waysToMake 15 [5]

waysToMake 12 [1,2,5] + waysToMake 13 [2,5] + waysToMake 12 [2,5] + waysToMake 14 [5]
+ waysToMake 11 [2,5] + waysToMake 13 [5] + waysToMake 10 [5] + waysToMake 15 []

waysToMake 11 [1,2,5] + waysToMake 12 [2,5] + waysToMake 11 [2,5] + waysToMake 13 [5]
+ waysToMake 10 [2,5] + waysToMake 12 [5] + waysToMake 9 [5] + waysToMake 14 []
+ waysToMake 9 [2,5] + waysToMake 11 [5] + waysToMake 8 [5] + waysToMake 13 []
+ waysToMake 5 [5] + waysToMake 10 [] + 0

前三个步骤似乎并不太可疑,但我们已经遇到过waysToMake 13 [2,5]两次.在第四步骤中,我们看到waysToMake 12 [2, 5],waysToMake 11 [2, 5],waysToMake 13 [5]所有这些我们以前见过.我们可以看到,我们将重复生成的大多数其他表达式,这些表达式本身会生成重复表达式的表达式.啊; 我有限的脑力计算机已经抱怨说有太多的工作要做.我们可以寻找一个更好的订单来使用硬币(有一个),但它仍然会重复子问题,这本身会重复子问题,等等.

快速解决问题

有一种更快的方法可以做到这一点.每一步,我们将使用较少硬币而不使用该硬币的数字加在一起.让我们创建一个表,并在计算时记录每个结果.每一步,我们都需要从表格中的更左边开始的数字(使用第一枚硬币中的一张)和一张桌子下面的数字(不要使用任何第一枚硬币).我们最终会探索整个表格.我们可以从填充边界条件所覆盖的左边和底边的数字开始.

Coins\Change  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[1,2,5]       1  
  [2,5]       1 
    [5]       1 
     []       1 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

现在我们将添加可以从表中已有的数字计算的所有数字.使用5美分硬币需要左边5个点,以及第一个点.

Coins\Change  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[1,2,5]       1  
  [2,5]       1 
    [5]       1 0 0 0 0 1
     []       1 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

使用2美分的硬币需要左侧的2号运动,以及第一个位置.

Coins\Change  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[1,2,5]       1  
  [2,5]       1 0 1
    [5]       1 0 0 0 0 1 0 0 0 0  1
     []       1 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

使用1美分的硬币需要左边的1号位,以及第1点的位置.

Coins\Change  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[1,2,5]       1 1 
  [2,5]       1 0 1 0 1
    [5]       1 0 0 0 0 1 0 0 0 0  1  0  0  0  0  1
     []       1 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

我们再迈出一步.我们可以看到,在另外13个简单的步骤中,我们将计算顶行中15的数字,我们将完成.

Coins\Change  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[1,2,5]       1 1 2 
  [2,5]       1 0 1 0 1 1 1
    [5]       1 0 0 0 0 1 0 0 0 0  1  0  0  0  0  1
     []       1 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

这是所有步骤之后的表格.我的脑力计算机没有困难计算waysToMake 15 [1,2,5] = 18.

Coins\Change  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[1,2,5]       1 1 2 2 3 4 5 6 7 8 10 11 13 14 16 18
  [2,5]       1 0 1 0 1 1 1 1 1 1  2  1  2  1  2  2
    [5]       1 0 0 0 0 1 0 0 0 0  1  0  0  0  0  1
     []       1 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

如果我们找到了一个更好的订单来使用硬币(有一个)我们不需要填写所有的表格,但它的工作量大致相同.

我们可以用这样在Haskell一个表Array从Data.Array在阵列封装.

使用表的一般计划是 - 根据我们的函数定义一个表waysToMake.无论在何处waysToMake进入自身,都要在表格中查看结果.在路上我们有两个皱纹要处理.

第一个问题是Array需要将数组中的索引作为实例Ix.我们的硬币列表没有很好的数组索引.相反,我们可以用我们跳过的硬币数替换硬币列表.0对于第一行,1对于第二行,以及最后一行的硬币列表的长度.

第二个问题是我们希望超越桌子的边缘.我们可以定义一个特殊的查找过程来填充表外的部分0,我们可以更改代码,使它永远不会在表外看,或者我们可以创建一个超大的表的两倍大的表.我将跳过所有这些路由,并检查该值是否属于表的一部分.

waysToMake x coins = waysToMake' (x,0)
    where
        tabled = tableRange ((0,0),(x,length coins)) waysToMake'
        waysToMake' (n, s) = waysToMake'' n (drop s coins)
            where                    
                waysToMake'' 0  _              = 1
                waysToMake'' n  _     | n <  0 = 0
                waysToMake'' n []              = 0
                waysToMake'' n (c:cs)          = tabled (n-c, s) + tabled (n, s+1)

tableRange创建一个在某些范围内记忆其结果的函数.它构建了Array一个在这些边界内持有懒惰评估函数的结果.它返回的函数检查参数是否在边界范围内,如果是,则从表中查找结果,否则直接询问原始函数.

tableRange :: Ix a => (a, a) -> (a -> b) -> (a -> b)
tableRange bounds f = lookup
    where
        lookup x = if inRange bounds x then table ! x else f x
        table = makeArray bounds f

makeArray是一个便利函数,它使包含所提供函数的数组f应用于提供的每个索引bounds.

makeArray :: Ix i => (i, i) -> (i -> e) -> Array i e
makeArray bounds f = listArray bounds . map f $ range bounds

我们的代码现在几乎立即运行,即使对于更大的问题,例如waysToMake 10000 [200,100,50,20,10,5,2,1].

我们可以继续讨论如何对递归函数进行通用的"表格"或"备忘录"或"记忆"或"动态编程"代码,但我认为讨论属于不同的问题.如果你想了解一个非常实用的固定功能点,这是一个很好的主题.