英文:
My Go recursive function not working as expected due to slices
问题
我写了一个函数,但是似乎找不到错误在哪里:
函数change
的工作原理如下:
输入为15(目标值),可能的值为[1, 5, 10, 25, 100],应返回[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("目标值不能小于零")
}
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("无法找到硬币组合的变化")
}
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
英文:
I have written a function and I can't seem to find where the bug is:
The function change
works like this:
An input of 15 (target value) with possible values of [1, 5, 10, 25, 100] should return [5, 10]. That's because to reach a target value of 15, the least amount of numbers to make up that target number is to have a 10 and 5
I use a caching mechanism, as it is a recursive function and remembers the values that have already been calculated.
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
}
The cache however have some abnormal behaviour, for example if I want to use the value of 12 in the cache later, instead of getting [2,5,5], I get [1 2 5] instead. Not sure where I went wrong. (but initially it was calculated and stored correctly, not sure how it got changed).
Here is a playground I used for troubleshooting:
答案1
得分: 4
你遇到了一个相当常见但有时很难发现的问题,这是由切片的工作方式引起的。在继续阅读之前,最好先浏览一下博客文章Go Slices: usage and internals。问题源于append
函数可以根据规范中的以下引用重用切片的底层数组:
如果切片
s
的容量不足以容纳额外的值,append
会分配一个新的足够大的底层数组,该数组同时适应现有切片元素和额外的值。否则,append
会重用底层数组。
下面的代码提供了一个简单的演示:
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
函数返回后,它的底层数组被修改了(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...)
英文:
You are encountering a fairly common, but sometimes difficult to spot, issue caused by the way slices work. Before reading further it's probably worth scanning the blog 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.
The below code provides a simple demonstration of what is occurring:
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))
}
The results are (playground):
x2 before sort [2 3 4]
x2 after sort [1 2 3]
x3 [1 2 3 4]
x2 cap 4
The result is probably not what you expected - why did x2
change when we sorted x3
? The reason this happens is that the backing array for x2
has a capacity of 4 (length is 3) and when we append
1 the new slice x3
uses the same backing array (capacity 4, length 4). This only becomes an issue when we make a change to the portion of the backing array used by x2
and this happens when we call sort
on x3
.
So in your code you are adding a slice to the map but it's backing array is then being altered after that instance of Change
returns (the append/sort ends up happening pretty much as in the example above).
There are a few ways you can fix this; removing the sort will do the trick but is probably not what you want. A better alternative is to take a copy of the slice; you can do this by replacing combination := append(remainderCombination, coin)
with:
combination := make([]int, len(remainderCombination)+1)
copy(combination , remainderCombination)
combination[len(remainderCombination)] = coin
or the simpler (but perhaps not as easy to grasp - playground):
combination := append([]int{coin}, remainderCombination...)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论