切片使用不当会导致意想不到的副作用

我有以下函数生成给定数组的所有子集。

这个想法很简单 - 我从一个包含空集(切片(的结果数组开始，对于输入数组中的每个元素，nums遍历所有以前生成的集合，将当前元素nums添加到其中，并将生成的新集合添加回结果数组。没什么特别有趣的。

func subsets(nums []int) [][]int {
result := [][]int{{}}
for _, n := range nums {
newSets := [][]int{}
for _, set := range result {
newSets = append(newSets, append(set, n))
}
result = append(result, newSets...)
}
return result
}

问题是使用append(newSets, append(set, n))会损坏result片，set是其中的成员。我用一些调试代码(见下文(稍微修改了函数，还发现了一种不会导致相同行为的解决方法(注释代码(。

我非常怀疑这是由通过引用传递而不是复制的东西引起的(我将newSets元素附加到result(。问题是我找不到它。:(我从不在迭代它的循环中更改结果。我还为每个循环使用新的newSets实例。所以我不确定是什么原因造成的。请指教。:)

func subsets(nums []int) [][]int {
result := [][]int{{}}
for _, n := range nums {
newSets := [][]int{}
var before, after []int
for _, set := range result {
lastResultIdx := len(result)-1
if lastResultIdx > 0 {
before = make([]int, len(result[lastResultIdx]))
copy(before, result[lastResultIdx])
}
//ns := []int{}
//for _,v := range set {
//  ns = append(ns, v)
//}
//ns = append(ns, n)
//newSets = append(newSets, ns)
newSets = append(newSets, append(set, n))
if lastResultIdx > 0 {
after = result[lastResultIdx]
if before[len(before)-1]!=after[len(after)-1] {
fmt.Println(n, "before", before, "after", after)
}
}
}
result = append(result, newSets...)
}
return result
}
func main() {
subsets([]int{0, 1, 2, 3, 4})
}

问题就在这里：

append(newSets, append(set, n))

问题不在于它是一个嵌套的追加。问题是你假设append(set,n)会返回一个新的切片。情况并非总是如此。切片是数组上的视图，当您向切片添加新元素时，如果添加未导致数组重新分配，则返回的切片与您传入的切片相同，len字段递增。因此，当您浏览结果数组时，您正在修改已经存在的元素，同时再次添加它们，就好像它们是不同的结果一样。

要解决，当您获取result的元素时，创建一个新切片，将result的元素复制到其中，附加新元素，然后将新切片添加到result。

问题很简单：append接受切片参数([]T用于某些类型的T(，当然还有要附加的元素，并返回[]T结果。但是[]T，如果不是零，则由两部分组成：指向某个后备阵列并携带当前长度和容量的切片标头，以及后备阵列。当append完成其工作时，它有一个选择：

就地修改后备阵列，

并返回重用现有后备阵列的新片标头，或者
原始值复制到新的后备阵列，并返回使用新后备阵列的新切片标头。

每当append复制后备阵列时，您的代码都可以工作。每当它重用后备数组时，您的代码可能会也可能不会工作，具体取决于其他切片标头是否使用相同的后备数组。

例如，假设您的后备阵列的长度为 5，其中一个现有的切片标头读取"长度 1，容量 5"，后备数组的元素 0 为零。也就是说，现有的切片标题h包含[0]. 现在你打电话给append(h, 1). 追加操作重用后备数组并将1放入第二个元素中，并返回包含[0, 1]的新切片标头h1。现在你再次取h，附加2，并制作一个双元素切片h2保持[0, 2]。但是这重用了h1重用的相同支持数组，所以现在h1也持有[0, 2]。

要在不对算法进行太多修改的情况下解决问题，您需要：

始终复制的append变体，或
的变体将一个 int 附加到始终复制的整数切片中。

后者更简单：

func setPlusInt(set []int, n int) []int {
return append(append([]int(nil), set...), n)
}

这使您可以替换现有代码的一行。

(我在这里做了另一个微不足道的更改，并添加了足够的内容以在Go Playground中提供一个工作示例。

(另一种解决方案是将您自己的每个切片标题设置为不提供额外容量，以便append必须始终复制。我还没有说明这种方法。

相关内容

最新更新

热门标签：