golang高性能双端队列(ring-buffer)插件库deque的使用

golang高性能双端队列(ring-buffer)插件库deque的使用

简介

deque是一个基于环形缓冲区(ring-buffer)实现的高性能双端队列(double-ended queue)库。它支持在队列两端高效地添加和删除元素，时间复杂度为O(1)。

安装

$ go get github.com/gammazero/deque

数据结构

Deque同时支持队列(FIFO)和栈(LIFO)操作：

  • 队列操作：使用PushBack和PopFront
  • 栈操作：使用PushBack和PopBack

环形缓冲区性能

该实现针对CPU和GC性能进行了优化：

  • 缓冲区大小按2的幂次方自动调整
  • 使用位运算进行计算
  • 可以设置基础容量(SetBaseCap)避免小规模调整
  • 可以预先扩容(Grow)以避免添加元素时的调整

相比基于切片或链表的实现，环形缓冲区减少了GC停顿，提高了内存和时间性能。

泛型支持

Deque使用泛型来创建特定类型的队列：

stringDeque := new(deque.Deque[string])
var intDeque deque.Deque[int]

示例代码

package main

import (
    "fmt"
    "github.com/gammazero/deque"
)

func main() {
    var q deque.Deque[string]
    q.PushBack("foo")  // 后端添加元素
    q.PushBack("bar")
    q.PushBack("baz")

    fmt.Println(q.Len())   // 输出: 3
    fmt.Println(q.Front()) // 输出: foo
    fmt.Println(q.Back())  // 输出: baz

    q.PopFront() // 移除前端元素"foo"
    q.PopBack()  // 移除后端元素"baz"

    q.PushFront("hello") // 前端添加元素
    q.PushBack("world")  // 后端添加元素

    // 遍历并消费队列
    for q.Len() != 0 {
        fmt.Println(q.PopFront())
    }
}

使用场景

Deque可以用作：

  • 队列(Queue)：使用PushBack和PopFront
  • 栈(Stack)：使用PushBack和PopBack

注意事项

  • 从空队列读取会panic，使用前应先检查Len()
  • 并发安全需要由应用层保证

更多关于golang高性能双端队列(ring-buffer)插件库deque的使用的实战教程也可以访问 https://www.itying.com/category-94-b0.html

1 回复

更多关于golang高性能双端队列(ring-buffer)插件库deque的使用的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


Golang高性能双端队列(deque)使用指南

什么是双端队列(deque)

双端队列(Deque, Double-ended queue)是一种具有队列和栈性质的数据结构，支持在两端高效地进行插入和删除操作。在Go语言中，标准库没有直接提供deque实现，但可以通过第三方库如gammazero/deque来使用高性能双端队列。

gammazero/deque库介绍

gammazero/deque是一个基于环形缓冲区(ring-buffer)实现的高性能双端队列库，具有以下特点：

  • O(1)时间复杂度的头部/尾部插入和删除
  • 自动扩容和缩容
  • 内存高效
  • 线程不安全(需自行加锁)

安装

go get github.com/gammazero/deque

基本使用示例

package main

import (
	"fmt"
	"github.com/gammazero/deque"
)

func main() {
	// 创建一个新的双端队列
	var dq deque.Deque[string]

	// 向尾部添加元素
	dq.PushBack("world")
	dq.PushBack("!")

	// 向头部添加元素
	dq.PushFront("Hello")

	// 遍历队列
	fmt.Println("Queue contents:")
	for i := 0; i < dq.Len(); i++ {
		fmt.Printf("%d: %s\n", i, dq.At(i))
	}

	// 从头部弹出元素
	fmt.Println("\nPop from front:")
	for dq.Len() > 0 {
		fmt.Println(dq.PopFront())
	}

	// 重新填充队列
	dq.PushBack("a")
	dq.PushBack("b")
	dq.PushBack("c")

	// 从尾部弹出元素
	fmt.Println("\nPop from back:")
	for dq.Len() > 0 {
		fmt.Println(dq.PopBack())
	}
}

高级功能

1. 设置初始容量

// 创建初始容量为100的双端队列
dq := deque.New[string](100)

2. 批量操作

// 批量添加元素到尾部
items := []string{"one", "two", "three"}
dq.PushBackMany(items...)

// 批量添加元素到头部
dq.PushFrontMany(items...)

3. 元素访问

// 获取但不移除头部元素
if dq.Len() > 0 {
	first := dq.Front()
	fmt.Println("Front:", first)
}

// 获取但不移除尾部元素
if dq.Len() > 0 {
	last := dq.Back()
	fmt.Println("Back:", last)
}

// 随机访问
if dq.Len() > 2 {
	third := dq.At(2)
	fmt.Println("Third element:", third)
}

4. 清空队列

dq.Clear()

性能优化技巧

  1. 预分配容量：如果知道大致元素数量，创建时指定容量可减少扩容开销
  2. 批量操作：使用PushFrontMany和PushBackMany比单个添加更高效
  3. 避免频繁扩容：大量操作时可临时禁用自动缩容
// 临时禁用自动缩容
dq.SetMinCapacity(1000)
// 执行大量操作...
// 恢复自动缩容
dq.SetMinCapacity(0)

线程安全使用

deque本身不是线程安全的，需要自行加锁：

import "sync"

type SafeDeque struct {
	dq deque.Deque[string]
	mu sync.Mutex
}

func (sd *SafeDeque) PushFront(item string) {
	sd.mu.Lock()
	defer sd.mu.Unlock()
	sd.dq.PushFront(item)
}

// 其他方法类似...

与其他实现的比较

  1. 标准库list：container/list是链表实现，内存开销大，随机访问慢
  2. slice模拟：用slice模拟deque，头部操作需要移动元素，效率低
  3. ring-buffer实现：gammazero/deque在大多数场景下性能最优

适用场景

  • 需要频繁在两端添加/删除元素的场景
  • 滑动窗口算法
  • 广度优先搜索(BFS)
  • 实现工作窃取(work-stealing)队列

总结

gammazero/deque提供了高性能的双端队列实现，适合需要高效头部/尾部操作的场景。通过合理使用初始容量和批量操作，可以进一步优化性能。在多线程环境下使用时，记得添加适当的同步机制。

回到顶部