Golang: 內建容器的用法

1.數組

數組是值類型

[10]int 和 [20]int是不同類型

調用func(arr [10]int)會拷貝數組

在go語言中一般不直接使用數據

package main
import "fmt"
func updateArr(arr *[5]int) {
	arr[0] = 100
}
func updateArrThroughSlice(arr []int)  {
	arr[0] = 100
}
func main() {
	//創建一個數據
	var arr [5]int
	arr2 := [5]int{1, 2, 3, 4, 5}
	//長度讓編譯器來數
	arr3 := [...]int{1, 2, 3, 4, 5}
	//[0 0 0 0 0] [1 2 3 4 5] [1 2 3 4 5]
	fmt.Println(arr, arr2, arr3)
	//定義二維數組 4行5列
	var arr4 [4][5]int
	//[[0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0]]
	fmt.Println(arr4)
	//遍歷數據
	//for i:=0;i<len(arr3);i++{
	//	fmt.Println(arr3[i])
	//}
	for num, v := range arr2 {
		fmt.Printf("第%d個元素為:%d\n", num, v)
	}
	//數據是值類型,通過指針可以改變值的大小
	fmt.Println("update before")
	fmt.Println(arr2)
	updateArr(&arr2) //傳入arr3的地址
	fmt.Println("update after")
	fmt.Println(arr2)
	
	//通過Slice改變數據
	fmt.Println("update before")
	fmt.Println(arr3)
	updateArrThroughSlice(arr3[:]) //傳入Slice
	fmt.Println("update after")
	fmt.Println(arr3)
}

2.Slice(切片)

2.1 Slice的實現

Slice本身沒有數據,是對底層array的一個view

在這裡插入圖片描述

Slice內部有個指針(ptr)指向開頭的元素,Slice有長度(len),容量(cap);cap代表從指針(ptr)開始到數組(arr)末尾的長度,Slice在擴展的時候不能超過cap.

package main
import "fmt"
func updateSlice(s []int) {
	s[0] = 100
}
func main() {
	arr := [...]int{0, 1, 2, 3, 4, 5, 6, 7}
	//創建一個Slice
	s1 := arr[:]
	s2 := arr[2:6]
	fmt.Printf("s1:%v\ns2:%v\n", s1, s2)
	//改變Slice內部元素
	updateSlice(s2)
	fmt.Println(s2)
	//ReSlice:對Slice再進行一次Slice操作
	s3 := s1[:5]
	fmt.Println(s3)
	s3 = s3[:2]
	fmt.Println(s3)
}

2.2 Slice的擴展

s[i]不可以超越len(i),向後擴展不可以超過底層數組cap(s)

在這裡插入圖片描述

package main
import "fmt"
func updateSlice(s []int) {
	s[0] = 100
}
func main() {
	arr := [...]int{0, 1, 2, 3, 4, 5, 6, 7}
	fmt.Printf("arr=%v\n", arr)
	//Extending Slice 不能超過cap(s)
	s1 := arr[2:6]
	fmt.Printf("s1=%v, len(s1)=%d, cap(s1)=%d\n", s1, len(s1), cap(s1))
	s2 := s1[3:5]
	fmt.Printf("s2=%v, len(s2)=%d, cap(s2)=%d\n", s2, len(s2), cap(s2))
	// s[i]不能超過len(s)
	fmt.Printf("get Slice element:%v",s2[1])
	//panic: runtime error: index out of range [2] with length 2
	//fmt.Printf("get Slice element:%v",s2[2])
}

2.2 Slice的其它操作

向Slice添加元素

package main
import "fmt"
//查看操作系統怎麼擴充Slice的cap
func printSlice(s []int) {
	fmt.Printf("%v, len=%d, cap=%d\n", s, len(s), cap(s))
}
func main() {
	arr := [...]int{0, 1, 2, 3, 4, 5, 6, 7}
	//添加元素時如果超越cap,系統會重新分配更大的底層數組
	//由於值傳遞的關系,必須接收append的返回值
	// s = append(s,val)
	s1 := arr[2:]
	fmt.Printf("s1=%v\n", s1)
	s2 := s1[3:5] //[s1[3], s1[4]]
	fmt.Printf("s2=%v, len(s2)=%d, cap(s2)=%d\n", s2, len(s2), cap(s2))
	s3 := append(s2, 10)
	s4 := append(s3, 11)
	s5 := append(s4, 12)
	fmt.Printf("s3=%v, s4=%v, s5=%v\n", s3, s4, s5)
	// s4 and s5 no longer view arr
	fmt.Printf("arr=%v\n", arr)
	//創建一個Slice
	var s []int
	//Zero value for slice is nil
	for i := 0; i < 100; i++ {
		printSlice(s)
		s = append(s, i*2+1)
	}
	fmt.Println(s)
}

