Go基础-数组和切片

发表于 | 分类于 | 评论数： | 阅读次数：
本文字数： 21k | 阅读时长 ≈ 19 分钟

摘要

本文内容转自网络，个人学习记录使用，请勿传播

只要掌握了数据结构中的四大法宝，就可以包打天下，他们是：array 、linked list 、hash table、binary tree 。这四大法宝可不是各自为战的，灵活结合才能游刃有余。比如，一个用 hash table 组织的 symbol table，其中个个都是由字符型 array 构成的 linked list 组成的。 — Go 语言之父 Rob Pike

Go 语言里面的数组其实很不常用，这是因为数组是定长的静态的，一旦定义好长度就无法更改，而且不同长度的数组属于不同的类型，之间不能相互转换相互赋值，用起来多有不方便之处。

切片是动态的数组，是可以扩充内容增加长度的数组。当长度不变时，它用起来就和普通数组一样。当长度不同时，它们也属于相同的类型，之间可以相互赋值。这就决定了数组的应用领域都广泛地被切片取代了。

不过也不可以小瞧数组，在切片的底层实现中，数组是切片的基石，是切片的特殊语法隐藏了内部的细节，让用户不能直接看到内部隐藏的数组。切片不过是数组的一个包装，给顽固的数组装上了灵活的翅膀，让石头也可以展翅飞翔。

数组

我们先试一下只申明类型，不赋初值。这时编译器会给数组默认赋上「零值」。数组的零值就是所有内部元素的零值。

定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package main

import "fmt"

func main() {
    var a [9]int
    fmt.Println(a)
}

------------
[0 0 0 0 0 0 0 0 0]

// 另外三种定义方式

func main() {
    var a = [9]int{1, 2, 3, 4, 5, 6, 7, 8, 9}
    var b [10]int = [10]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    c := [8]int{1, 2, 3, 4, 5, 6, 7, 8}
    fmt.Println(a)
    fmt.Println(b)
    fmt.Println(c)
}

---------------------
[1 2 3 4 5 6 7 8 9]
[1 2 3 4 5 6 7 8 9 10]
[1 2 3 4 5 6 7 8]

元素访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package main

import "fmt"

func main() {
    var squares [9]int
    for i := 0; i < len(squares); i++ {
        squares[i] = (i + 1) * (i + 1)
    }
    fmt.Println(squares)
}

--------------------
[1 4 9 16 25 36 49 64 81]

下标越界检查

可以使用内置函数len()来直接获取数组的长度。数组的长度是编译期确定的，当我们使用len()函数访问数组的长度属性时，编译器在背后偷偷把它替换成了整数值。

1
2
3
4
5
6
7
8
9
10
11
12
package main

import "fmt"

func main() {
    var a = [5]int{1,2,3,4,5}
    a[101] = 255
    fmt.Println(a)
}

-----
./main.go:7:3: invalid array index 101 (out of bounds for 5-element array)

Go 语言会对数组访问下标越界进行编译器检查。有一个重要的问题是，如果下标是一个变量，Go 是如何检查下标越界呢？变量需要在运行时才可以决定是否越界，Go 是如何办到的呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package main

import "fmt"

func main() {
    var a = [5]int{1,2,3,4,5}
    var b = 101
    a[b] = 255
    fmt.Println(a)
}

------------
panic: runtime error: index out of range

goroutine 1 [running]:
main.main()
    /Users/qianwp/go/src/github.com/pyloque/practice/main.go:8 +0x3d
exit status 2

Go 会在编译后的代码中插入下标越界检查的逻辑，所以数组的下标访问效率是要打折扣的，比不得 C 语言的数组访问性能。

赋值

  • 同样的子元素类型并且是同样长度的数组才可以相互赋值
  • 否则就是不同的数组类型，不能赋值
  • 数组的赋值本质上是一种浅拷贝操作
  • 赋值的两个数组变量的值不会共享
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package main

import "fmt"

func main() {
    var a = [9]int{1, 2, 3, 4, 5, 6, 7, 8, 9}
    var b [9]int
    b = a
    a[0] = 12345
    fmt.Println(a)
    fmt.Println(b)
}

