Go

3兄弟-Ring

Go, iT邦鐵人賽11Th


這隻又跑出來了XD
Ring其實就是雙向環鏈(circular doubled linked list)

用這圖, 是想表達, 我們有一個歌單
可以單向依序放到完, 當然也能選擇循環依序播放阿 !!!
Ring可以滿足這行為的操作!!
​

Ring

只有一個Value屬性,開發者可以任意操作.
prev, next都是給操作方法操作用的.

1
2
3
4
type Ring struct {
    next, prev *Ring
    Value      interface{} 
}

​

Ring vs List

可以發現Ring的結構跟List超像.

  • 結構差別是List是由List和Element類別兩個聯合表示; 而Ring自己就能代表值和關聯.
  • Ring一開始要指定初始元素個數, 被創建出來後, 長度就不可變; 但List則不必, 也沒這必要.
  • 通過var聲明的Ring的零值是長度為1的環鏈; 而List的零值則是長度為0的雙向鏈結, 因為只有root ptr, 並沒有指向任何元素.
  • Ring的Len()是O(N), 它需要把每個元素走訪一次直到走到自己; List的則是O(1), 因為有個len變數在紀錄長度. 這在某些情境上, 大大影響效能.
    ​

    初始化

  1. 透過New(size), 生出長度為size的Ring

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    // New creates a ring of n elements.
    func New(n int) *Ring {
        if n <= 0 {
            return nil
        }
        r := new(Ring)
        p := r
        for i := 1; i < n; i++ {
            p.next = &Ring{prev: p}
            p = p.next
        }
        p.next = r
        r.prev = p
        return r
    }
    ​
    func (r *Ring) init() *Ring {
        r.next = r
        r.prev = r
        return r
    }

  2. 透過宣告, 生出長度為1的Ring

    1
    var ring變數 ring.Ring

​

操作方法

  • 透過next取得下一個元素

    1
    func (r *Ring) Next() *Ring {...}

  • 透過prev取得前一個元素

    1
    func (r *Ring) Prev() *Ring {...}

  • 讓目前環鏈依據目前所在的元素位置, 往前(n<0)或是往後(n>0)移動數個位置

    1
    func (r *Ring) Move(n int) *Ring {...}

  • 讓目前的環鏈與另一個環鏈作連結, s會插入到r目前指向的元素後面, 返回插入前, r.Next()所表示的元素
    如果r跟s指向的是同一個ring, 就會刪掉r跟s之間的元素,
    被刪掉的元素會組成一個新的ring, 返回的就是指向這新ring的指針

    1
    func (r *Ring) Link(s *Ring) *Ring {...}

  • 從當前環鏈所在的Next()依序刪除n個元素, 返回值是被刪除的元素們

    1
    func (r *Ring) Unlink(n int) *Ring {...}

  • 取得環鏈元素個數, 複雜度為O(N)

    1
    func (r *Ring) Len() int {...}

  • 傳入一個函數, Do會依序地讓每個元素的Value當作參數去執行該函數; 類似JS的map()
    也能透過累加數值在外部變數上
    或者實做策略模式, 執行每個元素的封裝行為.
    但要避免函數f去改變了r, 會發生不可預期的行為.

    1
    func (r *Ring) Do(f func(interface{})) {...}

