Go标准容器之Ring的使用说明

简介

Go的标准包Container中包含了常用的容器类型,包括conatiner/list,container/heap,container/ring,本篇讲解container/ring的使用。

ring包

ring包提供了环形链表的操作。它仅导出了一个类型,Ring:

// Ring表示环形链表中的元素。
type Ring struct {
    Value interface{} // Value类型为interface{},因此可以接受任意类型
}
// 创建一个长度为n的环形链表
func New(n int) *Ring
// 针对环形链表中的每一个元素x进行f(x)操作
func (r *Ring) Do(f func(interface{}))
// 获取环形链表长度
func (r *Ring) Len() int
// 如果r和s在同一环形链表中,则删除r和s之间的元素,
// 被删除的元素组成一个新的环形链表,返回值为该环形链表的指针(即删除前,r->Next()表示的元素)
// 如果r和s不在同一个环形链表中,则将s插入到r后面,返回值为
// 插入s后,s最后一个元素的下一个元素(即插入前,r->Next()表示的元素)
func (r *Ring) Link(s *Ring) *Ring
// 移动 n % r.Len() 个位置,n正负均可
func (r *Ring) Move(n int) *Ring
// 返回下一个元素
func (r *Ring) Next() *Ring
// 返回前一个元素
func (r *Ring) Prev() *Ring
// 删除r后面的 n % r.Len() 个元素
func (r *Ring) Unlink(n int) *Ring

示例

Ring的用法

package main
import (
    "container/ring"
    "fmt"
)
func main() {
    const rLen = 3
    // 创建新的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
    // 该匿名函数用来打印Ring中的数据
    printRing := func(v interface{}) {
        fmt.Print(v, " ")
    }
    r.Do(printRing) // 0 1 2
    fmt.Println()
    // 将r之后的第二个元素的值乘以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 表示的元素赋值,即第二个元素
    another.Prev().Value = 9 // 给 another - 1 表示的元素赋值,即第三个元素
    another.Do(printRing) // 7 8 9
    fmt.Println()
    // 插入another到r后面,返回插入前r的下一个元素
    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之后的三个元素,返回被删除元素组成的Ring的指针
    result = r.Unlink(3)
    r.Do(printRing) // 0 4
    fmt.Println()
    result.Do(printRing) // 7 8 9
    fmt.Println()
}

模拟约瑟夫问题

环形列表可以模拟约瑟夫问题。约瑟夫问题描述如下:

来自百度:

据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

用代码模拟如下:

package main
import (
    "container/ring"
    "fmt"
)
type Player struct {
    position int  // 位置
    alive    bool // 是否存活
}
func main() {
    const (
        playerCount = 41  // 玩家人数
        startPos    = 1  // 开始报数位置
    )
    deadline := 3
    r := ring.New(playerCount)
    // 设置所有玩家初始值
    for i := 1; i <= playerCount; i++ {
        r.Value = &Player{i, true}
        r = r.Next()
    }
    // 如果开始报数的位置不为1,则设置开始位置
    if startPos > 1 {
        r = r.Move(startPos - 1)
    }
    counter := 1  // 报数从1开始,因为下面的循环从第二个开始计算
    deadCount := 0  // 死亡人数,初始值为0
    for deadCount < playerCount {  // 直到所有人都死亡,否则循环一直执行
        r = r.Next() // 跳到下一个人
        // 如果是活着的人,则报数
        if r.Value.(*Player).alive {
            counter++
        }
        // 如果报数为deadline,则此人淘汰出局
        if counter == deadline {
            r.Value.(*Player).alive = false
            fmt.Printf("Player %d died!\n", r.Value.(*Player).position)
            deadCount++
            counter = 0  // 报数置成0
        }
    }
}

输出如下,可以看到16和31是最后两个出队列的,因此Josephus将他的朋友与自己安排在第16个与第31个位置是安全的。

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!

