haskell - 我的Haskell代码中的堆栈溢出

Question

我想找到所有找零的组合。 1，2，5，10，20，50，100 und 200.（1 cent，2cent ..）
如果硬币超过500（5欧元），它应该给出-1。我的代码可以完美地与那些测试用例一起使用：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美分硬币，5 1美分硬币
1个5分硬币，5个1分硬币，1个5分硬币
2个1分硬币，1个5分硬币，2个1分硬币，1个5分硬币，1个1分硬币


以上所有示例均使用相同的硬币组合。他们都使用2个5美分硬币和5个1美分硬币，以不同的顺序计数。

我们可以通过始终以相同的顺序发行硬币来避免上述问题。这建议了一种简单的算法，用于从硬币列表中进行多少数量的特定数量的更改。我们可以使用第一类硬币中的一种，也可以承诺不再使用这种类型的硬币。

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个点以及向下的1个点。

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号运动和下方的1号运动。

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

如果我们发现有更好的顺序使用硬币（有一个），则不需要填写所有表格，但工作量大约相同。

我们可以使用 array package中 Array中的 Data.Array在Haskell中创建这样的表。

使用表格的总体计划将是-根据我们的函数 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]。

我们可以继续讨论如何使递归函数的“ tabling”，“ memoing”，“ memoizing”或“ dynamic programming”代码通用，但是我认为讨论将属于另一个问题。如果您想了解功能固定点的非常实际的用法，这是一个很好的主题。