--------------------------
[12345 2 3 4 5 6 7 8 9]
[1 2 3 4 5 6 7 8 9]

如果数组的长度很大，那么拷贝操作是有一定的开销的，使用的时候一定需要注意。

不同长度的数组之间赋值是禁止的，因为它们属于不同的类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
package main

import "fmt"

func main() {
    var a = [9]int{1, 2, 3, 4, 5, 6, 7, 8, 9}
    var b [10]int
    b = a
    fmt.Println(b)
}

--------------------------
./main.go:8:4: cannot use a (type [9]int) as type [10]int in assignment

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
package main

import "fmt"

func main() {
    var a = [5]int{1,2,3,4,5}
    for index := range a {
  fmt.Println(index, a[index])
 }
 for index, value := range a {
        fmt.Println(index, value)
    }
}

切片 slice

切片无疑是 Go 语言中最重要的数据结构，也是最有趣的数据结构，所有的 Go 语言开发者都津津乐道地谈论切片的内部机制，它也是 Go 语言技能面试中面试官最爱问的知识点之一。初级用户很容易滥用它，这小小的切片想要彻底的理解它是需要花费一番功夫的。

内部结构

一个切片变量包含三个域，分别是底层数组的指针、切片的长度 length 和切片的容量 capacity。切片支持 append 操作可以将新的内容追加到底层数组，也就是填充上面的灰色格子。如果格子满了，切片就需要扩容，底层的数组就会更换。

形象一点说，切片变量是底层数组的视图，底层数组是卧室，切片变量是卧室的窗户。通过窗户我们可以看见底层数组的一部分或全部。一个卧室可以有多个窗户，不同的窗户能看到卧室的不同部分。

创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package main

import "fmt"

func main() {
 // 使用内置make创建
 var s1 []int = make([]int, 5, 8)
 var s2 []int = make([]int, 8) // 满容切片
 fmt.Println(s1)
 fmt.Println(s2)
}

-------------
[0 0 0 0 0]
[0 0 0 0 0 0 0 0]

make 函数创建切片，需要提供三个参数，分别是

  • 切片的类型
  • 切片的长度
  • 切片的容量（可选）
  • 如果不提供第三个参数，那么长度和容量相等，也就是说切片的满容的

切片和普通变量一样，也可以使用类型自动推导，省去类型定义以及 var 关键字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package main

import "fmt"

func main() {
 var s1 = make([]int, 5, 8)
 s2 := make([]int, 8)
 fmt.Println(s1)
 fmt.Println(s2)
}

-------------
[0 0 0 0 0]
[0 0 0 0 0 0 0 0]

初始化

使用 make 函数创建的切片内容是「零值切片」，也就是内部数组的元素都是零值。Go 语言还提供了另一个种创建切片的语法，允许我们给它赋初值。使用这种方式创建的切片是满容的。

1
2
3
4
5
6
7
8
9
10
11
package main

import "fmt"

func main() {
 var s []int = []int{1,2,3,4,5}  // 满容的
 fmt.Println(s, len(s), cap(s))
}

---------
[1 2 3 4 5] 5 5

Go 语言提供了内置函数 len() 和 cap() 可以直接获得切片的长度和容量属性。

空切片

在创建切片时，还有两个非常特殊的情况需要考虑，那就是容量和长度都是零的切片，叫着「空切片」，这个不同于前面说的「零值切片」。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package main

import "fmt"

func main() {
 var s1 []int
 var s2 []int = []int{}
 var s3 []int = make([]int, 0)
 fmt.Println(s1, s2, s3)
 fmt.Println(len(s1), len(s2), len(s3))
 fmt.Println(cap(s1), cap(s2), cap(s3))
}

-----------
[] [] []
0 0 0
0 0 0

上面三种形式创建的切片都是「空切片」，不过在内部结构上这三种形式是有差异的，甚至第一种都不叫「空切片」，而是叫着「 nil 切片」。但是在形式上它们几乎一摸一样，用起来差不多没有区别。

赋值

