Go语言核心之美 3.2-slice切片

erlib · · 1635 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

版权声明:本文为Sunface(孙飞)原创文章,转载请注明出处 https://blog.csdn.net/abv123456789/article/details/50957218

Slice(切片)是长度可变的元素序列(与之对应,上一节中的数组是不可变的),每个元素都有相同的类型。slice类型写作[]T,T是元素类型。slice和数组写法很像,区别在于slice没有指定长度。

数组和slice之间的联系是非常紧密的。slice是很轻量的数据结构,是引用类型,它指向一个底层数组,该数组被称之为slice的底层数组,slice可以访问底层数组的某个子序列,也可以访问整个数组。一个slice由三个部分组成:指针、长度、容量,指针指向了slice中第一个元素对应的底层数组元素的地址,因为slice未必是从数组第一个元素开始,因此slice中的第一个元素未必是数组中的第一个元素;长度是slice中的元素数目,是不能超过容量的;容量一般是从slice中第一个元素对应底层数组中的开始位置,到底层数组的结尾的长度。内置函数len和cap分别返回slice的长度和容量。

多个slice可以共享底层数组,甚至它们引用的部分可以相互重叠。图4.1表示了一个数组,它的元素是一年中各个月份的字符串,还有两个重叠引用了底层数组的slice。数组定义:

months := [...]string{1: "January", /* ... */, 12: "December"}

其中一月份是months[1],十二月是months[12]。通常来说,数组第一个元素的索引从0开始,但是月份一般是从1月开始到12月,因此在声明数组时,我们跳过了第0个元素,这里,第0个元素会被默认初始化为""(空字符串)。

下面介绍切片操作s[i:j],其中0 ≤ i≤ j≤ cap(s),该操作会创建一个新的slice,slice会引用s中从第i个元素到第j-1个元素,新的slice有j-i个元素。如果省略下标i,写成s[:j],实际上代表s[0:j];如果省略下标j,写成s[i:],代表s[0:len(s)]。因此months[1:13]操作将引用全部月份,和months[1:]操作等价。months[:]则是引用整个数组。下面分别表示第二个季度和北方的夏天:

Q2 := months[4:7]
summer := months[6:9]
fmt.Println(Q2)     // ["April" "May" "June"]
fmt.Println(summer) // ["June" "July" "August"]

两个slice有重叠部分:六月份。下面是一个是否包含相同月份的测试(性能不高):

for _, s := range summer {
    for _, q := range Q2 {
        if s == q {
            fmt.Printf("%s appears in both\n", s)
        }
    }
}

如果slice操作访问的下标大于cap(s)将导致panic(越界),如果超过len(s)则意味着扩展slice(不能超过cap(s) ):

fmt.Println(summer[:20]) // panic: out of range

endlessSummer := summer[:5] // 在容量允许内扩展summer
fmt.Println(endlessSummer)  // "[June July August September October]"

另外,字符串的slice操作和[]byte的slice操作是很相似的,它们都表现为x[m:n],并且都返回原始序列的子序列,底层数组也都是原始序列,因此slice操作是常量级别的时间复杂度(只是更新slice中的指向位置,长度,容量)。若x[m:n]的目标是字符串,则生成一个子串;若目标是[]byte,则生成新的[]byte。

因为slice引用包含了指向底层数组的指针,因此向函数传递slice后,函数可以在内部对slice的底层数组进行更改。换而言之,复制slice就是为底层数组创建一个新的引用,代价是非常低的(其实就是复制一个含有三个字段的struct)。下面的reverse函数对[]int类型的slice进行就地反转(无内存分配),它可以用于任意长度的slice:

// reverse reverses a slice of ints in place.
func reverse(s []int) {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}

反转数组:

a := [...]int{0, 1, 2, 3, 4, 5}
reverse(a[:])
fmt.Println(a) // "[5 4 3 2 1 0]"

如果要将slice中前n个元素和后面所有的元素调换位置的话(以第n个元素为支点,向左旋转),其中一个办法是调用三次reverse函数,第一次是反转前n个元素,然后是反转剩下所有元素,最后是反转整个slice(如果是向右旋转,则将第一个和第三个函数对调位置即可)。

