golang高性能双端队列数据结构插件库deque的使用

golang高性能双端队列数据结构插件库deque的使用

概述

Deque是一个高度优化的双端队列，与list.List相比，在从开头或结尾添加/删除元素时效率更高。

基准测试

PushBack/Deque<harden>       100000000       12.0 ns/op       8 B/op      0 allocs/op
PushBack/Deque                20000000       55.5 ns/op      24 B/op      1 allocs/op
PushBack/list.List             5000000      158.7 ns/op      56 B/op      1 allocs/op

PushFront/Deque<harden>      195840157        9.2 ns/op       8 B/op      0 allocs/op
PushFront/Deque               30000000       49.2 ns/op      24 B/op      1 allocs/op
PushFront/list.List            5000000      159.2 ns/op      56 B/op      1 allocs/op

Random/Deque<harden>          65623633       15.1 ns/op       0 B/op      0 allocs/op
Random/Deque                  50000000       24.7 ns/op       4 B/op      0 allocs/op
Random/list.List              30000000       46.9 ns/op      28 B/op      1 allocs/op

开始使用

go get -u github.com/edwingeng/deque

使用示例

package main

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

func main() {
	// 创建新双端队列
	dq := deque.NewDeque()
	
	// 向后添加元素
	dq.PushBack(100)
	dq.PushBack(200)
	dq.PushBack(300)
	
	// 从前端弹出元素直到队列为空
	for !dq.Empty() {
		fmt.Println(dq.PopFront())
	}
	
	// 向前添加元素
	dq.PushFront(100)
	dq.PushFront(200)
	dq.PushFront(300)
	
	// 按长度遍历并弹出元素
	for i, n := 0, dq.Len(); i < n; i++ {
		fmt.Println(dq.PopFront())
	}
	
	// 输出:
	// 100
	// 200
	// 300
	// 300
	// 200
	// 100
}

强化元素数据类型

./harden.sh <outputDir> <packageName> [elemType]

注意：如果你使用的是Go 1.18或更高版本，请使用v2版本（泛型版本）。


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

1 回复

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


Golang高性能双端队列Deque的使用指南

双端队列(Deque)是一种支持在头部和尾部高效插入和删除元素的数据结构。在Golang中，有几个高性能的Deque实现库可供选择。下面我将介绍最常用的gammazero/deque库的使用方法。

1. 安装deque库

首先需要安装该库：

go get github.com/gammazero/deque

2. 基本使用示例

package main

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

func main() {
	var d deque.Deque[string]
	
	// 向尾部添加元素
	d.PushBack("world")
	d.PushBack("!")
	
	// 向头部添加元素
	d.PushFront("Hello")
	
	// 遍历队列
	fmt.Println("Queue contents:")
	for i := 0; i < d.Len(); i++ {
		fmt.Printf("%d: %v\n", i, d.At(i))
	}
	
	// 从头部移除元素
	front := d.PopFront()
	fmt.Println("\nFront element:", front)
	
	// 从尾部移除元素
	back := d.PopBack()
	fmt.Println("Back element:", back)
	
	// 查看剩余元素
	fmt.Println("\nRemaining elements:", d.Len())
}

3. 主要API方法

gammazero/deque提供了以下常用方法：

  • PushFront(value T) - 在队列头部插入元素
  • PushBack(value T) - 在队列尾部插入元素
  • PopFront() T - 移除并返回头部元素
  • PopBack() T - 移除并返回尾部元素
  • Front() T - 返回头部元素(不移除)
  • Back() T - 返回尾部元素(不移除)
  • At(index int) T - 返回指定位置的元素
  • Len() int - 返回队列长度
  • Cap() int - 返回队列容量
  • SetMinCapacity(minCapacity int) - 设置最小容量
  • Clear() - 清空队列

4. 性能优化特性

gammazero/deque具有以下高性能特性：

  1. 自动扩容/缩容：根据需要自动调整内部存储空间
  2. 环形缓冲区：使用环形缓冲区实现，减少内存分配
  3. 零内存分配：在已有容量内操作时不会分配新内存
  4. 类型安全：使用泛型实现，避免类型断言

5. 高级使用示例

package main

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

func main() {
	// 初始化时指定容量
	d := deque.New[int](32)
	
	// 批量添加元素
	for i := 0; i < 100; i++ {
		if i%2 == 0 {
			d.PushBack(i)
		} else {
			d.PushFront(i)
		}
	}
	
	// 设置最小容量防止频繁扩容
	d.SetMinCapacity(64)
	
	// 使用迭代器遍历
	fmt.Println("Queue contents (iterator):")
	for it := d.Iterator(); it.Next(); {
		fmt.Print(it.Value(), " ")
	}
	
	// 清空队列
	d.Clear()
	fmt.Println("\n\nAfter clear, length:", d.Len())
}

6. 与其他实现的比较

Golang中还有其他几个Deque实现：

  1. container/list：标准库的双向链表实现，但性能不如基于切片的实现
  2. ef-dn/go-deque：另一个高性能实现，API略有不同
  3. gammazero/deque：本文介绍的实现，性能优异且API友好

7. 使用场景

Deque特别适合以下场景：

  • 需要频繁在两端插入/删除元素的场景
  • 滑动窗口算法
  • 广度优先搜索(BFS)
  • 实现撤销/重做功能
  • 工作窃取(work-stealing)算法

8. 注意事项

  1. 空队列调用Pop/PopFront/PopBack会导致panic
  2. 对于基本数据类型，使用特化版本(如deque.Newint)可获得更好性能
  3. 频繁插入/删除时，设置合理的初始容量可提高性能

gammazero/deque是一个简单易用且高性能的双端队列实现，适合大多数Golang应用场景。

回到顶部