切片的赋值是一次浅拷贝操作，拷贝的是切片变量的三个域，你可以将切片变量看成长度为 3 的 int 型数组，数组的赋值就是浅拷贝。拷贝前后两个变量共享底层数组，对一个切片的修改会影响另一个切片的内容，这点需要特别注意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main

import "fmt"

func main() {
 var s1 = make([]int, 5, 8)
 // 切片的访问和数组差不多
 for i := 0; i < len(s1); i++ {
  s1[i] = i + 1
 }
 var s2 = s1
 fmt.Println(s1, len(s1), cap(s1))
 fmt.Println(s2, len(s2), cap(s2))

 // 尝试修改切片内容
 s2[0] = 255
 fmt.Println(s1)
 fmt.Println(s2)
}

--------
[1 2 3 4 5] 5 8
[1 2 3 4 5] 5 8
[255 2 3 4 5]
[255 2 3 4 5]

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package main


import "fmt"


func main() {
    var s = []int{1,2,3,4,5}
    for index := range s {
        fmt.Println(index, s[index])
    }
    for index, value := range s {
        fmt.Println(index, value)
    }
}

追加

切片是动态的数组，其长度是可以变化的。

切片每一次追加后都会形成新的切片变量

  • 如果底层数组没有扩容，那么追加前后的两个切片变量共享底层数组
  • 如果底层数组扩容了，那么追加前后的底层数组是分离的不共享的
  • 如果底层数组是共享的，一个切片的内容变化就会影响到另一个切片
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main

import "fmt"

func main() {
 var s1 = []int{1,2,3,4,5}
 fmt.Println(s1, len(s1), cap(s1))

 // 对满容的切片进行追加会分离底层数组
 var s2 = append(s1, 6)
 fmt.Println(s1, len(s1), cap(s1))
 fmt.Println(s2, len(s2), cap(s2))

 // 对非满容的切片进行追加会共享底层数组
 var s3 = append(s2, 7)
 fmt.Println(s2, len(s2), cap(s2))
 fmt.Println(s3, len(s3), cap(s3))
}

--------------------------
[1 2 3 4 5] 5 5
[1 2 3 4 5] 5 5
[1 2 3 4 5 6] 6 10
[1 2 3 4 5 6] 6 10
[1 2 3 4 5 6 7] 7 10

正是因为切片追加后是新的切片变量，Go 编译器禁止追加了切片后不使用这个新的切片变量，以避免用户以为追加操作的返回值和原切片变量是同一个变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
package main

import "fmt"

func main() {
 var s1 = []int{1,2,3,4,5}
 append(s1, 6)
 //_ = append(s1, 6)
 fmt.Println(s1)
}

--------------
./main.go:7:8: append(s1, 6) evaluated but not used

追加虽然会导致底层数组发生扩容，更换的新的数组，但是旧数组并不会立即被销毁被回收，因为老切片还指向这旧数组。

切片的域是只读的

切片追加后形成了一个新的切片变量，而老的切片变量的三个域其实并不会改变，改变的只是底层的数组。这里说的是切片的「域」是只读的，而不是说切片是只读的。切片的「域」就是组成切片变量的三个部分，分别是底层数组的指针、切片的长度和切片的容量。

切割

  • 不支持负数位置切割
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package main

import "fmt"

func main() {
 var s1 = []int{1,2,3,4,5,6,7}
 // start_index 和 end_index，不包含 end_index
 // [start_index, end_index)
 var s2 = s1[2:5] 
 fmt.Println(s1, len(s1), cap(s1))
 fmt.Println(s2, len(s2), cap(s2))
}

------------
[1 2 3 4 5 6 7] 7 7
[3 4 5] 3 5

子切片的内部数据指针指向了数组的中间位置，而不再是数组的开头了。子切片容量的大小是从中间的位置开始直到切片末尾的长度，母子切片依旧共享底层数组。

子切片语法上要提供起始和结束位置，这两个位置都可选的，不提供起始位置，默认就是从母切片的初始位置开始（不是底层数组的初始位置），不提供结束位置，默认就结束到母切片尾部（是长度线，不是容量线）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main

import "fmt"

