Go语言4

主要内容：

• 内置函数、递归函数、闭包
• 数组与切片
• map数据结构
• package介绍

内置函数

内置函数，是 go 语言直接支持的，可以直接使用，不用导入包：

• close ： 主要用来关闭channel
• len ： 求长度，比如：string、array、slice、map、channel，这些数据结构都有长度
• new ： 分配内存，主要用来分配值类型，比如：int、struct。返回的是指针
• make ： 分配内存，主要用来分配引用类型，比如：chan、map、slice
• append ： 用来追加元素到数组、切片中
• panic 和 recover ： 用来做错误处理

new 的示例：

package main

import "fmt"

func main() {
    a := new(int)
    fmt.Println(a, *a)
    *a = 100
    fmt.Println(a, *a)
}

错误处理的示例：

package main

import (
    "fmt"
    "time"
)

func error1(){
    var zero int = 0
    res := 100 / zero
    fmt.Println(res)
}

func error2(){
    // 写一个defer的匿名函数，捕获异常
    defer func() {
        if err := recover(); err != nil {
            fmt.Println(err)
        }
    }()
    var zero int = 0
    res := 100 / zero
    fmt.Println(res)
}

func main() {
    //error1()  // 执行这个函数，直接就报异常退出了
    error2()  // 这里的异常被捕获了，可以正常执行完毕
    // 生产环境里的服务一般是这么做的，永远不会跳出来，一直运行下去
    for {
        error2()
        time.Sleep(time.Second)
    }
}

递归函数

一个函数调用自己，就叫做递归。

递归的设计原则：

• 一个大问题能够分解成相似的小问题
• 定义好出口条件

递归计算阶乘：

package main

import "fmt"

// 用递归方式定义阶乘：0!=1，n!=(n-1)!×n
func calc(n int) int {
    if n == 0 {
        return 1
    }
    return calc(n - 1) * n
}

func main(){
    res := calc(10)
    fmt.Println(res)
}

尾递归

定义：如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。

具体就是满足这两点，当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。

大多数现代的编译器会利用这种特点自动生成优化的代码。 当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。如果递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。

上面这段太枯燥了，说白了就是： 不压栈的递归 ，放心用。

尾递归计算阶乘：

package main

import "fmt"

// 0的阶乘是1，不计算了直接返回结果
// 每次递归前把当前的计算结果传给参数res
// 比如计算10的阶乘，第一次res=10*1
// 然后递归到9的时候，res=9*10*1
// 最后递归到1的时候，res=1*2*...*9*10*1，此时返回res就是阶乘的结果
func calc(n int, res int) int {
    if n == 0 {
        return 1
    } else if n == 1 {
        return res
    }
    return calc(n-1, n * res)
}

func main(){
    res := calc(10, 1)
    fmt.Println(res)
}

精髓就是：通过参数传递结果，达到不压栈的目的。 我的理解，这样似乎和写一个for循环一样了。差别大概就是某些情况下可读性可能会更好，还有就是装逼。如果写不出来，大概可以先写成for循环，然后改成尾递归？

尾递归的斐波那契数列：

package main

import "fmt"

func fib(first int, second int, n int) int {
    if n <= 2 {
        return 1
    } else if n == 3 {
        return first + second
    }
    return fib(second, first + second, n - 1)
}

func main() {
    fmt.Print("请输入一个小一点的正整数：")
    var n int
    fmt.Scanf("%d\n", &n)
    fmt.Println(fib(1, 1, n))
}

这里第二个参数存结果，然后第三个参数相当于就是for循环里的计数。用for循环的话就是下面这样：

func fib2(n int) int {
    first := 1
    second := 1
    var tmp int
    for i := n; i >= 3; i-- {
        tmp = first
        first = second
        second = tmp + second
    }
    return second
}

上面的逻辑是参照尾递归写的，正常的逻辑，一般是这样的：

func fib3(n int) int {
    first := 1
    second := 1
    var ret int
    for i := 3; i <= n; i++ {
        ret = first + second
        first = second
        second = ret
    }
    return ret
}

闭包

闭包：一个函数和与其相关的引用环境组合而成的实体。

结合下面的例子讲一下：

package main

import "fmt"

// 下面这个是闭包
// 下面这个函数的返回值是一个函数
// 并且返回的函数时一个int参数和一个int返回值
func Adder() func(int) int {
    var x int
    return func (delta int) int {
        x += delta
        return x
    }
}

func main() {
    f := Adder()
    fmt.Println(f(1))
    fmt.Println(f(10))
    fmt.Println(f(10))
}

/* 执行结果
H:\Go\src\go_dev\day4\functions>go run adder.go
1
11
21

H:\Go\src\go_dev\day4\functions>
*/

每次执行后，闭包中x变量的值都会保存下来。下次再调用的时候，会沿用上次的x的值，而不是重新定一个新的x变量。所以第一次x初始值是0，计算后x是1并返回。第二次x初始值是1，计算后x是11并返回。第三次x初始值是11，计算后x是21并返回。

闭包的另一个例子：

package main

import (
    "fmt"
    "strings"
)

func makeSuffixFunc(suffix string) func(string) string {
    return func(name string) string {
        if !strings.HasSuffix(name, suffix){
            return name + suffix
        }
        return name
    }
}

func main(){
    f1 := makeSuffixFunc(".bmp")
    f2 := makeSuffixFunc(".jpg")
    fmt.Println(f1("test1"))
    fmt.Println(f2("test2"))
    fmt.Println(f1("test3.bmp"))
}

/* 执行结果
H:\Go\src\go_dev\day4\functions>go run suffix.go
test1.bmp
test2.jpg
test3.bmp

H:\Go\src\go_dev\day4\functions>
*/

数组

for i := 0; i < len(a); i++ {
}

for i, v := range a {
}

数组是值类型，因此改变副本的值，不会改变数组本身的值：

package main

import "fmt"

func modify(arr [5]int){
    arr[0] = 100
}

func main() {
    var a [5]int
    modify(a)
    for i := 0; i < len(a); i++ {
        fmt.Print(a[i], ", ")
    }
    fmt.Println()
}

/* 执行结果
H:\Go\src\go_dev\day4\array_slice>go run array.go
0, 0, 0, 0, 0,

H:\Go\src\go_dev\day4\array_slice>
5个元素都是初始值0，modify里改变的是副本的值
*/

数组初始化

package main 

import "fmt"

func main(){
    var a1 [5]int = [5]int{1,2,3,4,5}
    var a2 [5]int = [5]int{1,2,3}  // 不写全的话，没写的就是0
    var a3 = [5]int{1,2,3,4}  // var里没写类型，不过后面做了初始化，可以推导
    var a4 = [...]int{1,2,3,4,5,6}  // 用[...]推导长度，这里初始化了6个元素，数组长度是6
    var a5 = [5]int{0: 1, 4: 5}  // 使用下标，跳着初始化部分值
    fmt.Println(a1)
    fmt.Println(a2)
    fmt.Println(a3)
    fmt.Println(a4)
    fmt.Println(a5)
}

/* 执行结果
H:\Go\src\go_dev\day4\array_slice>go run array_init.go
[1 2 3 4 5]
[1 2 3 0 0]
[1 2 3 4 0]
[1 2 3 4 5 6]
[1 0 0 0 5]

H:\Go\src\go_dev\day4\array_slice>
*/

多维数组

定义二维数组： var arg [5][3]int 。

初始化： var arg [2][3]int = [2][3]int{{1, 2, 3}, {4, 5, 6}} 。

切片

切片：是数组的一个引用，因此 切片是引用类型 。

切片的长度可以改变，因此切片是一个可变的数组。

内置函数cap可以求出slice的最大的容量

定义切片：var 变量名 []类型，比如： var s1 []string 、 var a1 []int 。

切片是数组的一个引用的示例：

package main

import "fmt"

func main() {
    var slice []int
    var arr [5]int = [...]int{1,2,3,4,5}
    slice = arr[2:3]  // 包含从开头到结尾的元素，包括开头的元素，不包括结尾的元素
    fmt.Println(slice)
}

用cap求最大容量的示例：

package main

import "fmt"