补充:go语言中container容器数据结构heap、list、ring

heap堆的使用:

package main
import (
    "container/heap"
    "fmt"
)

type IntHeap []int
//我们自定义一个堆需要实现5个接口
//Len(),Less(),Swap()这是继承自sort.Interface
//Push()和Pop()是堆自已的接口

//返回长度
func (h *IntHeap) Len() int {
    return len(*h);
}

//比较大小(实现最小堆)
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];
}

//压入数据
func (h *IntHeap) Push(x interface{}) {
    //将数据追加到h中
    *h = append(*h, x.(int))
}

//弹出数据
func (h *IntHeap) Pop() interface{} {
    old := *h;
    n := len(old);
    x := old[n-1];
    //让h指向新的slice
    *h = old[0: n-1];
    //返回最后一个元素
    return x;
}

//打印堆
func (h *IntHeap) PrintHeap() {
    //元素的索引号
    i := 0
    //层级的元素个数
    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();
    //弹出数据,保证每次操作都是规范的堆结构
    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() {
    //创建一个链表
    l := list.New();

    //链表最后插入元素
    a1 := l.PushBack(1);
    b2 := l.PushBack(2);

    //链表头部插入元素
    l.PushFront(3);
    l.PushFront(4);

    printList(l);

    //取第一个元素
    f := l.Front();
    fmt.Println(f.Value);

    //取最后一个元素
    b := l.Back();
    fmt.Println(b.Value);

    //获取链表长度
    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);

    //移动元素到最后
    l.MoveToBack(a1);
    printList(l);

    //移动元素到头部
    l.MoveToFront(a1);
    printList(l);

    //移动元素在某元素之后
    l.MoveAfter(b2, a1);
    printList(l);

    //移动元素在某元素之前
    l.MoveBefore(b2, a1);
    printList(l);

    //删除某元素
    l.Remove(a1);
    printList(l);
}

ring环的使用:

package main;
import (
    "container/ring"
    "fmt"
)

func printRing(r *ring.Ring) {
    r.Do(func(v interface{}) {
        fmt.Print(v.(int), " ");
    });
    fmt.Println();
}

func main() {
    //创建环形链表
    r := ring.New(5);
    //循环赋值
    for i := 0; i < 5; i++ {
        r.Value = i;
        //取得下一个元素
        r = r.Next();
    }
    printRing(r);
    //环的长度
    fmt.Println(r.Len());

    //移动环的指针
    r.Move(2);

    //从当前指针删除n个元素
    r.Unlink(2);
    printRing(r);

    //连接两个环
    r2 := ring.New(3);
    for i := 0; i < 3; i++ {
        r2.Value = i + 10;
        //取得下一个元素
        r2 = r2.Next();
    }
    printRing(r2);

    r.Link(r2);
    printRing(r);
}

以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。如有错误或未考虑完全的地方,望不吝赐教。

时间: 2021-05-04

golang elasticsearch Client的使用详解