func main() {
 var s1 = []int{1, 2, 3, 4, 5, 6, 7}
 var s2 = s1[:5]
 var s3 = s1[3:]
 var s4 = s1[:]
 fmt.Println(s1, len(s1), cap(s1))
 fmt.Println(s2, len(s2), cap(s2))
 fmt.Println(s3, len(s3), cap(s3))
 fmt.Println(s4, len(s4), cap(s4))
}

-----------
[1 2 3 4 5 6 7] 7 7
[1 2 3 4 5] 5 7
[4 5 6 7] 4 4
[1 2 3 4 5 6 7] 7 7

验证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package main

import "fmt"

func main() {
 var s = make([]int, 5, 8)
 for i:=0;i<len(s);i++ {
  s[i] = i+1
 }
 fmt.Println(s, len(s), cap(s))

 var s2 = s
 var s3 = s[:]
 fmt.Println(s2, len(s2), cap(s2))
 fmt.Println(s3, len(s3), cap(s3))

 // 修改母切片
 s[0] = 255
 fmt.Println(s, len(s), cap(s))
 fmt.Println(s2, len(s2), cap(s2))
 fmt.Println(s3, len(s3), cap(s3))
}

-------------
[1 2 3 4 5] 5 8
[1 2 3 4 5] 5 8
[1 2 3 4 5] 5 8
[255 2 3 4 5] 5 8
[255 2 3 4 5] 5 8
[255 2 3 4 5] 5 8

数组变切片

对数组进行切割可以转换成切片，切片将原数组作为内部底层数组。也就是说修改了原数组会影响到新切片，对切片的修改也会影响到原数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package main

import "fmt"

func main() {
    var a = [10]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    var b = a[2:6]
    fmt.Println(b)
    a[4] = 100
    fmt.Println(b)
}

-------
[3 4 5 6]
[3 4 100 6]

copy 函数

Go 语言还内置了一个 copy 函数，用来进行切片的深拷贝。不过其实也没那么深，只是深到底层的数组而已。如果数组里面装的是指针，比如 []*int 类型，那么指针指向的内容还是共享的。

func copy(dst, src []T) int

copy 函数不会因为原切片和目标切片的长度问题而额外分配底层数组的内存，它只负责拷贝数组的内容，从原切片拷贝到目标切片，拷贝的量是原切片和目标切片长度的较小值 —— min(len(src), len(dst))，函数返回的是拷贝的实际长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package main

import "fmt"

func main() {
 var s = make([]int, 5, 8)
 for i:=0;i<len(s);i++ {
  s[i] = i+1
 }
 fmt.Println(s)
 var d = make([]int, 2, 6)
 var n = copy(d, s)
 fmt.Println(n, d)
}
-----------
[1 2 3 4 5]
2 [1 2]

切片的扩容点

当比较短的切片扩容时，系统会多分配 100% 的空间，也就是说分配的数组容量是切片长度的2倍。但切片长度超过1024时，扩容策略调整为多分配 25% 的空间，这是为了避免空间的过多浪费。试试解释下面的运行结果。

1
2
3
4
5
6
7
8
9
s1 := make([]int, 6)
s2 := make([]int, 1024)
s1 = append(s1, 1)
s2 = append(s2, 2)
fmt.Println(len(s1), cap(s1))
fmt.Println(len(s2), cap(s2))
-------------------------------------------
7 12
1025 1344

扩容是一个比较复杂的操作，内部的细节必须通过分析源码才能知晓，不去理解扩容的细节并不会影响到平时的使用，所以关于切片的源码我们后续在高级内容里面再仔细分析。

切片的三种特殊状态

切片的三种特殊状态

  • 「零切片」
  • 「空切片」
  • 「nil 切片」

切片的底层是一个数组，切片的表层是一个包含三个变量的结构体，当我们将一个切片赋值给另一个切片时，本质上是对切片表层结构体的浅拷贝。结构体中第一个变量是一个指针，指向底层的数组，另外两个变量分别是切片的长度和容量。

1
2
3
4
5
type slice struct {
  array unsafe.Pointer
  length int
  capcity int
}

零切片

「零切片」其实并不是什么特殊的切片，它只是表示底层数组的二进制内容都是零

