V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
vzard
V2EX  ›  问与答

golang 切片的一个奇怪的现象

  •  
  •   vzard · 2020-10-31 21:27:10 +08:00 · 1081 次点击
    这是一个创建于 1466 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有如下求全排列代码:

    package main
    
    import (
    	"fmt"
    )
    
    func main() {
    	res := permute([]int{5,4,6,2})
    	fmt.Println(res)
    }
    
    var result [][]int
    func permute(nums []int) [][]int {
    	result = make([][]int,0)
    	track := make([]int,0)
    	trackBack(nums,track)
    	return result
    }
    
    func trackBack(nums []int, track []int) {
    	if len(track) == len(nums) {
    		//tmp := make([]int,len(nums))
    		//copy(tmp,track)
    		//result = append(result,tmp)
    		
    		result = append(result,track)
    		return
    	}
    
    	for _,i := range nums {
    		// 已经在路径中的剪枝剪掉
    		if isInSlice(track,i) {
    			continue
    		}
    		track = append(track,i)
    		trackBack(nums,track)
    		track = track[:len(track)-1]
    	}
    
    }
    
    func isInSlice(nums []int,item int) bool {
    	for _,i := range nums {
    		if i == item {
    			return true
    		}
    	}
    	return false
    }
    
    

    运行结果如下:

    [[5 4 2 6] [5 4 2 6] [5 6 2 4] [5 6 2 4] [5 2 6 4] [5 2 6 4] [4 5 2 6] [4 5 2 6] [4 6 2 5] [4 6 2 5] [4 2 6 5] [4 2 6 5] [6 5 2 4] [6 5 2 4] [6 4 2 5] [6 4 2 5] [6 2 4 5] [6 2 4 5] [2 5 6 4] [2 5 6 4] [2 4 6 5] [2 4 6 5] [2 6 4 5] [2 6 4 5]]
    

    由于切片底层都是公用一份内存,修改子切片的值也会影响到父切片,所以正常的使用方式应该是在每次 append 的时候要使用一个 tmp 切片来 copy 一个复制的值,然后 append tmp 切片,不然结果里的值都将会是最后 append 的元素的值(因为它们都是公用的一份内存数据),但是这个问题比较诡异的地方是,他只有相邻的两两元素是一样的,不符合预期,有大佬遇到过类似的问题么?

    1 条回复    2020-10-31 21:51:32 +08:00
    vzard
        1
    vzard  
    OP
       2020-10-31 21:51:32 +08:00
    找到原因了,是切片内存自动扩容和缩容的坑:
    ```
    // 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:
    // slice = append(slice, elem1, elem2)
    // slice = append(slice, anotherSlice...)
    // As a special case, it is legal to append a string to a byte slice, like this:
    // slice = append([]byte("hello "), "world"...)
    func append(slice []Type, elems ...Type) []Type
    ```
    当 cap 不够的时候会自动扩容,当多次执行`track = track[:len(track)-1]`这样的操作之切片又会自动缩容,每次扩容和缩容都会导致底层数组的内存重新申请,每两次内存重新申请之前的 append 的值就会一样,增加日志可以验证:
    ```
    Cap Before: 1, track: [5]
    Cap Before: 2, track: [5 4]
    Cap Before: 4, track: [5 4 6]
    Cap Before: 4, track: [5 4 6 2]
    Cap After: 4, track: [5 4 6]
    Cap After: 4, track: [5 4]
    Cap Before: 4, track: [5 4 2]
    Cap Before: 4, track: [5 4 2 6]
    Cap After: 4, track: [5 4 2]
    Cap After: 4, track: [5 4]
    Cap After: 2, track: [5]
    Cap Before: 2, track: [5 6]
    Cap Before: 4, track: [5 6 4]
    Cap Before: 4, track: [5 6 4 2]
    Cap After: 4, track: [5 6 4]
    Cap After: 4, track: [5 6]
    Cap Before: 4, track: [5 6 2]
    Cap Before: 4, track: [5 6 2 4]
    Cap After: 4, track: [5 6 2]
    Cap After: 4, track: [5 6]
    Cap After: 2, track: [5]
    Cap Before: 2, track: [5 2]
    Cap Before: 4, track: [5 2 4]
    Cap Before: 4, track: [5 2 4 6]
    Cap After: 4, track: [5 2 4]
    Cap After: 4, track: [5 2]
    Cap Before: 4, track: [5 2 6]
    Cap Before: 4, track: [5 2 6 4]
    Cap After: 4, track: [5 2 6]
    Cap After: 4, track: [5 2]
    Cap After: 2, track: [5]
    Cap After: 1, track: []
    Cap Before: 1, track: [4]
    Cap Before: 2, track: [4 5]
    Cap Before: 4, track: [4 5 6]
    Cap Before: 4, track: [4 5 6 2]
    Cap After: 4, track: [4 5 6]
    Cap After: 4, track: [4 5]
    Cap Before: 4, track: [4 5 2]
    Cap Before: 4, track: [4 5 2 6]
    Cap After: 4, track: [4 5 2]
    Cap After: 4, track: [4 5]
    Cap After: 2, track: [4]
    Cap Before: 2, track: [4 6]
    Cap Before: 4, track: [4 6 5]
    Cap Before: 4, track: [4 6 5 2]
    Cap After: 4, track: [4 6 5]
    Cap After: 4, track: [4 6]
    Cap Before: 4, track: [4 6 2]
    Cap Before: 4, track: [4 6 2 5]
    Cap After: 4, track: [4 6 2]
    Cap After: 4, track: [4 6]
    Cap After: 2, track: [4]
    Cap Before: 2, track: [4 2]
    Cap Before: 4, track: [4 2 5]
    Cap Before: 4, track: [4 2 5 6]
    Cap After: 4, track: [4 2 5]
    Cap After: 4, track: [4 2]
    Cap Before: 4, track: [4 2 6]
    Cap Before: 4, track: [4 2 6 5]
    Cap After: 4, track: [4 2 6]
    Cap After: 4, track: [4 2]
    Cap After: 2, track: [4]
    Cap After: 1, track: []
    Cap Before: 1, track: [6]
    Cap Before: 2, track: [6 5]
    Cap Before: 4, track: [6 5 4]
    Cap Before: 4, track: [6 5 4 2]
    Cap After: 4, track: [6 5 4]
    Cap After: 4, track: [6 5]
    Cap Before: 4, track: [6 5 2]
    Cap Before: 4, track: [6 5 2 4]
    Cap After: 4, track: [6 5 2]
    Cap After: 4, track: [6 5]
    Cap After: 2, track: [6]
    Cap Before: 2, track: [6 4]
    Cap Before: 4, track: [6 4 5]
    Cap Before: 4, track: [6 4 5 2]
    Cap After: 4, track: [6 4 5]
    Cap After: 4, track: [6 4]
    Cap Before: 4, track: [6 4 2]
    Cap Before: 4, track: [6 4 2 5]
    Cap After: 4, track: [6 4 2]
    Cap After: 4, track: [6 4]
    Cap After: 2, track: [6]
    Cap Before: 2, track: [6 2]
    Cap Before: 4, track: [6 2 5]
    Cap Before: 4, track: [6 2 5 4]
    Cap After: 4, track: [6 2 5]
    Cap After: 4, track: [6 2]
    Cap Before: 4, track: [6 2 4]
    Cap Before: 4, track: [6 2 4 5]
    Cap After: 4, track: [6 2 4]
    Cap After: 4, track: [6 2]
    Cap After: 2, track: [6]
    Cap After: 1, track: []
    Cap Before: 1, track: [2]
    Cap Before: 2, track: [2 5]
    Cap Before: 4, track: [2 5 4]
    Cap Before: 4, track: [2 5 4 6]
    Cap After: 4, track: [2 5 4]
    Cap After: 4, track: [2 5]
    Cap Before: 4, track: [2 5 6]
    Cap Before: 4, track: [2 5 6 4]
    Cap After: 4, track: [2 5 6]
    Cap After: 4, track: [2 5]
    Cap After: 2, track: [2]
    Cap Before: 2, track: [2 4]
    Cap Before: 4, track: [2 4 5]
    Cap Before: 4, track: [2 4 5 6]
    Cap After: 4, track: [2 4 5]
    Cap After: 4, track: [2 4]
    Cap Before: 4, track: [2 4 6]
    Cap Before: 4, track: [2 4 6 5]
    Cap After: 4, track: [2 4 6]
    Cap After: 4, track: [2 4]
    Cap After: 2, track: [2]
    Cap Before: 2, track: [2 6]
    Cap Before: 4, track: [2 6 5]
    Cap Before: 4, track: [2 6 5 4]
    Cap After: 4, track: [2 6 5]
    Cap After: 4, track: [2 6]
    Cap Before: 4, track: [2 6 4]
    Cap Before: 4, track: [2 6 4 5]
    Cap After: 4, track: [2 6 4]
    Cap After: 4, track: [2 6]
    Cap After: 2, track: [2]
    Cap After: 1, track: []

    ```
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1062 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 19:31 · PVG 03:31 · LAX 11:31 · JFK 14:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.