基本範例

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package main
​
import (
    "container/ring"
    "fmt"
)
​
// 宣告一個要給Do()執行的函數, 用來列印值而已
var printRing = func(v interface{}) {
    fmt.Print(v.(int), "->")
}
​
// 只是用來呼叫r.Do跟代入printRing, 只是多一個換行
func PrintRing(r *ring.Ring) {
    r.Do(printRing)
    fmt.Println()
}
​
func main() {
    // 透過var 來宣告ring
    var varRing ring.Ring
    // 查看透過var宣告的ring的長度
    fmt.Println("查看透過var宣告的ring的長度: ", varRing.Len())
    fmt.Println("----------------------")
    //透過New創建10個元素的ring
    r := ring.New(10)
    // 查看透過New()初始化ring的長度
    fmt.Println("查看透過New()初始化ring的長度: ", r.Len())
    // 給ring中每個元素進行走訪並且給值
    for i := 0; i < 10; i++ {
        r.Value = i
        // 取得下一個元素
        r = r.Next()
    }
    fmt.Print("r : ")
    PrintRing(r)
​
    // 往後移動ring的指向
    r = r.Move(2)
    fmt.Println("ring 向後移動2個位置的元素值:", r.Value)
​
    // 往前移動ring的指向
    r = r.Move(-8)
    fmt.Println("ring 向前移動8個位置的元素值:", r.Value)
​
    // 從ring當前指向開始刪除n個元素
    deletedElm := r.Unlink(2)
    fmt.Print("r 所剩下的元素 : ")
    PrintRing(r)
    fmt.Print("從r刪除的元素 : ")
    PrintRing(deletedElm)
​
    // 準備第2個ring r2
    r2 := ring.New(3)
    for i := 0; i < 3; i++ {
        r2.Value = i + 10
        r2 = r2.Next()
    }
    fmt.Print("r2 : ")
    PrintRing(r2)
​
    fmt.Println("現在r的指向在 :", r.Value)
    // Link r 跟 r2
    fmt.Print("Link r 跟 r2 : ")
    linkedRing := r.Link(r2)
    PrintRing(r)
​
    // 以原本r.Next()開始走訪
    fmt.Print("以原本r.Next()開始走訪 : ")
    PrintRing(linkedRing)
}
/*
查看透過var宣告的ring的長度:  1
----------------------
查看透過New()初始化ring的長度:  10
r : 0->1->2->3->4->5->6->7->8->9->
ring 向後移動2個位置的元素值: 2
ring 向前移動8個位置的元素值: 4
r 所剩下的元素 : 4->7->8->9->0->1->2->3->
從r刪除的元素 : 5->6->
r2 : 10->11->12->
現在r的指向在 : 4
Link r 跟 r2 : 4->10->11->12->7->8->9->0->1->2->3->
以原本r.Next()開始走訪 : 7->8->9->0->1->2->3->4->10->11->12->
*/

輪播範例

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package main
​
import (
    "container/ring"
    "fmt"
    "time"
)
​
// song類別
type song struct {
    name   string
    artist string
    length time.Duration
}
​
// 定義歌單
var (
    songs = []song{
        {
            name:   "Something Just Like This",
            artist: "The Chainsmokers",
            length: 247,
        },
        {
            name:   "Blame",
            artist: "Calvin Harris",
            length: 214,
        },
        {
            name:   "Wolves",
            artist: "Selena Gomez",
            length: 197,
        },
        {
            name:   "Sing You To Sleep",
            artist: "Matt Cab",
            length: 236,
        },
    }
)
​
func main() {
    // 載入歌單
    songList := ring.New(len(songs))
    repeatedCnt := 0
​
    for i := 0; i < songList.Len(); i++ {
        songList.Value = songs[i]
        songList = songList.Next()
    }
​
   // 開始播放
    for {
        if repeatedCnt == 1 {
            break
        }
        songList.Do(func(v interface{}) {
            time.Sleep((v.(song).length / 100) * time.Second) // 加速播放
            fmt.Printf("現正播放%s, 演唱者為%s\n", v.(song).name, v.(song).artist)
        })
        repeatedCnt++
        fmt.Printf("播放次數 : %d\n", repeatedCnt)
    }
​
    fmt.Println("播放完畢")
}
/*
現正播放Something Just Like This, 演唱者為The Chainsmokers
現正播放Blame, 演唱者為Calvin Harris
現正播放Wolves, 演唱者為Selena Gomez
現正播放Sing You To Sleep, 演唱者為Matt Cab
播放次數 1: 
現正播放Something Just Like This, 演唱者為The Chainsmokers
現正播放Blame, 演唱者為Calvin Harris
現正播放Wolves, 演唱者為Selena Gomez
現正播放Sing You To Sleep, 演唱者為Matt Cab
播放次數 2: 
現正播放Something Just Like This, 演唱者為The Chainsmokers
現正播放Blame, 演唱者為Calvin Harris
現正播放Wolves, 演唱者為Selena Gomez
現正播放Sing You To Sleep, 演唱者為Matt Cab
播放次數 3: 
播放完畢
*/

​

3兄弟各自適合的使用場景

  1. List
    • FIFO queue
  2. Heap
    • 排序
    • Priority queue
    • 定時器
  3. Ring
    • 上面提到的輪播
    • 保存近n筆操作日誌
      ​
      應該還有更多, 我暫時還沒想到, 歡迎大家補充給我.
      感謝各位.

鐵人賽連結

分享到