s := []int{0, 1, 2, 3, 4, 5}
// 以2为支点,向左旋转
reverse(s[:2])
reverse(s[2:])
reverse(s)
fmt.Println(s) // "[2 3 4 5 0 1]"

要注意上面代码中,slice和数组的初始化语法的差异。虽然它们的语法很类似,都是用花括号包含的元素序列,但是slice是不需要指明长度的,因此会隐式的创建一个底层数组,然后slice内的指针会指向这个数组。初始化slice和初始化数组一样,可以使用值序列或者使用索引-值列表(见3.1节)。

在3.1节中,我们提到了若数组的类型可以比较,那数组可以比较,但是slice之间是不能通过==操作符进行比较的!标准库中提供了高度优化的bytes.Equal函数,可以用来判断两个[]byte是否相等,不过对于其它类型的slice,我们必须实现自己的比较函数:

func equal(x, y []string) bool {
    if len(x) != len(y) {
        return false
    }
    for i := range x {
        if x[i] != y[i] {
            return false
        }
    }
    return true
}

 为什么Go语言不支持slice的比较运算呢?第一个原因,slice是引用类型,一个slice甚至可以引用自身。虽然有很多解决办法,但是没有一个是简单有效的。第二个原因,因为slice是间接引用,因此一个slice在不同时间可能包含不同的元素-底层数组的元素可能被修改。只要一个数据类型可以做相等比较,那么就可以用来做map的key,map这种数据结构对key的要求是:如果最开始时key是相等的,那在map的生命周期内,key要一直相等,因此这里key是不可变的。而对于指针或chan这类引用类型,==可以判断两个指针是否引用了想同的对象,是有用的,但是slice的相等测试充满了不确定性,因此,安全的做法是禁止slice之间的比较操作。

唯一例外:slice可以和nil进行比较,例如,

if summer == nil { /* ... */ }

slice是引用类型,因此它的零值是nil。一个nil slice是没有底层数组的,长度和容量都是0,但是也有非nil的slice,长度和容量也是0,例如[]int{}或make([]int, 3)[3:]。我们可以通过[]int(nil)这种类型转换生成一个[]int类型的nil值。

var s []int    // len(s) == 0, s == nil
s = nil        // len(s) == 0, s == nil
s = []int(nil) // len(s) == 0, s == nil
s = []int{}    // len(s) == 0, s != nil

由上可知,如果要测试一个slice是否为空,要使用len(s) == 0。除了可以和nil做相等比较外,nil slice的使用和0长度slice的使用方式相同:例如,前文的函数reverse(nil)就是安全的。除非包文档特别说明,否则所有的Go函数都应该以相同的方式对待nil slice和0长度slice(byte包中的部分函数会对nil值slice做特殊处理)。

内置函数make可以用于创建一个指定类型、长度、容量的slice。很多时候,容量参数可以省略,这种情况下,容量等于长度:

make([]T, len)
make([]T, len, cap) // same as make([]T, cap)[:len]

实际上,make会创建一个匿名的底层数组,然后返回一个slice值,只有通过该值才能引用匿名的底层数组。在上面第一条语句中,slice的范围和底层数组范围一致;在第二条语句中,slice引用了底层数组前len个元素,但是slice的容量和底层数组的长度一致,因此slice可以在len不够用时,自动增长,只要长度不超过cap即可。


4.2.1. append函数

内置函数append用于向slice的末端追加元素:

var runes []rune
for _, r := range "Hello, 世界" {
    runes = append(runes, r)
}
fmt.Printf("%q\n", runes) // "['H' 'e' 'l' 'l' 'o' ',' ' ' '世' '界']"

上面的循环使用append构建了包含9个rune的slice(这个问题可以直接通过[]rune("Hello,世界")来解决)。

理解append对于理解slice的底层原理是非常有帮助的,下面是appendInt 1.0版本,用于处理[]int类型的slice:

func appendInt(x []int, y int) []int {
    var z []int
    zlen := len(x) + 1
    if zlen <= cap(x) {
        // 还有空间,扩展slice
        z = x[:zlen]
    } else {
        // 空间不足,分配新的数组
        // 新数组的长度按2的倍数增长.
        zcap := zlen
        if zcap < 2*len(x) {
            zcap = 2 * len(x)
        }
        z = make([]int, zlen, zcap)
        copy(z, x) // a built-in function; see text
    }
    z[len(x)] = y
    return z
}

每次调用appendInt,先检测slice的底层数组容量是否足够。如果足够,直接扩展slice(仍然在底层数组中),然后将y元素复制过去,这时x和z共享底层数组。

如果没有足够的容量,appendInt会重新分配一个足够大的数组,然后将x全部复制过去,再在尾部添加y。这时,x和z引用的是不同的底层数组。

上面那种通过循环来一个一个复制元素虽然很直接很简单,但是内置函数copy更适合这种场景。copy可以将一个slice复制给另一个同类型的slice,copy第一个参数是目标slice,第二个参数是源slice,可以通过这种方式来记住参数顺序: dst = src,将src'赋给'dst,dst和src两个slice可以共享底层数组,甚至重叠。copy将返回复制的元素个数-等于两个slice中较小的长度值,所以不用担心越界问题。

为了减少内存分配次数、提升利用率,新分配的数组的长度要大于x + y的长度,这里有个简单的办法,每次扩展数组时将长度翻倍,可以减少了多次内存分配,也保证了添加元素是常数时间操作:

func main() {
    var x, y []int
    for i := 0; i < 10; i++ {
        y = appendInt(x, i)
        fmt.Printf("%d cap=%d\t%v\n", i, cap(y), y)
        x = y
    }
}

容量的每次变化都会导致内存分配和内存拷贝,因为需要创建新的底层数组,并拷贝元素过去:

0  cap=1    [0]
1  cap=2    [0 1]
2  cap=4    [0 1 2]
3  cap=4    [0 1 2 3]
4  cap=8    [0 1 2 3 4]
5  cap=8    [0 1 2 3 4 5]
6  cap=8    [0 1 2 3 4 5 6]
7  cap=8    [0 1 2 3 4 5 6 7]
8  cap=16   [0 1 2 3 4 5 6 7 8]
9  cap=16   [0 1 2 3 4 5 6 7 8 9]

先看一下i=3那一次循环,循环开始前x包含了[0 1 2]三个元素,容量是4,这时底层数组末尾还有一个位置可以将新元素拷贝进来,不需要内存分配,循环后,y的长度和容量都是4并且x和y引用相同的底层数组:



再来看i=4这次循环,循环开始前,x的底层数组没有新空间了,因此appendInt重新创建一个容量为8的底层数组,将x的所有元素都复制过去,然后在末尾添加新元素4。循环后,y的长度是5,容量是8,因此还有3个空闲位置,后面的三次循环都不需要重新分配底层数组。在i=4这次循环中,y和x引用了不同的底层数组:

内置函数append使用了比appendInt更复杂的扩展策略,因此我们无法得知append调用是否导致了新的内存分配,也不能确定新的slice和旧的slice是否引用相同的底层数组,同时我们也不能确定在旧的slice上操作是否会影响新的slice。因此一般这样使用append:

runes = append(runes, r)

将值直接赋给旧的slice,这种更新slice变量的写法在调用append时是必要的。在实际应用中,除了append,其它任何可能导致长度、容量或底层数组变化的操作,都需要更新旧的slice变量。虽然slice是引用类型,访问底层数组是间接访问的,但是slice本身就是一个结构体,是一个值类型,里面包含了指针、长度、容量字段,因此要更新slice就要像上面那样有显式的赋值操作。从这个角度来说,slice并不是一个纯粹的引用类型:

type IntSlice struct {
    ptr      *int
    len, cap int
}

我们的appendInt函数每次只能添加一个元素,而append函数可以添加多个,甚至是一个slice:

var x []int
x = append(x, 1)
x = append(x, 2, 3)
x = append(x, 4, 5, 6)
x = append(x, x...) // 追加slice x
fmt.Println(x)      // "[1 2 3 4 5 6 1 2 3 4 5 6]"

现在我们将appendInt进行完善,以达到和append函数类似的效果,其中用到了变参函数,在下一章中会详细解释:

func appendInt(x []int, y ...int) []int {
    var z []int
    zlen := len(x) + len(y)
    // ...expand z to at least zlen...
    copy(z[len(x):], y)
    return z
}


4.2.2. 一些就地操作的技巧

再来看看更多的slice就地操作的例子,例如旋转、反转、修改元素。给定一个字符串列表,nonempty将在原有slice空间内进行操作,然后返回不包含空字符串的列表:

// Nonempty is an example of an in-place slice algorithm.
package main

import "fmt"

// nonempty returns a slice holding only the non-empty strings.
// The underlying array is modified during the call.
func nonempty(strings []string) []string {
    i := 0
    for _, s := range strings {
        if s != "" {
            strings[i] = s
            i++
        }
    }
    return strings[:i]
}

这里比较精妙的地方是,输入slice和输出slice共享底层数组,这样就避免了重新分配一个数组,不过造成的问题是原来的数据可能会被覆盖:

data := []string{"one", "", "three"}
fmt.Printf("%q\n", nonempty(data)) // `["one" "three"]`
fmt.Printf("%q\n", data)           // `["one" "three" "three"]`

根据4.2.1的内容,我们通常会这样使用nonempty函数:

  data = nonempty(data)

nonempty函数也可以使用append实现:

func nonempty2(strings []string) []string {
    out := strings[:0] // zero-length slice of original
    for _, s := range strings {
        if s != "" {
            out = append(out, s)
        }
    }
    return out
}

无论采用哪种实现方式,像这样复用数组空间要求每个输入值最多只有一个输出值,这种模式对很多算法都是适用的:过滤一个值序列或者合并值序列中的相邻元素。类似这种用法都是较为复杂的,也是较为少见的,但是在某些场合中可以发挥奇效。

可以用slice来模拟栈(stack)。给定一个空的slice,对应空的stack,然后使用append函数将新值入栈:

stack = append(stack, v) // push v

栈顶对应的是slice最后一个元素:

top := stack[len(stack)-1] // top of stack

通过切片操作可以弹出栈顶元素:

stack = stack[:len(stack)-1] // pop

要删除slice某个元素i并保存原有的元素顺序,可以通过copy将i后面的元素依次向前移动一位:

func remove(slice []int, i int) []int {
    copy(slice[i:], slice[i+1:])
    return slice[:len(slice)-1]
}

func main() {
    s := []int{5, 6, 7, 8, 9}
    fmt.Println(remove(s, 2)) // "[5 6 8 9]"
}

如果删除元素且不用保持原有顺序,可以用最后一个元素覆盖被删除的元素:

func remove(slice []int, i int) []int {
    slice[i] = slice[len(slice)-1]
    return slice[:len(slice)-1]
}

func main() {
    s := []int{5, 6, 7, 8, 9}
    fmt.Println(remove(s, 2)) // "[5 6 9 8]
}


练习 4.3: 重写reverse函数,使用数组指针代替slice。

练习 4.4: 编写一个rotate函数,通过一次循环完成旋转。

练习 4.5: 写一个函数,就地消除[]string中相邻的重复字符串

练习 4.6: 编写一个函数,给定一个UTF-8编码的[]byte类型的slice,就地将该slice中的相邻的两个Unicode空格(参见unicode.IsSpace)替换成一个ASCII空格

练习 4.7: 修改reverse函数,给定一个[]byte,对应的是UTF-8编码的字符串,然后就地反转。是否可以做到无内存分配?



文章所有权:Golang隐修会 联系人:孙飞,CTO@188.com!


有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:erlib

查看原文:Go语言核心之美 3.2-slice切片

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1635 次点击  
加入收藏 微博
被以下专栏收入,发现更多相似内容
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传