1
2
3
4
var s = make([]int, 10)
fmt.Println(s)
------------
[0 0 0 0 0 0 0 0 0 0]

如果是一个指针类型的切片，那么底层数组的内容就全是 nil

1
2
3
4
var s = make([]*int, 10)
fmt.Println(s)
------------
[<nil> <nil> <nil> <nil> <nil> <nil> <nil> <nil> <nil> <nil>]

空切片 和 nil 切片

长度为零的切片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var s1 []int
var s2 = []int{}
var s3 = make([]int, 0)
// new 函数返回是指针类型，所以需要使用 * 号来解引用
var s4 = *new([]int)

fmt.Println(len(s1), len(s2), len(s3), len(s4))
fmt.Println(cap(s1), cap(s2), cap(s3), cap(s4))
fmt.Println(s1, s2, s3, s4)

----------------
0 0 0 0
0 0 0 0
[] [] [] []

如何分析三面四种形式的内部结构的区别呢？接下里要使用到 Go 语言的高级内容，通过 unsafe.Pointer 来转换 Go 语言的任意变量类型。

因为切片的内部结构是一个结构体，包含三个机器字大小的整型变量，其中第一个变量是一个指针变量，指针变量里面存储的也是一个整型值，只不过这个值是另一个变量的内存地址。我们可以将这个结构体看成长度为 3 的整型数组 [3]int。然后将切片变量转换成 [3]int。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var s1 []int
var s2 = []int{}
var s3 = make([]int, 0)
var s4 = *new([]int)

var a1 = *(*[3]int)(unsafe.Pointer(&s1))
var a2 = *(*[3]int)(unsafe.Pointer(&s2))
var a3 = *(*[3]int)(unsafe.Pointer(&s3))
var a4 = *(*[3]int)(unsafe.Pointer(&s4))
fmt.Println(a1)
fmt.Println(a2)
fmt.Println(a3)
fmt.Println(a4)

---------------------
[0 0 0]
[824634199592 0 0]
[824634199592 0 0]
[0 0 0]
  • nil切片：s1,s4
  • 空切片： s2,s3
    • 824634199592 这个值是一个特殊的内存地址，所有类型的「空切片」都共享这一个内存地址
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var s2 = []int{}
var s3 = make([]int, 0)

var a2 = *(*[3]int)(unsafe.Pointer(&s2))
var a3 = *(*[3]int)(unsafe.Pointer(&s3))
fmt.Println(a2)
fmt.Println(a3)

var s5 = make([]struct{ x, y, z int }, 0)
var a5 = *(*[3]int)(unsafe.Pointer(&s5))
fmt.Println(a5)

--------
[824634158720 0 0]
[824634158720 0 0]
[824634158720 0 0]

用图形来表示「空切片」和「 nil 切片」如下

空切片指向的 zerobase 内存地址是一个神奇的地址，从 Go 语言的源代码中可以看到它的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//// runtime/malloc.go

// base address for all 0-byte allocations
var zerobase uintptr

// 分配对象内存
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
    ...
    if size == 0 {
        return unsafe.Pointer(&zerobase)
    }
    ...
}

//// runtime/slice.go
// 创建切片
func makeslice(et *_type, len, cap int) slice {
     ...
     p := mallocgc(et.size*uintptr(cap), et, true)
     return slice{p, len, cap}
}

区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main

import "fmt"

func main() {
    var s1 []int
    var s2 = []int{}

    fmt.Println(s1 == nil)
    fmt.Println(s2 == nil)

    fmt.Printf("%#v\n", s1)
    fmt.Printf("%#v\n", s2)
}

-------
true
false
[]int(nil)
[]int{}

所以为了避免写代码的时候把脑袋搞昏的最好办法是不要创建「 空切片」，统一使用「 nil 切片」，同时要避免将切片和 nil 进行比较来执行某些逻辑。这是官方的标准建议。

「空切片」和「 nil 切片」有时候会隐藏在结构体中，这时候它们的区别就被太多的人忽略了，下面我们看个例子

1
2
3
4
5
6
7
8
9
10
11
12
type Something struct {
    values []int
}

