百木园-与人分享,
就是让自己快乐。

Golang实现set

背景

Golang语言本身未实现set,但是实现了map

golang的map是一种无序的键值对的集合,其中键是唯一的

而set是键的不重复的集合,因此可以用map来实现set

Empty

由于map是key-value集合,如果使用map来实现set,则不需要关注value的具体类型和值

struct{}是具有零个元素的struct,struct{}的大小为0,不占用空间,因此十分适合作为value使用

type Empty struct{}

Int64HashSet

Golang是静态强类型语言,对于int8、uint8、int64、uint64、 string基础数据类型的set,均需要实现类似的代码

定义

type Int8HashSet map[int8]Empty
type UintHashSet map[uint8]Empty 
type Int64HashSet map[int64]Empty 
type Uint64HashSet map[uint64]Empty 
type Int64HashSet map[string]Empty  

以int64为例,实现set的基本操作

初始化

func NewInt64HashSet(cap ...int) Int64HashSet {
	var set Int64HashSet
	if len(cap) == 0 {
		set = make(Int64HashSet)
	} else {
		set = make(Int64HashSet, cap[0])
	}
	return set
}

插入

func (set Int64HashSet) Insert(items ...int64) {
	for _, item := range items {
		set[item] = Empty{}
	}
}

删除

func (set Int64HashSet) Delete(items ...int64) {
	for _, item := range items {
		delete(set, item)
	}
}

列表

func (set Int64HashSet) List() []int64 {
	list := make([]int64, 0, len(set))
	for item := range set {
		list = append(list, item)
	}
	return list
}

弊端

采用上面的方法实现,会充斥着大量重复代码,对于其它类型如int8,uint8,string等类型,需要单独实现,尽管逻辑基本一致。

在Go 1.18版本之前,我们可以使用反射来避免这个问题,

使用反射在运行时推断具体的类型,虽然有性能上的损耗,但是单次纳秒级别的操作,基本可以忽略不计。

HashSet

interface{}是没有方法的空接口,所有类型都实现了空接口

通过反射可以从interface获取对象的值和类型

定义

type HashSet map[interface{}]Empty

初始化

func NewHashSet(cap ...int) HashSet {
	var set HashSet
	if len(cap) == 0 {
		set = make(HashSet)
	} else {
		set = make(HashSet, cap[0])
	}
	return set
}

插入

func (set HashSet) Insert(items ...interface{}) {
	for _, item := range items {
		set[item] = Empty{}
	}
}

删除

func (set HashSet) Delete(items ...interface{}) {
	for _, item := range items {
		delete(set, item)
	}
}

列表

// 通过反射获取到具体的类型
// 可以将int64替换为其它类型,如uint8, string等
func (set HashSet) ListInt64() []int64 {
	list := make([]int64, 0, len(set))
	for item := range set {
		if val, ok := item.(int64); ok {
			list = append(list, val)
		}
	}
	return list
}

func (set HashSet) ListString() []string {
	list := make([]string, 0, len(set))
	for item := range set {
		if val, ok := item.(string); ok {
			list = append(list, val)
		}
	}
	return list
}

GenericHashSet

反射在编译时缺少类型检查,比如对于同一个set,先后插入int类型和string类型数据,在编译和运行阶段均不会报错。

hash := NewHashSet(8)
// 插入int类型
hash.Insert(111)
// 插入string类型
hash.Insert(\"string\")

使用反射在一定程度上避免了大量的重复代码,但是将set转换为slice还是会存在重复的相似逻辑的代码

并且需要在运行时获取/判断对象的类型和值,存在一定的性能损耗

在Go 1.18版本提供了范型(Generics)的支持,

范型可以在编译期间进行类型检查和类型推断,相对于反射机制而言,性能有所提升

定义

type GenericHashSet[T comparable] map[T]Empty

初始化

func NewGenericHashSet[T comparable](cap ...int) *GenericHashSet[T] {
	var set GenericHashSet[T]
	if len(cap) == 0 {
		set = make(GenericHashSet[T])
	} else {
		set = make(GenericHashSet[T], cap[0])
	}
	return &set
}

插入

func (set *GenericHashSet[T]) Insert(items ...T) {
	for _, item := range items {
		(*set)[item] = Empty{}
	}
}

删除

func (set *GenericHashSet[T]) Delete(items ...T) {
	for _, item := range items {
		delete(*set, item)
	}
}

列表

func (set *GenericHashSet[T]) List() []T {
	list := make([]T, 0, len(*set))
	for item := range *set {
		list = append(list, item)
	}
	return list
}

性能对比

插入操作测试代码

func BenchmarkInt64HashSetInsert(b *testing.B) {
	intHashSet := NewInt64HashSet()
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < b.N; i++ {
		intHashSet.Insert(rand.Int63())
	}
}

func BenchmarkGenericHashSetInsert(b *testing.B) {
	gHashSet := NewGenericHashSet[int64]()
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < b.N; i++ {
		gHashSet.Insert(rand.Int63())
	}
}

func BenchmarkHashSetInsert(b *testing.B) {
	hashSet := NewHashSet()
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < b.N; i++ {
		hashSet.Insert(rand.Int63())
	}
}

 插入操作测试结果

zbwdeAir:set zbw$ go test -bench=\"BenchmarkInt64HashSetInsert|BenchmarkGenericHashSetInsert|BenchmarkHashSetInsert\" -benchmem
goos: darwin
goarch: arm64
pkg: set/set
BenchmarkInt64HashSetInsert-8           10051916               119.2 ns/op            40 B/op          0 allocs/op
BenchmarkGenericHashSetInsert-8         13957741               123.7 ns/op            57 B/op          0 allocs/op
BenchmarkHashSetInsert-8                 6526810               188.9 ns/op            63 B/op          1 allocs/op
PASS
ok      set/set 4.897s

可以看出来,Int64HashSet性能最优,GenericHashSet次之,HashSet性能最差。

从实际使用角度看

对于Go < 1.18版本,使用HashSet即可。如果追求性能的极致,不介意大量重复代码,那还是使用Int64HashSet

对于单次操作的时间在ns级别,对于大部分业务场景,反射带来的性能损耗基本可以忽略,性能的瓶颈并不在这里。

对于Go >= 1.18版本,可以使用GenericHashSet

其它

如果需要实现有序set,则需要链表辅助实现

详细代码,见github

如果你觉得还可以,点一下Star🌟

 


来源:https://www.cnblogs.com/amos01/p/16586250.html
本站部分图文来源于网络,如有侵权请联系删除。

未经允许不得转载:百木园 » Golang实现set

相关推荐

  • 暂无文章