文章目录
- 引发思考的一道算法题
- slice
- make初始化
- 切片扩容原理
- 切片截取原理
- 切片复制原理
- 算法题的正解
- 补充
- string和[]byte互转
- string 与[]byte相互转换
引发思考的一道算法题
链接：组合
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
大致的思路就是递归+回溯:
- res [][]int存储所有可能的结果，temp []int存储一种可能的结果
- 首先确定递归参数和返回值。对于这道题目不需要有返回值，参数的话，传入n，k表示从n个数选出k个数，传入in表示当前处理的第几个数字.[由于闭包可以捕获变量所以n,k不需要作为参数传入]
- 递归边界就是，当切片temp中的元素个数到达k的时候，将其存储到res中
- 核心处理逻辑，从in–n中选择一个数字加入temp,然后递归，回溯
代码如下：
//这里使用到了闭包
func combine(n int, k int) [][]int {
var res [][]int
var tem []int
var dfs func (int)
dfs=func(in int){
if len(tem)==k{
res=append(res,tem)
}
for i:=in;i<=n;i++{
tem=append(tem,i)
dfs(i+1)
tem=tem[:len(tem)-1]
}
}
dfs(1)
return res
}
看一下运行结果
- 通过运行结果发现，结果中的值被覆盖掉了。要解释这个现象，还需要了解一下slice的底层构成。
slice
源码位置
src\runtime\slice.go
- slice其实是一个struct
type slice struct {
//指向底层数组的指针
array unsafe.Pointer
//数组长度
len int
//为数组分配的总空间大小
cap int
}
make初始化
slice:=make([]int,3,4)
利用"make"初始化一个slice会调用"makeslice函数"[src\runtime\slice.go]
func makeslice(et *_type, len, cap int) unsafe.Pointer {
//et.size表示的是切片内数据类型的大小，math.MulUinptr计算两个数的乘积，并返回这个乘积和一个表示是否溢出的bool型变量
mem, overflow := math.MulUintptr(et.size, uintptr(cap))
//要么是用cap申请的内存溢出或者超出最大限制，要么是len和cap的关系有问题
if overflow || mem > maxAlloc || len < 0 || len > cap {
//再次计算用len申请的内存大小
mem, overflow := math.MulUintptr(et.size, uintptr(len))
//内存溢出。或者超出最大限制或者len<0
if overflow || mem > maxAlloc || len < 0 {
//panic("len out of range ")
panicmakeslicelen()
}
//panic("cap out of range ")len>cap的情况
panicmakeslicecap()
}
//如果申请cap*size大小的内存可以的话就申请cap*size大小的内存，不然的话申请len*size大小的内存
return mallocgc(mem, et, true)
}
如果make函数初始化一个很大的切片，该切片会逃逸到堆上。如果分配了一个比较小的切片会直接在栈中分配。没有发生逃逸调用的是"makeslice"函数，发生逃逸调用的是"makeslice64"函数
func makeslice64(et *_type, len64, cap64 int64) unsafe.Pointer {
//首先会判断要申请的内存大小是否超出了理论上系统可以分配的内存大小
len := int(len64)
if int64(len) != len64 {
panicmakeslicelen()
}
cap := int(cap64)
if int64(cap) != cap64 {
panicmakeslicecap()
}
//没有超出，理论上可以申请内存
return makeslice(et, len, cap)
}
看一下“mallogc”分配内存的函数，这个函数就不展开来看了，看看源代码上的解释
Allocate an object of size bytes.
Small objects are allocated from the per-P cache’s free lists.
Large objects (> 32 kB) are allocated straight from the heap.
小对象(<=32KB)可以直接分配在P拥有的cache的空闲链表中[这里的P是指GMP中的P，cache和go的内存管理有关,指的是mcache]，大对象(>32KB)直接在堆上分配
需要注意的是每个版本的阈值可能不一样，我的版本是go version go1.20.8 windows/amd64
切片扩容原理
slice通过append进行扩容,先用代码演示一下
func main() {
//调用makesilice进行内存的分配
s := make([]int, 3, 4)
fmt.Println(len(s), cap(s)) //3 4
s = append(s, 1)
fmt.Println(len(s), cap(s))//4 4
s = append(s, 2)
fmt.Println(len(s), cap(s))//5 8
}
- 当插入元素时发现，没有可用的空间[len==cap]，会先进行扩容，然后插入新的元素。
扩容的核心逻辑位于“slice.go\growslice”函数中
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
oldLen := newLen - num
if raceenabled {
callerpc := getcallerpc()
racereadrangepc(oldPtr, uintptr(oldLen*int(et.size)), callerpc, abi.FuncPCABIInternal(growslice))
}
if msanenabled {
msanread(oldPtr, uintptr(oldLen*int(et.size)))
}
if asanenabled {
asanread(oldPtr, uintptr(oldLen*int(et.size)))
}
if newLen < 0 {
panic(errorString("growslice: len out of range"))
}
if et.size == 0 {
// append should not create a slice with nil pointer but non-zero len.
// We assume that append doesn't need to preserve oldPtr in this case.
return slice{unsafe.Pointer(&zerobase), newLen, newLen}
}
newcap := oldCap
doublecap := newcap + newcap
if newLen > doublecap {
newcap = newLen
} else {
const threshold = 256
if oldCap < threshold {
newcap = doublecap
} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < newLen {
// Transition from growing 2x for small slices
// to growing 1.25x for large slices. This formula
// gives a smooth-ish transition between the two.
newcap += (newcap + 3*threshold) / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = newLen
}
}
}
//根据内存对齐计算分配的内存大小
var overflow bool
var lenmem, newlenmem, capmem uintptr
switch {
case et.size == 1:
lenmem = uintptr(oldLen)
newlenmem = uintptr(newLen)
capmem = roundupsize(uintptr(newcap))
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
case et.size == goarch.PtrSize:
lenmem = uintptr(oldLen) * goarch.PtrSize
newlenmem = uintptr(newLen) * goarch.PtrSize
capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
newcap = int(capmem / goarch.PtrSize)
case isPowerOfTwo(et.size):
var shift uintptr
if goarch.PtrSize == 8 {
// Mask shift for better code generation.
shift = uintptr(sys.TrailingZeros64(uint64(et.size))) & 63
} else {
shift = uintptr(sys.TrailingZeros32(uint32(et.size))) & 31
}
lenmem = uintptr(oldLen) << shift
newlenmem = uintptr(newLen) << shift
capmem = roundupsize(uintptr(newcap) << shift)
overflow = uintptr(newcap) > (maxAlloc >> shift)
newcap = int(capmem >> shift)
capmem = uintptr(newcap) << shift
default:
lenmem = uintptr(oldLen) * et.size
newlenmem = uintptr(newLen) * et.size
capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
capmem = roundupsize(capmem)
newcap = int(capmem / et.size)
capmem = uintptr(newcap) * et.size
}
if overflow || capmem > maxAlloc {
panic(errorString("growslice: len out of range"))
}
var p unsafe.Pointer
if et.ptrdata == 0 {
p = mallocgc(capmem, nil, false)
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
p = mallocgc(capmem, et, true)
if lenmem > 0 && writeBarrier.enabled {
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.size+et.ptrdata)
}
}
//将旧数组的数据完全拷贝到新数组
memmove(p, oldPtr, lenmem)
return slice{p, newLen, newcap}
}
看核心代码如何计算扩容之后的新的容量的：
/*
oldLen:指的是旧数组的元素个数
num:指的是加入的元素的个数
newLen:指的是oldLen+num，新数组的元素个数
oldCap:指的是原数组的容量
*/
//首先将newCap赋值为oldCap
newcap := oldCap
//doubleCap等于原cap的两倍
doublecap := newcap + newcap
//新数组的长度大于原数组容量的两倍
if newLen > doublecap {
//新容量等于新的长度
newcap = newLen
} else {
//新长度小于等于旧容量的2倍
//阈值设为256
const threshold = 256
//旧容量小于阈值
if oldCap < threshold {
//新容量等于旧容量的两倍
newcap = doublecap
} else {
//旧容量大于等于阈值
//持续增加newcap[初始值是oldcap]直到newcap大于等于newLen或者newcap<=0[这种情况是发生了溢出]
for 0 < newcap && newcap < newLen {
//小切片[oldcap<256]以2倍的速度增长
//大切片[oldcap>=256]以1.25倍的速度增长
newcap += (newcap + 3*threshold) / 4
}
//经过计算之后newcap发生溢出
if newcap <= 0 {
//溢出的话，将新容量设置为新长度
newcap = newLen
}
}
}
综上述来看，扩容的策略如下：
- 新数组的长度大于旧容量的两倍，新容量等于新数组长度
- 新数组的长度小于旧容量的两倍
- 旧容量小于阈值256，新容量等于旧容量的两倍
- 旧容量大于等于阈值256，新容量用oldcap作为初始值以1.25倍的速度增长直到大于等于新长度
- 经过计算新容量发生了溢出，将新容量设置为新长度
为了内存对齐，申请的内存可能大于实际算出的内存大小，这涉及到内存管理的知识。
func main() {
//调用makesilice进行内存的分配
s := make([]int64, 99, 99)
fmt.Println(len(s), cap(s)) //99 99
s = append(s, 1)
fmt.Println(len(s), cap(s)) //100 224
s = append(s, 2)
fmt.Println(len(s), cap(s)) //101 224
}
根据不同的类型执行不同的逻辑
if et.ptrdata == 0 {
//没有指针类型的数据
p = mallocgc(capmem, nil, false)
//分配内存之后，将newlen之后的多出来的内存进行清空
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
//含有指针类型的数据
p = mallocgc(capmem, et, true)
if lenmem > 0 && writeBarrier.enabled {
//分配内存之后需要开启写屏障，对旧指针指向的对象进行标记[这里涉及到垃圾回收]
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.size+et.ptrdata)
}
}
//将oldPtr中的元素复制到p中
memmove(p, oldPtr, lenmem)
切片截取原理
切片截取会复制slice struct中的三个字段:array[unsafe.Pointer]、len[int]、cap[int]，所以由一个切片截取出来的切片会指向同一个底层数组。
但是需要注意的是，切片之间共享的是底层的数组，len和cap变量的值是没有共享的。所以对于同样的数据，切片a可以访问到，但是切片b访问不到
func case2() {
s1 := []int{1, 2, 3, 4, 5, 6, 7, 8}
printLengthAndCap(s1)
s2 := s1[1:]
printLengthAndCap(s2)
fmt.Printf("addr(s1)=%p,addr(s2)=%p\n", s1, s2)
}
/*
运行结果如下：
[1 2 3 4 5 6 7 8]
len=8 cap=8
[2 3 4 5 6 7 8]
len=7 cap=7
addr(s1)=0xc000010380,addr(s2)=0xc000010388
*/
可以看到s1和s2指向同一个底层数组，只是起始位置不一致。
func case3() {
s1 := []int{1, 2, 3, 4, 5, 6, 7, 8}
printLengthAndCap(s1)
s2 := s1[:]
printLengthAndCap(s2)
fmt.Printf("addr(s1)=%p,addr(s2)=%p\n", s1, s2)
}
/*
[1 2 3 4 5 6 7 8]
len=8 cap=8
[1 2 3 4 5 6 7 8]
len=8 cap=8
addr(s1)=0xc000010380,addr(s2)=0xc000010380
*/
func case4() {
s1 := []int{1, 2, 3, 4, 5, 6, 7, 8}
printLengthAndCap(s1)
s2 := s1[:6]
printLengthAndCap(s2)
fmt.Printf("addr(s1)=%p,addr(s2)=%p\n", s1, s2)
}
/*
[1 2 3 4 5 6 7 8]
len=8 cap=8
[1 2 3 4 5 6]
len=6 cap=8
addr(s1)=0xc000010380,addr(s2)=0xc000010380
*/
接下来对其中一个slice进行修改看看另外一个slice能不能看得到
func case5() {
s1 := []int{1, 2, 3, 4, 5, 6, 7, 8}
s2 := s1[:6]
s2[0] = 0
s2 = append(s2, 9)
printLengthAndCap(s1)
printLengthAndCap(s2)
}
/*
[0 2 3 4 5 6 9 8]
len=8 cap=8
[0 2 3 4 5 6 9]
len=7 cap=8
*/
- 从运行结果来看，s2的修改引起的s1的修改，因为s2和s1指向同一个底层数组。而且s2=append(s2,9)导致s1原本的元素被覆盖，这也能解释刚开始的算法题为什么出现了值被覆盖的情况，因为在向上回溯的过程中，对一个slice的修改影响了其它的slice。
- 如果append操作引起了扩容，那么对该slice的修改不会影响其它的slice。因为上面介绍过，扩容就是分配一块新的内存将原先的数据全部拷贝过来，然后插入新的数据。
package main
import "fmt"
func main(){
s:=[]int{1,2,3}
s1:=s[:2]
fmt.Println("s:",s,"s1:",s1)
s1=append(s1,4)
fmt.Println("s:",s,"s1:",s1)
s1=append(s1,6)
fmt.Println("s:",s,"s1:",s1)
}
/*
s: [1 2 3] s1: [1 2]
s: [1 2 4] s1: [1 2 4]
s: [1 2 4] s1: [1 2 4 6]
*/
那有什么方法可以解决呢？当时是希望在拷贝的过程中不只是简单的拷贝slice struct三个字段的值，而是将底层数组进行深拷贝。go中的copy函数可以做到这个，接下来看看切片复制的原理。
切片复制原理
截取切片，只会复制切片结构中的三个字段，指向的底层数组还是同一个。如果想要建立一个全新的与原来的切片拥有不同的数据源，可以使用copy(dst,src)函数
copy函数在运行时调用了memmove函数，实现基于内存的复制
// slicecopy is used to copy from a string or slice of pointerless elements into a slice.
func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
//src原切片和dst目标切片的长度都为0，无需复制
/*
从这一行代码也可以看出，以源切片和目的切片的最小长度为准，
源切片的长度为0表示没有数据，没有数据也就无法将数据拷贝到目的切片；
目的切片的长度为0表示没有可用的空间，源切片就算有数据也无法拷贝到目的切片。
*/
if fromLen == 0 || toLen == 0 {
return 0
}
//只会复制fromlen[src slice长度]和tolen[dst slice]中最小的长度
//n存储的是min(fromLen,toLen)
n := fromLen
if toLen < n {
n = toLen
}
//width指的是size of single element
if width == 0 {
return n
}
//计算需要分配的内存大小
size := uintptr(n) * width
if raceenabled {
callerpc := getcallerpc()
pc := abi.FuncPCABIInternal(slicecopy)
racereadrangepc(fromPtr, size, callerpc, pc)
racewriterangepc(toPtr, size, callerpc, pc)
}
if msanenabled {
msanread(fromPtr, size)
msanwrite(toPtr, size)
}
if asanenabled {
asanread(fromPtr, size)
asanwrite(toPtr, size)
}
/*
如果需要分配的内存只有1byte,那么不需要进行内存的分配，只需将fromptr[src slice]转换为byte复制给toptr
*/
if size == 1 {
*(*byte)(toPtr