var s1 = Something{}
var s2 = Something{[]int{}}
fmt.Println(s1.values == nil)
fmt.Println(s2.values == nil)

--------
true
false

「空切片」和「 nil 切片」还有一个极为不同的地方在于 JSON 序列化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type Something struct {
    Values []int
}

var s1 = Something{}
var s2 = Something{[]int{}}
bs1, _ := json.Marshal(s1)
bs2, _ := json.Marshal(s2)
fmt.Println(string(bs1))
fmt.Println(string(bs2))

---------
{"Values":null}
{"Values":[]}

对比两个slice是否一致

  • reflect比较的方法
  • 循环遍历比较的方法

reflect

1
2
3
func StringSliceReflectEqual(a, b []string) bool {
    return reflect.DeepEqual(a, b)
}

循环遍历

  • 比较长度是否相等
  • 比较两个slice是否都为nil或都不为nil
  • 比较对应索引处两个slice的元素是否相等
    • 这种方式比较的时候要求两个slice的元素顺序都一样才算相等
    • 如果只考虑元素相等，不考虑元素的顺序，需要对比的两个slice元素排序后对比
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func StringSliceEqual(a, b []string) bool {
    if len(a) != len(b) {
        return false
    }

    if (a == nil) != (b == nil) {
        return false
    }

    for i, v := range a {
        if v != b[i] {
            return false
        }
    }

    return true
}

需要注意，这段代码是必须的，虽然如果没有这段代码，在大多数情况下，上面的函数可以正常工作，但是增加这段代码的作用是与reflect.DeepEqual的结果保持一致：[]int{} != []int(nil)

1
2
3
if (a == nil) != (b == nil) {
    return false
}

Benchmark测试效率

我们都知道Golang中reflect效率很低，所以虽然循环遍历的方法看起来很啰嗦，但是如果真的效率比reflect方法高很多，就只能忍痛放弃reflect了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func BenchmarkEqual(b *testing.B) {
    sa := []string{"q", "w", "e", "r", "t"}
    sb := []string{"q", "w", "a", "s", "z", "x"}
    b.ResetTimer()
    for n := 0; n < b.N; n++ {
        StringSliceEqual(sa, sb)
    }
}

func BenchmarkDeepEqual(b *testing.B) {
    sa := []string{"q", "w", "e", "r", "t"}
    sb := []string{"q", "w", "a", "s", "z", "x"}
    b.ResetTimer()
    for n := 0; n < b.N; n++ {
        StringSliceReflectEqual(sa, sb)
    }
}

上面两个函数中，b.ResetTimer()一般用于准备时间比较长的时候重置计时器减少准备时间带来的误差，这里可用可不用

在测试文件所在目录执行go test -bench=.命令

sort后对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func StringSliceEqual(a, b []string) bool {
    if len(a) != len(b) {
        return false
    }

    if (a == nil) != (b == nil) {
        return false
    }
    sort.Sort(sort.IntSlice(a))
    sort.Sort(sort.IntSlice(b))
    
    b = b[:len(a)]
    for i, v := range a {
        if v != b[i] {
            return false
        }
    }

    return true
}

BCE优化

Golang提供BCE特性，即Bounds-checking elimination，关于Golang中的BCE，推荐一篇大牛博客Bounds Check Elimination (BCE) In Golang 1.7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func StringSliceEqualBCE(a, b []string) bool {

    if len(a) != len(b) {
        return false
    }

    if (a == nil) != (b == nil) {
        return false
    }

    b = b[:len(a)]
    for i, v := range a {
        if v != b[i] {
            return false
        }
    }

    return true
}

上述代码通过b = b[:len(a)]处的bounds check能够明确保证v != b[i]中的b[i]不会出现越界错误，从而避免了b[i]中的越界检查从而提高效率

Benchmark函数

1
2
3
4
5
6
7
8
func BenchmarkEqualBCE(b *testing.B) {
    sa := []string{"q", "w", "e", "r", "t"}
    sb := []string{"q", "w", "a", "s", "z", "x"}
    b.ResetTimer()
    for n := 0; n < b.N; n++ {
        StringSliceEqualBCE(sa, sb)
    }
}

slice排序

