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

huangapple go评论108阅读模式
英文:

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 &lt; 0 {
		return nil, errors.New(&quot;Target can&#39;t be less than zero&quot;)
	}

	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) &lt; len(leastNumOfCoinChangeCombinations) {
				leastNumOfCoinChangeCombinations = combination
			}
		}
	}
	if leastNumOfCoinChangeCombinations == nil {
		return nil, errors.New(&quot;Can&#39;t find changes from coin combinations&quot;)
	}
	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:

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

答案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函数返回后,它的底层数组被修改了(appendsort的过程与上面的示例几乎相同)。

你可以通过几种方法来解决这个问题;删除排序可能会解决问题,但可能不是你想要的。一个更好的选择是复制切片;你可以用以下代码替换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 (
	&quot;fmt&quot;
	&quot;sort&quot;
)

func main() {
	x := []int{2, 3}
	x2 := append(x, 4)
	x3 := append(x2, 1)
	fmt.Println(&quot;x2 before sort&quot;, x2)
	sort.Ints(x3)
	fmt.Println(&quot;x2 after sort&quot;, x2)
	fmt.Println(&quot;x3&quot;, x3)
	fmt.Println(&quot;x2 cap&quot;, 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...)

huangapple
  • 本文由 发表于 2021年8月8日 09:48:35
  • 转载请务必保留本文链接:https://go.coder-hub.com/68697240.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定