V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
18870715400
V2EX  ›  Go 编程语言

请教 golang 的一个切片的问题

  •  
  •   18870715400 · 231 天前 · 1255 次点击
    这是一个创建于 231 天前的主题,其中的信息可能已经有所发展或是发生改变。
    package main
    
    import "fmt"
    
    type pq struct {
    	arr []int
    }
    
    func (q *pq) put(num int) {
    	// 从小到大的顺序插入进去
    	index := b_s(q.arr, num)
    	if index >= len(q.arr) {
    		// 直接插到最后一个数位
    		q.arr = append(q.arr, num)
    	} else {
    		tmp := append(q.arr[:index], num)
    		tmp = append(tmp, q.arr[index:]...)
    		q.arr = tmp
    	}
    
    }
    
    func (q *pq) get() int {
    	if len(q.arr) > 0 {
    		num := q.arr[0]
    		q.arr = q.arr[1:]
    		return num
    	}
    	panic("arr is empty!!!")
    }
    
    func (q *pq) getSize() int {
    	return len(q.arr)
    }
    
    func b_s(arr []int, target_num int) int {
    	if len(arr) == 0 {
    		return 0
    	} else {
    		left, right := 0, len(arr)-1
    		for {
    			if right-left <= 1 {
    				if target_num <= arr[left] {
    					return left
    				} else if target_num <= arr[right] {
    					return right
    				} else {
    					return right + 1
    				}
    			} else {
    				mid := (left + right) / 2
    				if arr[mid] == target_num {
    					return mid
    				} else if arr[mid] < target_num {
    					left = mid
    				} else {
    					right = mid
    				}
    			}
    		}
    	}
    }
    
    func main() {
    	s := &pq{arr: make([]int, 0)}
    	s.put(20)
    	s.put(3)
    	s.put(30)
    	fmt.Println(s.arr)
    }
    

    请教一下输出的为什么不是[3 20 30] 呀, 感觉使用好像和 python 的不太一样

    5 条回复    2024-03-21 23:16:20 +08:00
    kfish
        1
    kfish  
       231 天前
    很明显不是切片的问题, 算法没写对呗
    nagisaushio
        2
    nagisaushio  
       231 天前 via Android
    tmp := append(q.arr[:index], num) 这句会覆写后面已有的数据
    18870715400
        3
    18870715400  
    OP
       231 天前
    @nagisaushio 大佬, 由于我这边是从 python 转过来的,python 类似的就是这样的写法,不知道这样具体有啥问题呢。
    NilXuan
        4
    NilXuan  
       231 天前
    tmp := append(q.arr[:index], num);可以看做两条语句:
    a := q.arr[:index];
    tmp := append(a,num);
    问题的关键在于关键的问题:a 虽然是一个新的切片变量,但是 a 的底层数据结构——数组是和 q.arr 共享的;因此 tmp := append(a,num); 相当于把 num 放到了底层数组 index 的位置,那么从 q.arr 的角度来看,就是数据被覆盖了;
    可以尝试新创建一个数组,然后 copy 一下;
    18870715400
        5
    18870715400  
    OP
       231 天前
    @NilXuan 感谢大佬,看了一下解释,
    第一次 put(20)的时候是正常没有问题,
    第二次 put(3)的时候是发生了以下的过程
    首先计算出来 index=0 ,
    所以
    tmp := append(q.arr[:index], num)就变成了以下两个步骤
    a := q.arr[:0], 所以切片截取之后 a 和 q.arr 的 header 地址相同,len 不同,q.arr 是 1 ,a=0 ,cap 一样,
    tmp := append(a, num), 此时没有发生扩容,所以 a 和 q.arr 还是使用的同一片地址, 所以第一个元素就改成了 num 就是 3 了

    tmp = append(tmp, q.arr[index:]...)
    所以此时 q.arr[index:] 就是 等于 [3]了
    此时 append 进行了扩容,tmp 会迁移到一个新的地址当中,所以此时 tmp 就是[3, 3]了, 而之前的 q.arr 还是[3]

    之后 put(30)就是正常的操作了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1003 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 19ms · UTC 21:32 · PVG 05:32 · LAX 13:32 · JFK 16:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.