用 slice 实现归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func merge(left, right []int) (result []int) {
    var l, r int
    for l < len(left) && r < len(right) {
        if left[l] < right[r] {
            result = append(result, left[l])
            l++
        } else {
            result = append(result, right[r])
            r++
        }
    }
    result = append(result, left[l:]...)
    result = append(result, right[r:]...)
    return

}

func mergeSort(s []int) []int {
    if len(s) <= 1 {
        return s
    }
    middle := len(s) / 2
    left := mergeSort(s[:middle])
    right := mergeSort(s[middle:])
    return merge(left, right)
}

sort包

1
sort.Sort(sort.IntSlice(slice))

调用 sort.Slice() 排序

提升点难度，假设 slice 中存储是一个自定义的结构体，假设定义的结构体格式是，待排序的是 Value 字段，results 为待排序的切片 []result：

1
2
3
4
type result struct {
    IP    string  `json:"IP"`
    Value float64 `json:"Value"`
}

使用 sort 提供的排序接口，可按照如下的方式排序：

1
2
3
sort.Slice(results, func(i, j int) bool {
        return results[i].Value < results[j].Value
})

实现 sort 排序的接口

除了上面的排序方式，也可以自定义类型，然后实现排序需要的接口(Len、Less、Swap），按照如下方式实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
type byValue []result

func (v byValue) Len() int {
    return len(v)
}

func (v byValue) Swap(i, j int) {
    v[i], v[j] = v[j], v[i]
}

func (v byValue) Less(i, j int) bool {
    return v[i].Value < v[j].Value
}

然后在排序的切片上调用 sort.Sort 函数即可：

1
sort.Sort(byValue(results))

引入第三方包排序

github.com/patrickmn/sortutil

1
sortutil.AscByField(results, "Value")

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package main

import (
    "encoding/json"
    "fmt"
    "net/http"
    "sort"
    "time"

    "github.com/pmylund/sortutil"
)

type result struct {
    IP    string  `json:"IP"`
    Value float64 `json:"Value"`
}

type byValue []result

func (v byValue) Len() int {
    return len(v)
}

func (v byValue) Swap(i, j int) {
    v[i], v[j] = v[j], v[i]
}

func (v byValue) Less(i, j int) bool {
    return v[i].Value < v[j].Value
}

func main() {
    resp, err := http.Get("gengerate result struct url")
    if err != nil {
        fmt.Println(err)
        return
    }
    defer resp.Body.Close()
    results := make([]result, 0)

    err = json.NewDecoder(resp.Body).Decode(&results)
    if err != nil {
        fmt.Println(err)
        return
    }
    t := time.Now()
    sort.Slice(results, func(i, j int) bool {
        return results[i].Value < results[j].Value

    })

    sortutil.AscByField(results, "Value")
    sort.Sort(byValue(results))
    for _, v := range results {
        fmt.Printf("k: %s, v:%f\n", v.IP, v.Value)
    }
    fmt.Printf("used time: %v\n", time.Since(t))
}

slice元素去重

合并两个整型切片，返回没有重复元素的切片，有两种去重策略

通过双重循环来过滤重复元素（时间换空间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 通过两重循环过滤重复元素
func RemoveRepByLoop(slc []int) []int {
    result := []int{}  // 存放结果
    for i := range slc{
        flag := true
        for j := range result{
            if slc[i] == result[j] {
                flag = false  // 存在重复元素，标识为false
                break
            }
        }
        if flag {  // 标识为false，不添加进结果
            result = append(result, slc[i])
        }
    }
    return result
}

通过字典来过滤（空间换时间）

因为字典的主键唯一，所以可以用来判断元素是否重复

1
2
3
4
5
6
7
8
9
10
11
12
13
// 通过map主键唯一的特性过滤重复元素
func RemoveRepByMap(slc []int) []int {
    result := []int{}
    tempMap := map[int]byte{}  // 存放不重复主键
    for _, e := range slc{
        l := len(tempMap)
        tempMap[e] = 0
        if len(tempMap) != l{  // 加入map后，map长度变化，则元素不重复
            result = append(result, e)
        }
    }
    return result
}

ps : 这里为了节省内存，使用map[int]byte。 因为map的value并没有用到，所以什么类型都可以。

效率第一，如果节省计算时间，则可以采用如下方式

1
2
3
4
5
6
7
8
9
10
// 元素去重
func RemoveRep(slc []int) []int{
    if len(slc) < 1024 {
        // 切片长度小于1024的时候，循环来过滤
        return RemoveRepByLoop(slc)
    }else{
        // 大于的时候，通过map来过滤
        return RemoveRepByMap(slc)
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package main

import "fmt"

func main() {
    var arr = []string{"hello", "hi", "world", "hi", "china", "hello", "hi"}
    fmt.Println(RemoveRepeatedElement(arr))
}


func RemoveRepeatedElement(arr []string) (newArr []string) {
    newArr = make([]string, 0)
    for i := 0; i < len(arr); i++ {
        repeat := false
        for j := i + 1; j < len(arr); j++ {
            if arr[i] == arr[j] {
                repeat = true
                break
            }
        }
        if !repeat {
            newArr = append(newArr, arr[i])
        }
    }
    return
}

切片的扩容

切片结构

切片（Slice）在 Go 语言中，有一个很常用的数据结构，切片是一个拥有相同类型元素的可变长度的序列，它是基于数组类型做的一层封装。它非常灵活，支持自动扩容。并发不安全。
切片是一种引用类型，它有三个属性：指针，长度和容量。

底层源码定义：

1
2
3
4
5
type slice struct {
  array unsafe.Pointer
  len   int
  cap   int
}
  • 指针： 指向 slice 可以访问到的第一个元素。
  • 长度： slice 中元素个数。
  • 容量： slice 起始元素到底层数组最后一个元素间的元素个数。

比如使用 make([]byte, 5) 创建一个切片，它看起来是这样的：

扩容时机与过程

Go 中切片的扩容机制是基于动态数组的，这意味着切片的底层数组会动态调整大小以适应元素的增加。下面是 Go 切片扩容的一般过程：

1.初始分配：

当使用 make 创建一个切片时，Go 会为其分配一块初始的底层数组，并将切片的长度和容量都设置为相同的值。

2.追加元素：

当你使用 append 向切片追加元素时，Go 会检查是否有足够的容量来容纳新的元素。如果有足够的容量，新元素会被添加到底层数组的末尾，切片的长度会增加。如果没有足够的容量，就需要进行扩容。

3.扩容：

当切片需要扩容时，Go 会创建一个新的更大的底层数组（具体的扩容策略看下面扩容原理）。然后，原数组的元素会被复制到新数组中，新元素会被添加到新数组的末尾。最后，切片的引用会指向新的底层数组，原数组会被垃圾回收。
这个扩容的过程保证了在大多数情况下，append 操作都是高效的。由于每次扩容都会涉及元素的复制，因此在涉及大量元素的情况下可能会导致一些性能开销。如果你知道切片需要存储的元素数量，可以使用 make 函数make([]T, length, capacity)的第三个参数显式指定容量，以减少扩容的次数。

扩容原理

Go1.18之前切片的扩容是以容量1024为临界点，当旧容量 < 1024个元素,扩容变成2倍；当旧容量 > 1024个元素，那么会进入一个循环，每次增加25%直到大于期望容量。
然而这个扩容机制已经被Go 1.18弃用了，官方说新的扩容机制能更平滑地过渡。
具体扩容原理分别如下：

Go 1.18版本 之前扩容原理
在分配内存空间之前需要先确定新的切片容量，运行时根据切片的当前容量选择不同的策略进行扩容：

  • 如果期望容量大于当前容量的两倍就会使用期望容量；
  • 如果当前切片的长度小于 1024 就会将容量翻倍；
  • 如果当前切片的长度大于等于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；

Go 1.18版本之后扩容原理

  • 如果期望容量大于当前容量的两倍就会使用期望容量；
  • 如果当前切片的长度小于阈值（默认 256）就会将容量翻倍；
  • 如果当前切片的长度大于等于阈值（默认 256），就会每次增加 25% 的容量，基准是 newcap + 3*threshold，直到新容量大于期望容量；