Slice的copy,添加,刪除元素操作

package main
import (
	"fmt"
)
//查看操作系統怎麼擴充Slice的cap
func printSlice(str string, s []int) {
	fmt.Printf("%s=%v, len=%d, cap=%d\n", str, s, len(s), cap(s))
}
func main() {
	//初始化slice
	s1 := []int{2, 4, 6, 8}
	fmt.Println(s1)
	//[2 4 6 8]
	//創建一個len為16的Slice
	s2 := make([]int, 16)
	//創建一個len為10,cap為32的Slice
	s3 := make([]int, 10, 32)
	printSlice("s2", s2)
	//[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0], len=16, cap=16
	printSlice("s3", s3)
	//[0 0 0 0 0 0 0 0 0 0], len=10, cap=32
	//拷貝Slice
	fmt.Println("Copying Slice")
	//dst src
	copy(s2, s1)
	printSlice("s2", s2)
	//[2 4 6 8 0 0 0 0 0 0 0 0 0 0 0 0], len=16, cap=16
	//刪除Slice中的元素
	fmt.Println("Deleting element from slice")
	//刪除下標為3的元素
	//通過...append s2下標為4後的元素
	s2 = append(s2[:3], s2[4:]...)
	printSlice("s2", s2)
	//刪除頭尾元素
	fmt.Println("Popping from front")
	front := s2[0]
	s2 = s2[1:]
	fmt.Println(front)
	fmt.Println(s2)
	fmt.Println("Popping from back")
	tail := s2[len(s2)-1]
	s2 = s2[:len(s2)-1]
	fmt.Println(tail)
	fmt.Println(s2)
}

3.Map

3.1 Map的操作

創建: make(map[string]int)

獲取元素:m[key]

key不存在時,獲得Value類型的初始值

用value,ok := m[key]來判斷是否存在key

用delete刪除一個key

使用range遍歷key,或者遍歷key, value對

不保證遍歷順序,如需順序,需手動對key排序

使用len獲得元素個數

package main
import "fmt"
func main() {
	//創建一個map
	//map中的key是無序的,是一個HashMap
	m := map[string]string{
		"name":    "Cocktail_py",
		"course":  "golang",
		"site":    "CSDN",
		"quality": "pretty well",
	}
	m2 := make(map[string]int) // m2 = empty map
	var m3 map[string]int      // m3 == nil
	fmt.Println(m, m2, m3)
	fmt.Println("Traversing map")
	for k, v := range m {
		fmt.Println(k, v)
	}
	//map 操作
	//獲取元素:m[key]
	fmt.Println("Getting values")
	courseName, ok := m["course"]
	fmt.Println(courseName, ok)
	
	//當key不存在
	if courName, ok := m["courName"]; ok {
		fmt.Println(courName) // Zero value
	} else {
		fmt.Println("key does not exist")
	}
	
	fmt.Println("Deleting values")
	delete(m, "name")
	name, ok := m["name"]
	fmt.Println(name, ok)
}

3.2 Map的key

map使用哈希表,必須可以比較相等

除瞭Slice,map,function的內建類型都可以作為key

Struct類型不包含上述字段,也可作為key

3.3 Map的例題:尋找最長不含有重復字符的子串

在這裡插入圖片描述

/*
當前一個字符串,從左往後開始掃描,隻要掃描一遍就可以,如果掃到X的位置,看到一個字母X應該怎麼做呢
首先,記錄一個start表示當前找到的最長不含有重復字符的子串的開始,保證start到X之前的子串是不含有重復字符的,
之後,需要查看從start到X-1這個位置之間有沒有X,使用一個叫lastOccurred[x]記錄X最後出現的位置在哪裡,使用map會有三種情況:1.x重來沒有出現過,或者x出現在start之前,若x出現在start之前,最長的子串+1; 2.lastOccurred[x]出現在start到X中間,更新start位置,start指向lastOccurred[x+1]的位置
*/
package main
import "fmt"
func lengthOfNonRepeatingSubStr(s string)int  {
	lastOccurred := make(map[byte]int)
	start := 0
	maxLength := 0
	//遍歷字符串 go語言中char類型是使用瞭一種rune(32位)類型
	for x, ch := range []byte(s){
		//lastOccurred[ch]有可能不存在;若不存在出現0,會影響運算
		if lastl, ok:= lastOccurred[ch];ok && lastl >= start{
			start = lastl + 1
		}
		//stat到i結束
		if x-start + 1 > maxLength{
			maxLength = x -start + 1
		}
		lastOccurred[ch] = x
	}
	return maxLength
}
func main() {
	fmt.Println(lengthOfNonRepeatingSubStr("hellohello"))
}

