dongyong9224 2018-01-28 13:50
浏览 37
已采纳

如何理解以下有关golang slice的代码?

Recently I found some code that I can't understand, below is my code:

func subsetsWithDup(nums []int) [][]int {
    if len(nums) == 0 {
        return [][]int{[]int{}}
    }
    sort.Ints(nums)
    result := [][]int{}
    backtracking(nums, &result, []int{}, 0)
    return result
}

func backtracking(nums []int, result *[][]int, tempList []int, start int) {
    *result = append(*result, tempList)
    for i := start; i < len(nums); i++ {
        if i > start && nums[i] == nums[i-1] {
            continue
        }
        tempList = append(tempList, nums[i])
        backtracking(nums, result, tempList, i+1)
        tempList = tempList[:len(tempList)-1:len(tempList)-1]
    }
}

and another approach:

func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums)
    return subsets(nums, []int{}, [][]int{})
}

func subsets(nums []int, result []int, results [][]int) [][]int {    
    newR := make([]int, len(result))
    copy(newR, result)
    results = append(results, newR)

    if len(nums) == 0 {return results}

    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i] == nums[i - 1] {continue}
        result = append(result, nums[i])
        results = subsets(nums[i + 1:], result, results)
        result = result[:len(result) - 1]
    }

    return results
}

In the first approach, I use the following code :

tempList = tempList[:len(tempList)-1:len(tempList)-1]

it works, but if I change it to:

tempList = tempList[:len(tempList)-1]

it dose not work.In the second approach which use copy function also works. I want to know what happens behind the code, any help is appreciated, thanks.

  • 写回答

1条回答 默认 最新

  • dongzexi5125 2018-01-28 14:31
    关注

    In Go, slice is a pointer type to maintain information about underlying array, so change of the underlying array would cause changes of the slice value, which sometimes might be surprising.

    The second part of the puzzle is that append modifies the underlying array if the cap of the slice is sufficient. Document:

    The append built-in function appends elements to the end of a slice. If it has sufficient capacity, the destination is resliced to accommodate the new elements. If it does not, a new underlying array will be allocated. Append returns the updated slice. It is therefore necessary to store the result of append, often in the variable holding the slice itself.

    So in you failed attempt, tempList = append(tempList, nums[i]) will possibly change value of previously stored slices in result.

    On the other hand, the second approach creates a new slice with new underlying array and copy to it explictly, so the error is avoided. The first approach is more subtle, as it use a full slice expressions: tempList[:len(tempList)-1:len(tempList)-1]. The code limits the new slice's cap so append would have to allocate a new underlying array each time instead of using the orignal one.

    More about full slice expressions(spec):

    For an array, pointer to array, or slice a (but not a string), the primary expression

    a[low : high : max]
    

    constructs a slice of the same type, and with the same length and elements as the simple slice expression a[low : high]. Additionally, it controls the resulting slice's capacity by setting it to max - low. Only the first index may be omitted; it defaults to 0. After slicing the array a

    a := [5]int{1, 2, 3, 4, 5}
    t := a[1:3:5]
    

    the slice t has type []int, length 2, capacity 4, and elements

    t[0] == 2
    t[1] == 3
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥15 state显示变量是字符串形式,但是仍然红色,无法引用,并显示类型不匹配
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