func main() {
    var slice []int
    fmt.Println(slice, len(slice), cap(slice))
    slice = append(slice, 1)
    fmt.Println(slice, len(slice), cap(slice))
    slice = append(slice, 2)
    fmt.Println(slice, len(slice), cap(slice))

    var slice2 []int = []int{1,2,3}
    fmt.Println(slice2, len(slice2), cap(slice2))
    slice2 = append(slice2, 4)
    fmt.Println(slice2, len(slice2), cap(slice2))
}

/* 执行结果
H:\Go\src\go_dev\day4\array_slice>go run slice_cap.go
[] 0 0
[1] 1 1
[1 2] 2 2
[1 2 3] 3 3
[1 2 3 4] 4 6

H:\Go\src\go_dev\day4\array_slice>
*/

如果往切片里添加元素，并且切片的容量不够了，则会自动扩容。

切片初始化

var slice []int = arr[start: end]  // 包含start到end之间的元素，包括start，不包括end
var slice []int = arr[0: end]
var slice []int = arr[: end]  // 上面的简写
var slice []int = arr[start: len{arr)]  // 包含start之后所有的元素
var slice []int = arr[start:]  // 上面的简写
var slice []int = arr[0: len(arr)]  // 就是arr所有的元素
var slice []int = arr[:]  // 上面的简写

把切片最后一个元素去掉，可以这么写：

slice = slice[: len(slice)-1]

通过make来创建切片

上面都是通过数组创建切片，切片是数组的引用。

还可以通过make创建切片，当然也有数组，不过是隐藏在底层的，我们不需要知道：

var slice []type = make([]type, len)
slice := make([]type, len)
slice := make([]type, len, cap)  // 还有第三个可选参数，设置切片的容量

操作切片（追加）

可以用内置函数 appned 往切片里追加元素：

slice = append(slice, 10)

// 还可以追加多个元素，把一个切片里的元素，展开追加到另一个切片里：
var a = []int{1,2,3}
var b = []ing{4,5,6}
a = append(a, b...)  // 把切片展开追加
a = append(a, 7, 8, 9)  // 还能用可变参数，也是一次追加多个元素

数组与切片

package main

import "fmt"

func main() {
    var a [5]int = [...]int{1,2,3,4,5}  // 定义一个数组
    s := a[:]  // 切片引用这个数组
    a[1] = 22  // 修改数组的元素，切片也会受影响
    fmt.Printf("%p %p %v\n", &a, s, s)  // 打印切片和数组的地址，是一样的
    s = s[: len(s)-1]  // 这里切到了最后一个元素，不会影响数组，接着看再次追加的情况
    fmt.Printf("%p %p %v\n", &a, s, s)
    s = append(s, 6)  // 切片里追加一个元素。追加的内存区域还是数组的最后一个元素的，所以数组会变
    fmt.Printf("%p %p %v\n", &a, s, s)
    s = append(s, 6)  // 这次追加会导致切片超出数组的边界
    a[2] = 33  // 现在改数组，影响不到切片了
    fmt.Printf("%p %p %v\n", &a, s, s)
    fmt.Println(a)
}

/* 执行结果
H:\Go\src\go_dev\day4\array_slice>go run slice_addr.go
0xc04206a030 0xc04206a030 [1 22 3 4 5]
0xc04206a030 0xc04206a030 [1 22 3 4]
0xc04206a030 0xc04206a030 [1 22 3 4 6]
0xc04206a030 0xc0420860f0 [1 22 3 4 6 6]
[1 22 33 4 6]

H:\Go\src\go_dev\day4\array_slice>
*/

切片是数组的引用，开始切片和数组是同一块内存区域。如果改变数组的元素，也就是改变了切片的对应元素。

切片的长度可变，可以任意改变长度，只要不超出被引用数组的范围，都没问题。使用同一块内存，修改一个的值，同时也就是修改另一个的值。

最后当切片超出数组的边界时，会为切片单独开辟一块内存，把值都复制过去。此时不在和原来的数字使用相同的内存了。修改一个的值，也不再影响到另一个了。

切片的拷贝

使用内置函数copy，可以实现切片的拷贝：

s1 := []int{1, 2, 3, 4, 5}
s2 := make([]int, 10)
copy(s2, s1)  // 把s1拷贝到s2里去