elasticsearch 的client ,通过 NewClient 建立连接,通过 NewClient 中的 Set.URL设置访问的地址,SetSniff设置集群 获得连接 后,通过 Index 方法插入数据,插入后可以通过 Get 方法获得数据(最后的测试用例中会使用 elasticsearch client 的Get 方法) func Save(item interface{}) { client, err := elastic.NewClient( elastic.SetURL("h

goland设置颜色和字体的操作

如下所示: 补充:Goland调整Terminal窗口字体大小 Goland的Ternimal窗口样式和Console窗口公用同一个样式,修改路径: Setting->Editor->Color Scheme->Console Font 若不生效,重启一下IDE即可. 以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们.如有错误或未考虑完全的地方,望不吝赐教.

golang日志包logger的用法详解

1. logger包介绍 import "github.com/wonderivan/logger" 在我们开发go程序的过程中,发现记录程序日志已经不是fmt.print这么简单,我们想到的是打印输出能够明确指定当时运行时间.运行代码段,当然我们可以引入go官方自带包 import "log",然后通过log.Printf.log.Println等方式输出,而且默认是日志输出时只带时间的,想要同时输出所运行代码段位置,还需要通过执行一下指定进行相关简单的设置 lo

浅谈golang 中time.After释放的问题

在谢大群里看到有同学在讨论time.After泄漏的问题,就算时间到了也不会释放,瞬间就惊呆了,忍不住做了试验,结果发现应该没有这么的恐怖的,是有泄漏的风险不过不算是泄漏, 先看API的说明: // After waits for the duration to elapse and then sends the current time // on the returned channel. // It is equivalent to NewTimer(d).C. // The underl

go设置多个GOPATH的方式

go设置多个GOPATH linux: GOPATH="/home/www/gopath1:/home/www/gopath2" windows: GOPATH=f:/gopath1;f:/gopath2; 注意: go get 时默认安装到第一个GOPATH路径 go build时,有时会报同一种类型或方法不匹配,由于多个是GOPATH路径顺序不对导致的,调换一下顺序即可解决 补充:golang 多个项目时如何配置(使用gb在非GOPATH路径下构建项目) 方案1:将每个项目路径写入

go语言中GOPATH GOROOT的作用和设置方式

GOPATH 和 GOROOT 不同于其他语言,go中没有项目的说法,只有包, 其中有两个重要的路径,GOROOT 和 GOPATH GOROOT是安装目录,GOPATH是我们的工作空间, 用来存放包的目录 GOPATH可以设置多个,其中,第一个将会是默认的包目录,使用 go get 下载的包都会在第一个path中的src目录下,使用 go install时,在哪个GOPATH中找到了这个包,就会在哪个GOPATH下的bin目录生成可执行文件 修改 GOPATH 和 GOROOT 安装的时候如果

golang 定时任务方面time.Sleep和time.Tick的优劣对比分析

golang 写循环执行的定时任务,常见的有以下三种实现方式 1.time.Sleep方法: for { time.Sleep(time.Second) fmt.Println("我在定时执行任务") } 2.time.Tick函数: t1:=time.Tick(3*time.Second) for { select { case <-t1: fmt.Println("t1定时器") } } 3.其中Tick定时任务 也可以先使用time.Ticker函数获取

go 类型转换方式(interface 类型的转换)

go 在做类型转换时,报错: cannot convert m (type interface {}) to type Msg: need type assertion 原因: go 的在 interface 类型转换的时候, 不是使用类型的转换, 而是使用 t,ok := i.(T) 例子: //处理网络消息 func ProcessMsg(m interface{}){ //var a interface{} = m //Msg(m) msg := m.(*Msg) 补充:go []inte

C++中4种类型转换方式 cast操作详解

Q:什么是C风格转换?什么是static_cast,dynamic_cast以及reinterpret_cast?区别是什么?为什么要注意? A:转换的含义是通过改变一个变量的类型为别的类型从而改变该变量的表示方式.为了类型转换一个简单对象为另一个对象你会使用传统的类型转换操作符.比如,为了转换一个类型为doubole的浮点数的指针到整型:代码:inti;doubled; i=(int)d;或者: i=int(d); 对于具有标准定义转换的简单类型而言工作的很好.然而,这样的转换符也能不分皂白的

Struts2单选按钮详解及枚举类型的转换代码示例

本文研究的主要是Struts2框架单选按钮详解及枚举类型的转换的相关示例,具体如下. 使用struts2标签,毫无疑问要先引入标签库: <%@ taglib prefix="s" uri="/struts-tags"%> 假设radio单选框中List的值为一个Map集合: <s:radio list="#{'MAN':'男','WOMEN':'女'}" name="gender" listKey="

pytorch使用 to 进行类型转换方式

在程序中,有多种方法进行强制类型转换. 本博文将介绍一个非常常用的方法:to()方法. 我们通常使用它来进行GPU和CPU的类型转换,但其实也可以用来进行torch的dtype转换. 常见方法:tensor.to('cuda:0') 先看官网介绍: **Performs Tensor dtype and/or device conversion. A torch.dtype and torch.device are inferred from the arguments of self.to(*

C语言中自动隐式转换与类型强制转换实例分析

本文通过一个C程序实例对C语言中自动隐式转换与类型强制转换的注意点进行深入分析,详情如下: 先看一个C程序: #include<stdlib.h> #include<stdio.h> #include<conio.h> double proc(int q){ int n; double sum,t;//本例的关键就在这几个变量的类型上 sum = 2.0; while(sum<=q){ t=sum; //sum = sum+(n+1)/n;//自动隐式转换 sum

MySQL隐式类型的转换陷阱和规则

前言 相信大家都知道隐式类型转换有无法命中索引的风险,在高并发.大数据量的情况下,命不中索引带来的后果非常严重.将数据库拖死,继而整个系统崩溃,对于大规模系统损失惨重.所以下面通过本文来好好学习下MySQL隐式类型的转换陷阱和规则. 1. 隐式类型转换实例 今天生产库上突然出现MySQL线程数告警,IOPS很高,实例会话里面出现许多类似下面的sql:(修改了相关字段和值) SELECT f_col3_id,f_qq1_id FROM d_dbname.t_tb1 WHERE f_col1_id=

C++中Operator类型强制转换成员函数解析

类型转换操作符(type conversion operator)是一种特殊的类成员函数,它定义将类类型值转变为其他类型值的转换.转换操作符在类定义体内声明,在保留字 operator 之后跟着转换的目标类型.转换函数又称类型强制转换成员函数,它是类中的一个非静态成员函数.它的定义格式如下: 复制代码 代码如下: class <类型说明符1> { public: operator <类型说明符2>(); - } 这个转换函数定义了由<类型说明符1>到<类型说明符2

浅谈c语言中类型隐性转换的坑

谨记:在C语言中,当两种不同类型之间运算时,低字节长度类型会向高自己长度类型转换,有符号会向无符号类型转换. 举例子如下: #include <stdio.h> void func(void) { int i = 1; unsigned char c1 = 1; signed char c2 = -1; if (c2 > i){ printf("\r\n -1 > 1"); } else{ printf("\r\n -1 <= 1");

基于java中byte数组与int类型的转换(两种方法)

java中byte数组与int类型的转换,在网络编程中这个算法是最基本的算法,我们都知道,在socket传输中,发送.者接收的数据都是 byte数组,但是int类型是4个byte组成的,如何把一个整形int转换成byte数组,同时如何把一个长度为4的byte数组转换为int类型.下面有两种方式. public static byte[] int2byte(int res) { byte[] targets = new byte[4]; targets[0] = (byte) (res & 0xf

浅谈Java数值类型的转换与强制转换

数值类型之间的转换 6个实心箭头箭头表示无信息丢失的转换; 3个虚箭头表示可能有精度损失的转换. 当使用上面两个数值进行二元操作时,先要将两个操作数转换为同一类型,然后再进行计算. 规则:`两个数中小类型的值将自动转换为大类型的值. 小转大可以,但是大转小会损失精度,则需要强制转换. 强制类型转换 语法格式 在圆括号中给出想要转换的目标类型,后面紧跟待转换的变量名. 例: double m = 9.99; int n = (int)m; 其中n的值为9. 强制类型转换通过截断小数部分将浮点值转换

python如何把字符串类型list转换成list

这篇文章主要介绍了python如何吧字符串类型list转换成list,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 python读取了一个list是字符串形式的'[11.23,23.34]',想转换成list类型: 方式一: import ast str_list = "[11.23,23.34]" list_list = ast.literal_eval(str_list) print(type(list_list)) 得到结果为: