Ring怎么在Golang中使用

今天就跟大家聊聊有關(guān)Ring怎么在Golang中使用，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

golang的優(yōu)點(diǎn)

golang是一種編譯語(yǔ)言，可以將代碼編譯為機(jī)器代碼，編譯后的二進(jìn)制文件可以直接部署到目標(biāo)機(jī)器而無(wú)需額外的依賴(lài)，所以golang的性能優(yōu)于其他的解釋性語(yǔ)言，且可以在golang中使用goroutine來(lái)實(shí)現(xiàn)并發(fā)性，它提供了一個(gè)非常優(yōu)雅的goroutine調(diào)度程序系統(tǒng)，可以很容易地生成數(shù)百萬(wàn)個(gè)goroutine。

ring包

ring包提供了環(huán)形鏈表的操作。它僅導(dǎo)出了一個(gè)類(lèi)型，Ring：

// Ring表示環(huán)形鏈表中的元素。
type Ring struct {
    Value interface{} // Value類(lèi)型為interface{}，因此可以接受任意類(lèi)型
}
// 創(chuàng)建一個(gè)長(zhǎng)度為n的環(huán)形鏈表
func New(n int) *Ring
// 針對(duì)環(huán)形鏈表中的每一個(gè)元素x進(jìn)行f(x)操作
func (r *Ring) Do(f func(interface{}))
// 獲取環(huán)形鏈表長(zhǎng)度
func (r *Ring) Len() int
// 如果r和s在同一環(huán)形鏈表中，則刪除r和s之間的元素，
// 被刪除的元素組成一個(gè)新的環(huán)形鏈表，返回值為該環(huán)形鏈表的指針（即刪除前，r->Next()表示的元素）
// 如果r和s不在同一個(gè)環(huán)形鏈表中，則將s插入到r后面，返回值為
// 插入s后，s最后一個(gè)元素的下一個(gè)元素（即插入前，r->Next()表示的元素）
func (r *Ring) Link(s *Ring) *Ring
// 移動(dòng) n % r.Len() 個(gè)位置，n正負(fù)均可
func (r *Ring) Move(n int) *Ring
// 返回下一個(gè)元素
func (r *Ring) Next() *Ring
// 返回前一個(gè)元素
func (r *Ring) Prev() *Ring
// 刪除r后面的 n % r.Len() 個(gè)元素
func (r *Ring) Unlink(n int) *Ring

示例

Ring的用法

package main
import (
    "container/ring"
    "fmt"
)
func main() {
    const rLen = 3
    // 創(chuàng)建新的Ring
    r := ring.New(rLen)
    for i := 0; i < rLen; i++ {
        r.Value = i
        r = r.Next()
    }
    fmt.Printf("Length of ring: %d\n", r.Len()) // Length of ring: 3
    // 該匿名函數(shù)用來(lái)打印Ring中的數(shù)據(jù)
    printRing := func(v interface{}) {
        fmt.Print(v, " ")
    }
    r.Do(printRing) // 0 1 2
    fmt.Println()
    // 將r之后的第二個(gè)元素的值乘以2
    r.Move(2).Value = r.Move(2).Value.(int) * 2
    r.Do(printRing) // 0 1 4
    fmt.Println()
    // 刪除 r 與 r+2 之間的元素，即刪除 r+1
    // 返回刪除的元素組成的Ring的指針
    result := r.Link(r.Move(2))
    r.Do(printRing) // 0 4
    fmt.Println()
    result.Do(printRing) // 1
    fmt.Println()
    another := ring.New(rLen)
    another.Value = 7
    another.Next().Value = 8 // 給 another + 1 表示的元素賦值，即第二個(gè)元素
    another.Prev().Value = 9 // 給 another - 1 表示的元素賦值，即第三個(gè)元素
    another.Do(printRing) // 7 8 9
    fmt.Println()
    // 插入another到r后面，返回插入前r的下一個(gè)元素
    result = r.Link(another)
    r.Do(printRing) // 0 7 8 9 4
    fmt.Println()
    result.Do(printRing) // 4 0 7 8 9
    fmt.Println()
    // 刪除r之后的三個(gè)元素，返回被刪除元素組成的Ring的指針
    result = r.Unlink(3)
    r.Do(printRing) // 0 4
    fmt.Println()
    result.Do(printRing) // 7 8 9
    fmt.Println()
}

模擬約瑟夫問(wèn)題

環(huán)形列表可以模擬約瑟夫問(wèn)題。約瑟夫問(wèn)題描述如下：

來(lái)自百度：