拷贝如果容量不足，虽然不会报错，但是切片也不会扩容，放不下的元素就不拷贝了。

string 与 slice

string 底层就是一个byte的slice，因此可以进行切片操作。

package main

import "fmt"

func main() {
    s0 := "Hello World"
    s1 := s0[:5]
    s2 := s0[6:]
    fmt.Println(s1)
    fmt.Println(s2)
}

但是字符串里的元素是不可变的，下面的方法操作会报错：

s := "Hello World"
s[0] = 'h'  // 这句是无法操作的，换成双引号的话类型都错了，错的更多

改变string中的字符，需要先转成切片类型，修改之后再把类型转回去：

package main

import "fmt"

func main() {
    str1 := "Hello World"
    tmp1 := []byte(str1)
    tmp1[0] = 'h'
    str1 = string(tmp1)
    fmt.Println(str1)

    // 考虑到非ASCII字符，就不能转成[]byte类型了，要用[]rune类型
    str2 := "Hello World，你好 世界"
    tmp2 := []rune(str2)
    tmp2[4] = '0'
    tmp2[6] = '我'
    tmp2[12] = '他'
    str2 = string(tmp2)
    fmt.Println(str2)
}

排序

排序操作主要都在 sort 包中：

sort.Ints
sort.Strings
sort.Float64s

不能操作数组，只能对切片进行排序。不过数组可以方便的转成切片：

package main

import (
    "sort"
    "fmt"
)

func main() {
    var a = [...]int{7,4,8,5,2,4,6,1,5}  // 定义a是个数组
    sort.Ints(a[:])  // 传进去 排序 的是引用数组a的切片
    fmt.Printf("%T %T\n", a, a[:])  // 看看类型
    fmt.Println(a)  // 之前讲过，切片和数组是同一块内存，所以数组也一样变了
}

查找

上面的几种类型对应的索引方法如下，都是在a里搜索x，返回x的下标：

sort.SearchInts(a []int, x int)
sort.SearchStrings(a []string, x string)
sort.SearchFloat64s(a []float6, x float64)

这并不是一个查找的方法。而是使用二分查找法在切片a中查找到适合x插入的索引的值。当然如果x是在切片a中的话，返回索引值就是x的位置了。不过切片a需要先排序。如果没有排序的话，不会报错，但是二分查找就不准了，返回值也不对。

所以要先进行排序，然后再查找索引：

package main

import (
    "sort"
    "fmt"
)

func main() {
    var a = [...]string{"x", "y", "z", "c", "b", "a"}
    sort.Strings(a[:])  // 要先排序，否则有问题
    index := sort.SearchStrings(a[:], "y")  // y排序后的下标是4
    fmt.Println(index)  // 值是4
    index = sort.SearchStrings(a[:], "e")  // 没有e，它的索引位置应该改c后面
    fmt.Println(index)  // 值是3
}

返回0的话就是在最前面，返回数组的长度，就是在最后面。如果不先进行排序的话，对这个无序的数组进行二分查找会有问题，最终返回6，就是在数组的最后。

实现查找的方法

还确实是一个查找的方法，而且是快速查找的方法，不用遍历就能完成查找。需要下面3步：

• 先排序
• 再获得索引值
• 最后，比较索引位置的元素和被查找的元素

map 数据结构

map，是一种 key: value 的数据结构，又叫字典或关联数组。 map 是引用类型

声明语法： var name map[KeyType]ValueType 。声明是不会分配内存的，初始化需要make。

var a map[string]string
var b map[string]int
var c map[int]string
var d map[string]map[string]string  // value的类型也是一个map

初始化

下面是各种初始化的方法：

// 定义，然后初始化
var m1 map[string]string
m1 = make(map[string]string)

// 用 :=
m2 := make(map[string]string)

// 定义后直接初始化
var m3 map[string]string = make(map[string]string)

// 直接赋初始值，就不用make来分配内存了，会自动帮我么分配空间
var m1 map[string]string
m1 = map[string]string{"key": "value"}
m2 := map[string]string{"key": "value"}
var m3 map[string]string = map[string]string{"key": "value"}

