由于切片，我的 Go 递归函数无法按预期工作

Question

我写了一个函数，但我似乎找不到错误在哪里：

函数change是这样工作的：

输入 15（目标值），可能值为 [1, 5, 10, 25, 100] 应该 return [5, 10]。那是因为要达到目标值 15，组成该目标数字的最少数字是 10 和 5

我使用缓存机制，因为它是一个递归函数并且会记住已经计算过的值。

func Change(coins []int, target int, resultsCache map[int][]int) ([]int, error) {
    if val, ok := resultsCache[target]; ok {
        return val, nil
    }
    if target == 0 {
        return make([]int, 0), nil
    }
    if target < 0 {
        return nil, errors.New("Target can't be less than zero")
    }

    var leastNumOfCoinChangeCombinations []int
    for _, coin := range coins {
        remainder := target - coin
        remainderCombination, _ := Change(coins, remainder, resultsCache)

        if remainderCombination != nil {
            combination := append(remainderCombination, coin)
            if leastNumOfCoinChangeCombinations == nil || len(combination) < len(leastNumOfCoinChangeCombinations) {
                leastNumOfCoinChangeCombinations = combination
            }
        }
    }
    if leastNumOfCoinChangeCombinations == nil {
        return nil, errors.New("Can't find changes from coin combinations")
    }
    sort.Ints(leastNumOfCoinChangeCombinations)
    resultsCache[target] = leastNumOfCoinChangeCombinations
    return leastNumOfCoinChangeCombinations, nil
}

但是缓存有一些异常行为，例如，如果我想稍后在缓存中使用值 12，而不是 [2,5,5]，我会得到 [1 2 5]。不知道我哪里出错了。（但最初它是正确计算和存储的，不知道它是如何改变的）。

这是我用于故障排除的 playground：

https://play.golang.org/p/Rt8Sh_Ul-ge

Answer 1

您遇到了一个相当普遍但有时难以发现的由切片工作方式引起的问题。在进一步阅读之前，可能值得浏览博客 post Go Slices: usage and internals. The issue stems from the way append can reuse the slices underlying array as per this quote from the spec:

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large underlying array that fits both the existing slice elements and the additional values. Otherwise, append re-uses the underlying array.

下面的代码提供了正在发生的事情的简单演示：

package main

import (
    "fmt"
    "sort"
)

func main() {
    x := []int{2, 3}
    x2 := append(x, 4)
    x3 := append(x2, 1)
    fmt.Println("x2 before sort", x2)
    sort.Ints(x3)
    fmt.Println("x2 after sort", x2)
    fmt.Println("x3", x3)
    fmt.Println("x2 cap", cap(x2))
}

结果是（playground）：

x2 before sort [2 3 4]
x2 after sort [1 2 3]
x3 [1 2 3 4]
x2 cap 4

结果可能不是您所期望的 - 为什么在我们对 x3 进行排序时 x2 发生了变化？发生这种情况的原因是 x2 的后备数组的容量为 4（长度为 3），而当我们 append 1 时，新切片 x3 使用相同的后备数组（容量为 4 , 长度 4).当我们更改 x2 使用的支持数组部分时，这只会成为一个问题，当我们在 x3 上调用 sort 时会发生这种情况。

所以在你的代码中，你正在向地图添加一个切片，但是它的支持数组在 Change returns 的那个实例之后被改变（append/sort 最终发生得很好就像上面的例子一样）。

有几种方法可以解决这个问题；删除排序可以解决问题，但可能不是您想要的。更好的选择是复制切片；您可以将 combination := append(remainderCombination, coin) 替换为：

combination := make([]int, len(remainderCombination)+1)
copy(combination , remainderCombination)
combination[len(remainderCombination)] = coin

或更简单的（但可能不那么容易掌握 - playground）：

combination := append([]int{coin}, remainderCombination...)

由于切片，我的 Go 递归函数无法按预期工作

My Go recursive function not working as expected due to slices

go

slice