4.rune

rune相當於go的char

使用range遍歷pos,rune對

使用utf8.RuneCountlnString獲得字符數量

使用len獲得字節長度

使用[]byte獲得字節

package main
import (
	"fmt"
	"unicode/utf8"
)
func main() {
	//英文占一個字節,中文占三個字節
	s := "yes我愛CSDN!"
	fmt.Println(len(s)) // 14
	//%X十六進制,大寫字符,每個字節兩個字符
	//796573E68891E788B14353444E21
	fmt.Printf("%X\n",[]byte(s))
	//%T 相應值的類型
	//使用for range遍歷字符串時,會默認將byte(int8)類型轉化為rune(int32)類型,因為go采用UTF-8編碼 可變長的編碼
	for _,b := range s{
		fmt.Printf("%T %X\n",b,b)
	}
	for _,b := range []byte(s){
		fmt.Printf("%T %X\n",b,b)
	}
	//打印字符的個數
	fmt.Println("Rune count:",utf8.RuneCountInString(s))
	bytes := []byte(s)
	fmt.Println(bytes)
	for len(bytes) > 0{
		ch,size := utf8.DecodeRune(bytes)
		bytes = bytes[size:]
		//相應Unicode碼點所表示的字符
		fmt.Printf("%c",ch)
	}
	//獲取第幾個字符是誰
	for i, ch := range []rune(s) {
		fmt.Printf("(%d %c) ", i, ch)
	}
	fmt.Println()
}

4.1 Map的例題:尋找最長不含有重復字符的子串(國際版)

//國際版
func lengthOfNonRepeatingSubStr(s string) int {
	lastOccurred := make(map[rune]int)
	start := 0
	maxLength := 0
	//遍歷字符串 go語言中char類型是使用瞭一種rune(32位)
	//for i, ch := range s{
	for i, ch := range []rune(s) {
		//lastOccurred[ch]有可能不存在;若不存在出現0,會影響運算
		if lastI, ok := lastOccurred[ch]; ok && lastI >= start {
			start = lastI + 1
		}
		//start到i結束
		if i-start+1 > maxLength {
			maxLength = i - start + 1
		}
		lastOccurred[ch] = i
	}
	return maxLength
}

補充:Golang 容器的學習與實踐

Golang 提供瞭幾個簡單的容器供我們使用,本文在介紹幾種 Golang 容器的基礎上,實現一個基於 Golang 容器的LRU算法。

容器介紹

Golang 容器位於 container 包下,提供瞭三種包供我們使用,heap、list、ring. 下面我們分別學習。

heap

heap 是一個堆的實現。一個堆正常保證瞭獲取/彈出最大(最小)元素的時間為log n、插入元素的時間為 log n.

Golang堆實現接口如下:

// src/container/heap.go
type Interface interface {
 sort.Interface
 Push(x interface{}) // add x as element Len()
 Pop() interface{} // remove and return element Len() - 1.
}

heap 是基於 sort.Interface 實現的。

// src/sort/
type Interface interface {
 Len() int
 Less(i, j int) bool
 Swap(i, j int)
}

因此,如果要使用官方提供的 heap,需要我們實現如下幾個接口:

Len() int {} // 獲取元素個數
Less(i, j int) bool  {} // 比較方法
Swap(i, j int) // 元素交換方法
Push(x interface{}){} // 在末尾追加元素
Pop() interface{} // 返回末尾元素

然後在使用時,我們可以使用如下幾種方法:

// 初始化一個堆
func Init(h Interface){}
// push一個元素倒堆中
func Push(h Interface, x interface{}){}
// pop 堆頂元素
func Pop(h Interface) interface{} {}
// 刪除堆中某個元素,時間復雜度 log n
func Remove(h Interface, i int) interface{} {}
// 調整i位置的元素位置(位置I的數據變更後)
func Fix(h Interface, i int){}

list 鏈表

list 實現瞭一個雙向鏈表,鏈表不需要實現 heap 類似的接口,可以直接使用。

鏈表的構造:

// 返回一個鏈表對象
  func New() *List {}

官方提供瞭豐富的方法供我們操作列表,方法如下:

// 返回鏈表的長度
func (l *List) Len() int {}
// 返回鏈表中的第一個元素
func (l *List) Front() *Element {}
// 返回鏈表中的末尾元素
func (l *List) Back() *Element {}
// 移除鏈表中的某個元素
func (l *List) Remove(e *Element) interface{} {}
// 在表頭插入值為 v 的元素
func (l *List) PushFront(v interface{}) *Element {}
// 在表尾插入值為 v 的元素
func (l *List) PushBack(v interface{}) *Element {}
// 在mark之前插入值為v 的元素
func (l *List) InsertBefore(v interface{}, mark *Element) *Element {}
// 在mark 之後插入值為 v 的元素
func (l *List) InsertAfter(v interface{}, mark *Element) lement {}
// 移動e某個元素到表頭
func (l *List) MoveToFront(e *Element) {}
// 移動e到隊尾
func (l *List) MoveToBack(e *Element) {}
// 移動e到mark之前
func (l *List) MoveBefore(e, mark *Element) {}
// 移動e 到mark 之後
func (l *List) MoveAfter(e, mark *Element) {}
// 追加到隊尾
func (l *List) PushBackList(other *List) {}
// 將鏈表list放在隊列前
func (l *List) PushFrontList(other *List) {}

我們可以通過 Value 方法訪問 Element 中的元素。除此之外,我們還可以用下面方法做鏈表遍歷:

// 返回下一個元素
func (e *Element) Next() *Element {}
// 返回上一個元素
func (e *Element) Prev() *Element {}
下面是隊列的遍歷的例子:
// l 為隊列,
for e := l.Front(); e != nil; e = e.Next() {
  //通過 e.Value 做數據訪問
}

ring 循環列表

container 中的循環列表是采用鏈表實現的。

// 構造一個包含N個元素的循環列表
func New(n int) *Ring {}
// 返回列表下一個元素
func (r *Ring) Next() *Ring {}
// 返回列表上一個元素
func (r *Ring) Prev() *Ring {}
// 移動n個元素 (可以前移,可以後移)
func (r *Ring) Move(n int) *Ring {}
// 把 s 鏈接到 r 後面。如果s 和r 在一個ring 裡面,會把r到s的元素從ring 中刪掉
func (r *Ring) Link(s *Ring) *Ring {}
// 刪除n個元素 (內部就是ring 移動n個元素,然後調用Link)
func (r *Ring) Unlink(n int) *Ring {}
// 返回Ring 的長度,時間復雜度 n
func (r *Ring) Len() int {}
// 遍歷Ring,執行 f 方法 (不建議內部修改ring)
func (r *Ring) Do(f func(interface{})) {}

訪問 Ring 中元素,直接 Ring.Value 即可。

容器的使用

下面,我們通過 map 和 官方包中的雙向鏈表實現一個簡單的 lru 算法,用來熟悉golang 容器的使用。

LRU 算法 (Least Recently Used),在做緩存置換時用的比較多。逐步淘汰最近未使用的 cache,而使我們的緩存中持續保持著最近使用的數據。

package main 
import "fmt"
import "container/list"
 
// lru 中的數據
type Node struct {
  K, V interface{}
}
 
// 鏈表 + map
type LRU struct {
  list *list.List
  cacheMap map[interface{}]*list.Element
  Size int
}
 
// 初始化一個LRU
func NewLRU(cap int) *LRU {
  return &LRU{
    Size: cap,
    list: list.New(),
    cacheMap: make(map[interface{}]*list.Element, cap),
  }
}
 
// 獲取LRU中數據
func (lru *LRU) Get(k interface{}) (v interface{}, ret bool) {
  // 如果存在,則把數據放到鏈表最前面
  if ele, ok := lru.cacheMap[k]; ok {
    lru.list.MoveToFront(ele)
    return ele.Value.(*Node).V, true
  }
  return nil, false
}
// 設置LRU中數據
func (lru *LRU) Set(k, v interface{}) {
  // 如果存在,則把數據放到最前面
  if ele, ok := lru.cacheMap[k]; ok {
    lru.list.MoveToFront(ele)
    ele.Value.(*Node).V = v // 更新數據值
    return
  }
  // 如果數據是滿的,先刪除數據,後插入
  if lru.list.Len() == lru.Size {
    last := lru.list.Back()
    node := last.Value.(*Node)
    delete(lru.cacheMap, node.K)
    lru.list.Remove(last)
  }  ele := lru.list.PushFront(&Node{K: k, V: v})
  lru.cacheMap[k] = ele
}

註意事項

上述的容器都不是 goroutines 安全的

1、上面的lr 也不是 goroutines 安全的

2、Ring 中不建議在 Do 方法中修改 Ring 的指針,行為是未定義的

以上為個人經驗,希望能給大傢一個參考,也希望大傢多多支持WalkonNet。如有錯誤或未考慮完全的地方,望不吝賜教。