go语言数据结构和算法库GoSTL

stirling · · 241 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

GoSTL

GoSTL是一个go语言数据结构和算法库,类似C++的STL,但功能更强大。结合go语言的特点,大部分数据结构都实现了线程安全,可以在创建对象的时候通过配置参数指定是否开启。

功能列表

例子

切片(slice)

这个库中的切片是对go原生切片的重定义。
下面是一个如何将go原生的切片转成IntSlice,然后对其排序的例子。

package main

import (
   "fmt"
   "github.com/liyue201/gostl/algorithm/sort"
   "github.com/liyue201/gostl/ds/slice"
   "github.com/liyue201/gostl/utils/comparator"
)

func main() {
   a := slice.IntSlice(make([]int, 0))
   a = append(a, 2)
   a = append(a, 1)
   a = append(a, 3)
   fmt.Printf("%v\n", a)
   
   // sort in ascending
   sort.Sort(a.Begin(), a.End())
   fmt.Printf("%v\n", a)
   
   // sort in descending
   sort.Sort(a.Begin(), a.End(), comparator.Reverse(comparator.BuiltinTypeComparator))
   fmt.Printf("%v\n", a)
}

数组(array)

数组是一种一旦创建长度就固定的数据结构,支持随机访问和迭代器访问。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/ds/array"
)

func main() {
    a := array.New(5)
    for i := 0; i < a.Size(); i++ {
        a.Set(i, i + 1)
    }
    for i := 0; i < a.Size(); i++ {
        fmt.Printf("%v ", a.At(i))
    }

    fmt.Printf("\n")
    for iter := a.Begin(); iter.IsValid(); iter.Next() {
        fmt.Printf("%v ", iter.Value())
    }
}

vector

向量是一种大小可以自动伸缩的数据结构,内部使用切片实现。支持随机访问和迭代器访问。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/algorithm/sort"
    "github.com/liyue201/gostl/ds/vector"
    "github.com/liyue201/gostl/utils/comparator"
)

func main() {
    v := vector.New()
    v.PushBack(1)
    v.PushBack(2)
    v.PushBack(3)
    for i := 0; i < v.Size(); i++ {
        fmt.Printf("%v ", v.At(i))
    }
    fmt.Printf("\n")

    // sort in descending
    sort.Sort(v.Begin(), v.End(), comparator.Reverse(comparator.BuiltinTypeComparator))
    for iter := v.Begin(); iter.IsValid(); iter.Next() {
        fmt.Printf("%v ", iter.Value())
    }
}

列表(list)

  • 简单列表

简单列表是一种单向列表,支持从头部和尾部插入数据,只支持从头部遍历数据。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/ds/list/simple_list"
)

func main() {
    l := simple_list.New()
    l.PushBack(1)
    l.PushFront(2)
    l.PushFront(3)
    l.PushBack(4)
    for n := l.FrontNode(); n != nil; n = n.Next() {
        fmt.Printf("%v ", n.Value)
    }
}
  • 双向列表

双向列表,支持从头部和尾部插入数据,支持从头部和尾部遍历数据。

package main

import (
    "fmt"
    list "github.com/liyue201/gostl/ds/list/bid_list"
)

func main() {
    l := list.New()
    l.PushBack(1)
    l.PushFront(2)
    l.PushFront(3)
    l.PushBack(4)
    for n := l.FrontNode(); n != nil; n = n.Next() {
        fmt.Printf("%v ", n.Value)
    }
    fmt.Printf("\n", )

    for n := l.BackNode(); n != nil; n = n.Prev() {
        fmt.Printf("%v ", n.Value)
    }
}

双端队列(deque)

双端队列支持从头部和尾部高效的插入数据,支持随机访问和迭代器访问。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/algorithm/sort"
    "github.com/liyue201/gostl/ds/deque"
)

func main() {
    q := deque.New()
    q.PushBack(2)
    q.PushFront(1)
    q.PushBack(3)
    q.PushFront(4)
    fmt.Printf("%v\n", q)

    sort.Sort(q.Begin(), q.End())
    fmt.Printf("%v\n", q)
    fmt.Printf("%v\n", q.PopBack())
    fmt.Printf("%v\n", q.PopFront())
    fmt.Printf("%v\n", q)
}

队列(queue)

队列是一种先进先出的数据结构,底层使用双端队列或者链表作为容器,默认使用双端队列,若想使用链表,可以在创建对象时使用queue.WithListContainer()参数。支持线程安全。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/ds/queue"
    "sync"
    "time"
)

func example1()  {
    fmt.Printf("example1:\n")
    q := queue.New()
    for i := 0; i < 5; i++ {
        q.Push(i)
    }
    for !q.Empty() {
        fmt.Printf("%v\n", q.Pop())
    }
}

//  基于链表
func example2()  {
    fmt.Printf("example2:\n")
    q := queue.New(queue.WithListContainer())
    for i := 0; i < 5; i++ {
        q.Push(i)
    }
    for !q.Empty() {
        fmt.Printf("%v\n", q.Pop())
    }
}

// 线程安全
func example3() {
    fmt.Printf("example3:\n")

    s := queue.New(queue.WithThreadSave())
    sw := sync.WaitGroup{}
    sw.Add(2)
    go func() {
        defer sw.Done()
        for i := 0; i < 10; i++ {
            s.Push(i)
            time.Sleep(time.Microsecond * 100)
        }
    }()

    go func() {
        defer sw.Done()
        for i := 0; i < 10; {
            if !s.Empty() {
                val := s.Pop()
                fmt.Printf("%v\n", val)
                i++
            } else {
                time.Sleep(time.Microsecond * 100)
            }
        }
    }()
    sw.Wait()
}

func main() {
    example1()
    example2()
    example3()
}

优先队列(priority_queue)

优先队列基于go标准库的container/heap包实现,支持线程安全。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/ds/priority_queue"
    "github.com/liyue201/gostl/utils/comparator"
)

func main() {
    q := priority_queue.New(priority_queue.WithComparator(comparator.Reverse(comparator.BuiltinTypeComparator)),
        priority_queue.WithThreadSave())
    q.Push(5)
    q.Push(13)
    q.Push(7)
    q.Push(9)
    q.Push(0)
    q.Push(88)
    for !q.Empty() {
        fmt.Printf("%v\n", q.Pop())
    }
}

栈(stack)

栈是一种后进先出的数据结构,底层使用双端队列或者链表作为容器,默认使用双端队列,若想使用链表,可以在创建对象时使用queue.WithListContainer()参数。支持线程安全。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/ds/stack"
    "sync"
    "time"
)

func example1() {
    fmt.Printf("example1:\n")

    s := stack.New()
    s.Push(1)
    s.Push(2)
    s.Push(3)
    for !s.Empty() {
        fmt.Printf("%v\n", s.Pop())
    }
}

// based on list
func example2() {
    fmt.Printf("example2:\n")

    s := stack.New(stack.WithListContainer())
    s.Push(1)
    s.Push(2)
    s.Push(3)
    for !s.Empty() {
        fmt.Printf("%v\n", s.Pop())
    }
}

// thread-save
func example3() {
    fmt.Printf("example3:\n")

    s := stack.New(stack.WithThreadSave())
    sw := sync.WaitGroup{}
    sw.Add(2)
    go func() {
        defer sw.Done()
        for i := 0; i < 10; i++ {
            s.Push(i)
            time.Sleep(time.Microsecond * 100)
        }
    }()

    go func() {
        defer sw.Done()
        for i := 0; i < 10; {
            if !s.Empty() {
                val := s.Pop()
                fmt.Printf("%v\n", val)
                i++
            } else {
                time.Sleep(time.Microsecond * 100)
            }
        }
    }()
    sw.Wait()
}

func main() {
    example1()
    example2()
    example3()
}

红黑树(rbtree)

红黑树是一种平衡二叉排序树,用于高效的插入和查找数据。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/ds/rbtree"
)

func main()  {
    tree := rbtree.New()
    tree.Insert(1, "aaa")
    tree.Insert(5, "bbb")
    tree.Insert(3, "ccc")
    fmt.Printf("find %v returns %v\n",5, tree.Find(5))

    tree.Traversal(func(key, value interface{}) bool {
        fmt.Printf("%v : %v\n", key, value)
        return true
    })
    tree.Delete(tree.FindNode(3))
}

映射(map)

映射底层使用红黑树实现,支持按key顺序迭代访问,有别于go原生的map类型(go原生的map底层是哈希,不支持按key顺序迭代访问)。支持线程安全。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/ds/map"
)

func main() {
    m := treemap.New(treemap.WithThreadSave())

    m.Insert("a", "aaa")
    m.Insert("b", "bbb")

    fmt.Printf("a = %v\n", m.Get("a"))
    fmt.Printf("b = %v\n", m.Get("b"))
    
    m.Erase("b")
}

集合(set)

集合底层使用红黑树实现,支持线程安全。支持集合的基本运算,如求并集,交集,差集。支持线程安全。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/ds/set"
)

func main()  {
    s := set.New(set.WithThreadSave())
    s.Insert(1)
    s.Insert(5)
    s.Insert(3)
    s.Insert(4)
    s.Insert(2)

    s.Erase(4)

    for iter := s.Begin(); iter.IsValid(); iter.Next() {
        fmt.Printf("%v\n", iter.Value())
    }

    fmt.Printf("%v\n", s.Contains(3))
    fmt.Printf("%v\n", s.Contains(10))
}

位映射(bitmap)

位映射用于快速标记和查找一个非负整数是否集合中。相对于map或数组占用内存空间更小。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/ds/bitmap"
)

func main() {
    bm := bitmap.New(1000)
    bm.Set(6)
    bm.Set(10)

    fmt.Printf("%v\n", bm.IsSet(5))
    fmt.Printf("%v\n", bm.IsSet(6))
    bm.Unset(6)
    fmt.Printf("%v\n", bm.IsSet(6))
}

布隆过滤器(bloom_filter)

布隆过滤器用来快速判断数据是否在集合中,底层使用bitmap实现,相对于map占用内存空间更小。缺点是不支持删除和有一定的错误率。支持线程安全。支持数据导出和通过导出的数据重现构建。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/ds/bloomfilter"
)

func main() {
    filter := bloom.New(100, 4, bloom.WithThreadSave())
    filter.Add("hhhh")
    filter.Add("gggg")

    fmt.Printf("%v\n", filter.Contains("aaaa"))
    fmt.Printf("%v\n", filter.Contains("gggg"))
}

哈希映射树(hamt)

哈希映射树相对于传统哈希(开放地址法或链表法哈希),出现哈希冲突的概率更小,空间利用率更高。扩容缩容性时间复杂度低。支持线程安全。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/ds/hamt"
)

func main() {
    h := hamt.New()
    // h := hamt.New(hamt.WithThreadSave())
    key := []byte("aaaaa")
    val := "bbbbbbbbbbbbb"

    h.Insert(key, val)
    fmt.Printf("%v = %v\n", string(key), h.Get(key))

    h.Erase(key)
    fmt.Printf("%v = %v\n", string(key), h.Get(key))
}

一致性哈希(ketama)

一致性哈希ketama算法,使用64位的哈希函数和map存储,出现冲突的概率更小。支持线程安全。

package main

import (
    "github.com/liyue201/gostl/ds/ketama"
    "fmt"
)

func main() {
    k := ketama.New()
    k.Add("1.2.3.3")
    k.Add("2.4.5.6")
    k.Add("5.5.5.1")
    node, _ := k.Get("aaa")
    fmt.Printf("%v\n", node)
    k.Remove("2.4.5.6")
}

跳表(skliplist)

跳表是一种通过以空间换时间来实现快速查找的数据结构。支持线程安全。

package main

import (
    "fmt"
    "github.com/liyue201/gostl/ds/skiplist"
)

func main()  {
    list := skiplist.New(skiplist.WithMaxLevel(15))
    list.Insert("aaa", "1111")
    list.Insert("bbb", "2222")
    fmt.Printf("aaa = %v\n", list.Get("aaa"))
    fmt.Printf("aaa = %v\n\n", list.Get("bbb"))

    list.Traversal(func(key, value interface{}) bool {
        fmt.Printf("key:%v value:%v\n", key, value)
        return true
    })

    list.Remove("aaa")
}

排序、稳定排序、二分查找

Sort: 内部使用的是快速排序算法。
Stable: 稳定排序,内部使用归并排序。
BinarySearch: 通过二分查找,判断一个元素是否在迭代器范围中。
LowerBound: 通过二分查找,找到第一个等于该元素的数据返回该迭代器。
UpperBound: 通过二分查找,找到第一个大于该元素的数据返回该迭代器。

package main

import (
    "github.com/liyue201/gostl/algorithm/sort"
    "github.com/liyue201/gostl/utils/comparator"
    "github.com/liyue201/gostl/ds/slice"
    "fmt"
)

func main()  {
    a := make([]string, 0)
    a = append(a, "bbbb")
    a = append(a, "ccc")
    a = append(a, "aaaa")
    a = append(a, "bbbb")
    a = append(a, "bb")

    sliceA := slice.StringSlice(a)

    ////Sort in ascending order
    sort.Sort(sliceA.Begin(), sliceA.End())
    //sort.Stable(sliceA.Begin(), sliceA.End())
    fmt.Printf("%v\n", a)

    if sort.BinarySearch(sliceA.Begin(), sliceA.End(), "bbbb") {
        fmt.Printf("BinarySearch: found bbbb\n")
    }

    iter := sort.LowerBound(sliceA.Begin(), sliceA.End(), "bbbb")
    if iter.IsValid() {
        fmt.Printf("LowerBound bbbb: %v\n", iter.Value())
    }
    iter = sort.UpperBound(sliceA.Begin(), sliceA.End(), "bbbb")
    if iter.IsValid() {
        fmt.Printf("UpperBound bbbb: %v\n", iter.Value())
    }
    //Sort in descending order
    sort.Sort(sliceA.Begin(), sliceA.End(), comparator.Reverse(comparator.BuiltinTypeComparator))
    //sort.Stable(sliceA.Begin(), sliceA.End(), comparator.Reverse(comparator.BuiltinTypeComparator))
    fmt.Printf("%v\n", a)
}

下个排序组合(next_permutation)

这个函数修改迭代器范围内的数据为下一个排序组合。

package main

import (
    "github.com/liyue201/gostl/algorithm/sort"
    "github.com/liyue201/gostl/ds/slice"
    "github.com/liyue201/gostl/utils/comparator"
    "fmt"
)

func main()  {
    a := slice.IntSlice(make([]int, 0))

    for i := 1; i <= 3; i++ {
        a = append(a, i)
    }
    fmt.Println("NextPermutation")
    for {
        fmt.Printf("%v\n", a)
        if !sort.NextPermutation(a.Begin(), a.End()) {
            break
        }
    }
    fmt.Println("PrePermutation")
    for {
        fmt.Printf("%v\n", a)
        if !sort.NextPermutation(a.Begin(), a.End(), comparator.Reverse(comparator.BuiltinTypeComparator)) {
            break
        }
    }
}

本文来自:Segmentfault

感谢作者:stirling

查看原文:go语言数据结构和算法库GoSTL

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:muxilin131420 备注:入群;或加QQ群:977810755

241 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传