arrays - 关于附加内置函数的一些问题
问题描述
package main
import (
"fmt"
)
func main() {
result := subsets([]int{9,3,0,1,2})
fmt.Println(result)
}
func subsets(nums []int) [][]int {
result := [][]int{}
var fun func([]int, int)
fun = func (preSets []int, start int) {
// fmt.Println(start, preSets, result)
result = append(result, preSets)
// fmt.Println(result)
for idx := start; idx < len(nums); idx++ {
tmp := nums[idx]
newSet := append(preSets, tmp)
fun(newSet, idx+1)
newSet = newSet[:len(newSet) - 1]
}
}
fun([]int{}, 0)
return result
}
我想找到一个切片的子集,并认为上面的代码应该可以工作。但它给了我以下输出
[[] [9] [9 3] [9 3 0] [9 3 0 2] [9 3 0 1 2] [9 3 0 2] [9 3 1] [9 3 1 2] [9 3 2] [9 0] [9 0 1] [9 0 1 2] [9 0 2] [9 1] [9 1 2] [9 2] [3] [3 0] [3 0 1] [3 0 1 2] [3 0 2] [3 1] [3 1 2] [3 2] [0] [0 1] [0 1 2] [0 2] [1] [1 2] [2]]
第五片应该是[9 3 0 1],但它是[9 3 0 2],我每一步都打印结果,我发现第五片在第七片时从[9301]变成了[9302] [9302] 是附加的,我认为它应该与切片下的数组存储有关,但是为什么
解决方案
我认为[问题是]与切片下的数组存储有关
是的。
但为什么
append
功能:
- 有时会重新使用原始的后备数组,但是
- 有时会创建一个新的支持数组并将原始值复制到新数组。
关于何时执行这两个中的一个,没有做出任何承诺。
当它重新使用原始数组时,您会遇到您不喜欢的行为。当它创建一个新数组时,您会遇到您想要的行为。由于您想要复制行为,您可以简单地编写自己的“始终复制”代码并获得您想要的行为。但是,一个更小的更改是替换:
result = append(result, preSets)
和:
result = append(result, unshare(preSets))
函数unshared
定义为:
func unshare(a []int) []int {
tmp := make([]int, len(a))
copy(tmp, a)
return tmp
}
如果你试图向自己解释为什么你得到了你得到的确切结果,这有点棘手,因为你没有得到任何关于何时创建新的支持数组以及何时重用现有的支持数组的承诺——但它是可以解释的,如果你做出以下两个假设:append
append
如果没有必要,永远不要复制后备数组;和- 当
append
确实进行复制时,它有时会因某些因素过度分配新的后备数组。
也就是说,append
行为或多或少像这样,当然除了这个特定于[]int
:
func xappend(orig []int, add []int) []int {
has := len(orig)
needed := has + len(add)
// If we can fit the added elements in, do that now.
if cap(orig) >= needed {
fmt.Println("copy in place")
orig = orig[:needed]
copy(orig[has:needed], add)
return orig
}
newSize := undocumentedFunction(has, cap(orig), needed)
fmt.Println("make new, size", newSize)
new := make([]int, needed, newSize)
copy(new, orig)
copy(new[has:needed], add)
return new
}
func undocumentedFunction(oldCap, oldLen, newCap int) int {
twiceAsMuch := oldCap + oldCap
if newCap > twiceAsMuch {
return newCap
}
// 2x old capacity is enough, but
// we'll tweak this in various ways.
// The exact tweaks might change at any time.
if oldLen < 1024 {
return twiceAsMuch
}
panic("didn't copy this part")
}
这个“未记录的函数”是运行时系统的一部分,它与编译器协作。您可以在此处查看其实际代码(注意:此链接有时可能会中断或转到错误的行)。
( Go Playground 上的示例可运行代码。)