www.zhblog.net

ring 包


对于环状数据结构,Go 提供了container/ring包,Ring结构有Value字段,可以使用New指定元素数量来创建实例,可用的方法有:

func (r *Ring) Do(f func(interface{}))  // 遍历每个元素并传入 f
func (r *Ring) Len() int                // 元素数量
func (r *Ring) Link(s *Ring) *Ring      // 衔接另一个 Ring
func (r *Ring) Move(n int) *Ring        // 移动 n 个元素,n 可正或负
func (r *Ring) Next() *Ring             // 下一个链(也就是下一个元素)
func (r *Ring) Prev() *Ring             // 上一个链(也就是上一个元素)
func (r *Ring) Unlink(n int) *Ring      // 解除指定数量的 Ring,返回被解除的子链

因为是环状结构,每个元素都可视为一个链的开头或结尾,因此Link等操作都返回*Ring。底下是个创建Ring并设值的简单范例:

package main

import (
    "fmt"
    "container/ring"
)

func main() {
    numbers := ring.New(10)
    for i := 0; i < numbers.Len(); i++ {
        numbers.Value = i
        numbers = numbers.Next()
    }

    numbers.Do(func(n interface{}) {
        fmt.Printf("%d ", n.(int))
    })
}

ring的官方文件有相关方法的范例,这边就不重复列出了,实际应用上,ring可以用来管理有限笔数的历史记录、轮播等。

这边的话拿来解一下约瑟夫问题(Josephus Problem)好了:

package main

import (
    "fmt"
    "container/ring"
)

type Person struct {
    Number int
}

func main() {
    persons := ring.New(41)
    // 给每个人编号
    for i := 1; i <= persons.Len(); i++ {
        persons.Value = &Person{i}
        persons = persons.Next()    
    }

    persons = persons.Prev()

    // 最后只留下两人
    for persons.Len() > 2 {
        for i := 1; i <= 2; i++ {
            persons = persons.Next()
        }
        // 报数 3 Out
        persons.Unlink(1)
    }

    fmt.Print("安全位置:")
    persons.Do(func(p interface{}) {
        person := p.(*Person)
        fmt.Printf("%d ", person.Number)
    })
}




展开阅读全文

评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 心情