據(jù)說(shuō)著名猶太歷史學(xué)家 Josephus有過(guò)以下的故事：在羅馬人占領(lǐng)喬塔帕特后，39 個(gè)猶太人與Josephus及他的朋友躲到一個(gè)洞中，39個(gè)猶太人決定寧愿死也不要被敵人抓到，于是決定了一個(gè)自殺方式，41個(gè)人排成一個(gè)圓圈，由第1個(gè)人開(kāi)始報(bào)數(shù)，每報(bào)數(shù)到第3人該人就必須自殺，然后再由下一個(gè)重新報(bào)數(shù)，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個(gè)人開(kāi)始，越過(guò)k-2個(gè)人（因?yàn)榈谝粋€(gè)人已經(jīng)被越過(guò)），并殺掉第k個(gè)人。接著，再越過(guò)k-1個(gè)人，并殺掉第k個(gè)人。這個(gè)過(guò)程沿著圓圈一直進(jìn)行，直到最終只剩下一個(gè)人留下，這個(gè)人就可以繼續(xù)活著。問(wèn)題是，給定了和，一開(kāi)始要站在什么地方才能避免被處決？Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個(gè)與第31個(gè)位置，于是逃過(guò)了這場(chǎng)死亡游戲。

用代碼模擬如下：

package main
import (
    "container/ring"
    "fmt"
)
type Player struct {
    position int  // 位置
    alive    bool // 是否存活
}
func main() {
    const (
        playerCount = 41  // 玩家人數(shù)
        startPos    = 1  // 開(kāi)始報(bào)數(shù)位置
    )
    deadline := 3
    r := ring.New(playerCount)
    // 設(shè)置所有玩家初始值
    for i := 1; i <= playerCount; i++ {
        r.Value = &Player{i, true}
        r = r.Next()
    }
    // 如果開(kāi)始報(bào)數(shù)的位置不為1，則設(shè)置開(kāi)始位置
    if startPos > 1 {
        r = r.Move(startPos - 1)
    }
    counter := 1  // 報(bào)數(shù)從1開(kāi)始，因?yàn)橄旅娴难h(huán)從第二個(gè)開(kāi)始計(jì)算
    deadCount := 0  // 死亡人數(shù)，初始值為0
    for deadCount < playerCount {  // 直到所有人都死亡，否則循環(huán)一直執(zhí)行
        r = r.Next() // 跳到下一個(gè)人
        // 如果是活著的人，則報(bào)數(shù)
        if r.Value.(*Player).alive {
            counter++
        }
        // 如果報(bào)數(shù)為deadline，則此人淘汰出局
        if counter == deadline {
            r.Value.(*Player).alive = false
            fmt.Printf("Player %d died!\n", r.Value.(*Player).position)
            deadCount++
            counter = 0  // 報(bào)數(shù)置成0
        }
    }
}

輸出如下，可以看到16和31是最后兩個(gè)出隊(duì)列的，因此Josephus將他的朋友與自己安排在第16個(gè)與第31個(gè)位置是安全的。

Player 3 died!
Player 6 died!
Player 9 died!
Player 12 died!
Player 15 died!
Player 18 died!
Player 21 died!
Player 24 died!
Player 27 died!
Player 30 died!
Player 33 died!
Player 36 died!
Player 39 died!
Player 1 died!
Player 5 died!
Player 10 died!
Player 14 died!
Player 19 died!
Player 23 died!
Player 28 died!
Player 32 died!
Player 37 died!
Player 41 died!
Player 7 died!
Player 13 died!
Player 20 died!
Player 26 died!
Player 34 died!
Player 40 died!
Player 8 died!
Player 17 died!
Player 29 died!
Player 38 died!
Player 11 died!
Player 25 died!
Player 2 died!
Player 22 died!
Player 4 died!
Player 35 died!
Player 16 died!
Player 31 died!

補(bǔ)充：go語(yǔ)言中container容器數(shù)據(jù)結(jié)構(gòu)heap、list、ring

heap堆的使用：

package main 
import (
    "container/heap"
    "fmt"
)
 
type IntHeap []int 
//我們自定義一個(gè)堆需要實(shí)現(xiàn)5個(gè)接口
//Len(),Less(),Swap()這是繼承自sort.Interface
//Push()和Pop()是堆自已的接口
 
//返回長(zhǎng)度
func (h *IntHeap) Len() int {
    return len(*h);
}
 
//比較大小(實(shí)現(xiàn)最小堆)
func (h *IntHeap) Less(i, j int) bool {
    return (*h)[i] < (*h)[j];
}
 
//交換值
func (h *IntHeap) Swap(i, j int) {
    (*h)[i], (*h)[j] = (*h)[j], (*h)[i];
}
 
//壓入數(shù)據(jù)
func (h *IntHeap) Push(x interface{}) {
    //將數(shù)據(jù)追加到h中
    *h = append(*h, x.(int))
}
 
//彈出數(shù)據(jù)
func (h *IntHeap) Pop() interface{} {
    old := *h;
    n := len(old);
    x := old[n-1];
    //讓h指向新的slice
    *h = old[0: n-1];
    //返回最后一個(gè)元素
    return x;
}
 
//打印堆
func (h *IntHeap) PrintHeap() {
    //元素的索引號(hào)
    i := 0
    //層級(jí)的元素個(gè)數(shù)
    levelCount := 1
    for i+1 <= h.Len() {
        fmt.Println((*h)[i: i+levelCount])
        i += levelCount
        if (i + levelCount*2) <= h.Len() {
            levelCount *= 2
        } else {
            levelCount = h.Len() - i
        }
    }
}
 
func main() {
    a := IntHeap{6, 2, 3, 1, 5, 4};
    //初始化堆
    heap.Init(&a);
    a.PrintHeap();
    //彈出數(shù)據(jù)，保證每次操作都是規(guī)范的堆結(jié)構(gòu)
    fmt.Println(heap.Pop(&a));
    a.PrintHeap();
    fmt.Println(heap.Pop(&a));
    a.PrintHeap();
    heap.Push(&a, 0);
    heap.Push(&a, 8);
    a.PrintHeap();
}

list鏈表的使用：

package main; 
import (
    "container/list"
    "fmt"
)
 
func printList(l *list.List) {
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value, " ");
    }
    fmt.Println();
}
 
func main() {
    //創(chuàng)建一個(gè)鏈表
    l := list.New();
 
    //鏈表最后插入元素
    a1 := l.PushBack(1);
    b2 := l.PushBack(2);
 
    //鏈表頭部插入元素
    l.PushFront(3);
    l.PushFront(4);
 
    printList(l);
 
    //取第一個(gè)元素
    f := l.Front();
    fmt.Println(f.Value);
 
    //取最后一個(gè)元素
    b := l.Back();
    fmt.Println(b.Value);
 
    //獲取鏈表長(zhǎng)度
    fmt.Println(l.Len());
 
    //在某元素之后插入
    l.InsertAfter(66, a1);
 
    //在某元素之前插入
    l.InsertBefore(88, a1);
 
    printList(l);
 
    l2 := list.New();
    l2.PushBack(11);
    l2.PushBack(22);
    //鏈表最后插入新鏈表
    l.PushBackList(l2);
    printList(l);
 
    //鏈表頭部插入新鏈表
    l.PushFrontList(l2);
    printList(l);
 
    //移動(dòng)元素到最后
    l.MoveToBack(a1);
    printList(l);
 
    //移動(dòng)元素到頭部
    l.MoveToFront(a1);
    printList(l);
 
    //移動(dòng)元素在某元素之后
    l.MoveAfter(b2, a1);
    printList(l);
 
    //移動(dòng)元素在某元素之前
    l.MoveBefore(b2, a1);
    printList(l);
 
    //刪除某元素
    l.Remove(a1);
    printList(l);
}

ring環(huán)的使用：

package main; 
import (
    "container/ring"
    "fmt"
)
 
func printRing(r *ring.Ring) {
    r.Do(func(v interface{}) {
        fmt.Print(v.(int), " ");
    });
    fmt.Println();
}
 
func main() {
    //創(chuàng)建環(huán)形鏈表
    r := ring.New(5);
    //循環(huán)賦值
    for i := 0; i < 5; i++ {
        r.Value = i;
        //取得下一個(gè)元素
        r = r.Next();
    }
    printRing(r);
    //環(huán)的長(zhǎng)度
    fmt.Println(r.Len());
 
    //移動(dòng)環(huán)的指針
    r.Move(2);
 
    //從當(dāng)前指針刪除n個(gè)元素
    r.Unlink(2);
    printRing(r);
 
    //連接兩個(gè)環(huán)
    r2 := ring.New(3);
    for i := 0; i < 3; i++ {
        r2.Value = i + 10;
        //取得下一個(gè)元素
        r2 = r2.Next();
    }
    printRing(r2);
 
    r.Link(r2);
    printRing(r);
}

看完上述內(nèi)容，你們對(duì)Ring怎么在Golang中使用有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。