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> */
陣列
陣列:是同一種資料型別的固定長度的序列
陣列定義:var a [len]int
,比如:var a [5]int
陣列可以通過下標訪問,下標從0開始。訪問越界,如果下標在陣列的合法範圍之外,則丟擲異常訪問越界。
下面是遍歷陣列的2種寫法:
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筆記:ofollow,noindex" target="_blank">http://blog.51cto.com/steed/2152725