使用make分配内存，还可以加第二个参数。在初始化的时候，可以指定map的容量。自动扩容是很方便不过会牺牲性能。根据情况，在初始化时分配足够的容量，执行过程中不会出现需要扩容的情况。这样性能是最高的：

var m1 map[string]string
m1 = make(map[string]string, 10)

map 相关操作

var m map[string]string = make(map[string]string, 10)

// 插入和更新
m["k1"] = "val1"

// 查找，val是查找到的value值，ok则是返回的状态，是否有找到
val, ok := m["k1 "]

// 遍历
for k, v := rang a {
    fmt.Println(k, v)
}

// 删除
delete(a, "k1")

// 长度
len(m)

由map组成的slice

主要是初始化的问题。没有引用数组的切片要先初始化。并且切片中的每一个元素都是map，每个map也都有先初始化之后才能使用。可以用for循环，一次把所有元素的map初始化都完成。也可以每次用之前先判断，通过 nil 来判断是否已经初始化了，没有就先初始化：

package main

import "fmt"

func main() {
    var s1 []map[string]int  // s是一个切面，里面的元素是map
    s1 = make([]map[string]int, 5)  // 这个切片没有引用数组，需要make初始化
    s1[0] = make(map[string]int)  // 切片的每个元素都是map，都需要初始化
    s1[0]["k1"] = 10
    fmt.Println(s1)

    s2 := make([]map[string]int, 5)
    // 通过for循环，把切片里的每个map都进行初始化
    for i, _ := range s2 {
        s2[i] = make(map[string]int)
    }
    s2[0]["k1"] = 10
    s2[0]["k2"] = 20
    s2[1]["k3"] = 31
    fmt.Println(s2)

    s3 := make([]map[string]int, 5)
    // 每次用之前判断是否能有初始化，没有进先初始化在用
    if s3[3] == nil {
        s3[3] = make(map[string]int)
    }
    s3[3]["k3"] = 30
    fmt.Println(s3)
}

map 排序

map是无序的，每次输出的时候，每次元素出现的顺序都可能变。如果想每次遍历的顺序都一样，就需要自己排序。

并没有提供给map排序的方法，需要自己一步一步自己实现：

• 先获取所有的key，把key进行排序
• 按照排序好的key，进行查找

package main

import (
    "fmt"
    "sort"
)

func main() {
    m := map[string]int{
        "a": 1,
        "b": 2,
        "c": 3,
        "d": 4,
        "e": 5,
    }
    fmt.Println(m)  // 打印mao，元素的位置每次会变化
    // 先把key都提取出来
    var keys []string
    for k, _ := range m {
        keys = append(keys, k)
    }
    sort.Strings(keys)  // 对key排序
    // 通过排序后的key来遍历字典，下面for循环遍历的结果每次都一样
    for _, v := range keys {
        fmt.Println(v, m[v])
    }
}

map 反转

把map的key和value互换。需要另外定义一个map存放反转后的map。

package main

import "fmt"

func main() {
    var m1 = map[int]string{
        1: "k1",
        2: "k2",
        3: "k3",
        4: "k4",
        5: "k5",
    }
    fmt.Println(m1)

    var m2 = make(map[string]int, 5)
    for k, v := range m1 {
        m2[v] = k
    }
    fmt.Println(m2)
}

sync 包

关于包

Golang 目前有150个标准包，覆盖了几乎所有的基础库。官网 golang.org 有所有包的文档，可以去翻一下。

线程同步使用 sync 包。

sync 包提供了互斥锁这类的基本的同步原语.

不加锁

先看下不加锁的情况，起多个goroute，同时操作一个map，比如下面这样：

package main

import (
    "fmt"
    //"time"
)

func main() {
    pipe := make(chan int, 1000)
    var count int = 0
    for i := 0; i < 1000; i++ {
        go func(n *int, p chan int){
            *n++
            //time.Sleep(time.Millisecond)  // 加点延迟，效果会很明显
            p <- *n
        }(&count, pipe)
    }
    for i := 0; i < 1000; i++ {
        res := <- pipe
        fmt.Println(res)
        //break  // 下面用-race参数执行的时候，放开注释，避免过多的结果打印顶掉打印的竞争信息
    }
}

上面的程序执行后，执行到最后打印的也不是1000。

使用 -race 参数编译执行

编译执行还有个-race参数，会启动数据竞争检测

-race >enable data race detection. >Supported only on linux/amd64, freebsd/amd64, darwin/amd64 and windows/amd64.

使用 -race 参数编译执行上面的代码，就会检测到数据竞争：

H:\Go\src\go_dev\day4\sync>go run -race test.go
==================
WARNING: DATA RACE
Read at 0x00c04200e0a0 by goroutine 7:
  main.main.func1()
      H:/Go/src/go_dev/day4/sync/test.go:13 +0x46

Previous write at 0x00c04200e0a0 by goroutine 6:
  main.main.func1()
      H:/Go/src/go_dev/day4/sync/test.go:13 +0x5f

Goroutine 7 (running) created at:
  main.main()
      H:/Go/src/go_dev/day4/sync/test.go:12 +0xc0

Goroutine 6 (finished) created at:
  main.main()
      H:/Go/src/go_dev/day4/sync/test.go:12 +0xc0
==================
1
Found 1 data race(s)
exit status 66

H:\Go\src\go_dev\day4\sync>

使用竞争检测后，执行的结果倒是真正确了。不过代码本身还是有问题，需要用别的方法来解决竞争的问题。

加锁

这2个锁是用的最多的：

var mu sync.Mutex
var mu sync.RWMutex

上面的代码，加上互斥锁后就没有问题了：

package main

import (
    "fmt"
    "time"
    "sync"
)

var lock sync.Mutex
func main() {
    pipe := make(chan int, 10000)
    var count int = 0
    for i := 0; i < 1000; i++ {
        go func(n *int, p chan int){
            lock.Lock()
            *n++
            time.Sleep(time.Millisecond)  // 加点延迟，效果会很明显
            p <- *n
            lock.Unlock()
        }(&count, pipe)
    }
    for i := 0; i < 1000; i++ {
        res := <- pipe
        fmt.Println(res)
    }
}

上面的所换成读写锁，效果也是一样的，而且示例主要也是写操作

读写锁

如果是一个读的线程拿到了锁，其他读的线程还是可以继续访问这个资源的。但是如果是一个写的线程拿到了锁，那么效果就和互斥锁一样了。

在有大量读操作的时候，加读写锁性能会比互斥锁高很多。互斥锁即使是读操作也会阻止其他的线程的读访问。

var rwlock sync.RWMutex
relock.Rlock()  // 读操作加锁
relock.RUnlock()  // 释放一次读操作的锁
relock.Lock()  // 写操作加锁
relock.Unlock()  // 释放写操作的锁

atomic 包

import "sync/atomic"

atomic 包提供了底层的原子性内存原语，这对于同步算法的实现很有用

通过原子操作一样可以解决上面的竞争问题。在上面的例子中，有下面2行代码：

*n++
p <- *n

// 上面的2步操作换成原子操作
p <- atomic.AddInt32(n, 1)

这两行代码在cpu里可能并不是一起执行的。之前中间加一个sleep也是为了保证cpu在2个时间片中分别执行这2行代码。这样使得在n计算完成后，它可能被别的线程又调用了，然后再回到下面的代码把n保存起来。

原子操作就是保证了这2条语句所要执行的动作：计算+赋值，是像原子一样不可再分。在cpu中不会被打断，一定是计算和赋值都完成后，cpu才会做线程的切换。

上面的示例用原子操作改写：

package main

import (
    "fmt"
    "sync/atomic"
)

func main() {
    pipe := make(chan int32, 1000)
    var count int32 = 0
    for i := 0; i < 1000; i++ {
        go func(n *int32, p chan int32){
            //*n++
            //p <- *n
            p <- atomic.AddInt32(n, 1)  // 计算+赋值作为原子操作
        }(&count, pipe)
    }
    for i := 0; i < 1000; i++ {
        res := <- pipe
        fmt.Println(res)
    }
}

课后作业

一、实现一个冒泡排序

二、实现一个选择排序

三、实现一个插入排序

四、实现一个快速排序

这里有算法和排序的 python 笔记： http://blog.51cto.com/steed/2152725