在 Go 中构建您自己的全功能 Set 类型
image.png
很多人学习 Go 时发现的一件更令人沮丧的事情是缺少集合类型，例如 Sets 及其常用操作。在本文中，我们将展示 Go 1.19 中泛型的引入如何让我们能够构建自己的功能齐全的 Set 类型。
您可能熟悉非常有用的数据收集类型 Set。Set 是唯一项的无序集合。通常集合是使用 Hashmap 实现的，Hashmap 查找值的时间复杂度为 O(1)（假设没有哈希冲突）。集合有 4 个主要操作，使它们特别有用：
- Union ( A ⋃ B ) — 并集是包含集合 A 和 B 中所有元素的集合。
- Intersection ( A ∩ B ) — 交集是包含集合 A 和 B 中相交元素的集合。
- Complement ( A c) — 补集是通用集合 S 中但不在 A 中的元素集合。我们将忽略补集，因为它由 Difference 处理。
- Difference ( A − B ) — 差集是 A 中但不在 B 中的元素的集合。
让我们开始在 Go 中定义我们的 Set 类型。首先，我们要定义 Set 是什么，使用泛型我们可以利用约束轻松扩展 Set 类型以处理大量数据类型。
package collections
// A collection of unique comparable items. Uses a map with only true values
// to accomplish set functionality.
type Set[T comparable] map[T]bool
// Create a new empty set with the specified initial size.
func NewSet[T comparable](size int) Set[T] {
return make(Set[T], size)
}
// Add a new key to the set
func (s Set[T]) Add(key T) {
s[key] = true
}
// Remove a key from the set. If the key is not in the set then noop
func (s Set[T]) Remove(key T) {
delete(s, key)
}
// Check if Set s contains key
func (s Set[T]) Contains(key T) bool {
return s[key]
}
在第一部分中，我们创建了使用内置地图类型的 Set 类型。我们将映射的键限制为 Comparable 类型。从文档中，我们知道 Comparable 类型包括
（布尔值、数字、字符串、指针、通道、可比较类型的数组、字段都是可比较类型的结构）
我们还在我们的类型上添加了一些基本方法，用于添加、删除和检查是否存在。有了这个，我们还没有准备好开始实施上面定义的 Set 操作。让我们从 Difference 开始。
// A difference B | NOTE: A-B != B-A
func (a Set[T]) Difference(b Set[T]) Set[T] {
resultSet := NewSet[T](0)
for key := range a {
if !b.Contains(key) {
resultSet.Add(key)
}
}
return resultSet
}
相当简单的例子。我们简单地创建一个容量为 0 的新 Set（因为我们不知道新 Set 有多大），然后迭代 Set A 只添加不包含在 B。
接下来的两个操作 Union 和 Intersection 遵循类似的模式 — 但这次我们添加了一个轻微的优化。
// A union B
func (a Set[T]) Union(b Set[T]) Set[T] {
small, large := smallLarge(a, b)
for key := range small {
large.Add(key)
}
return large
}
// A intersect B
func (a Set[T]) Intersection(b Set[T]) Set[T] {
small, large := smallLarge(a, b)
resultSet := NewSet[T](0)
for key := range small {
if large.Contains(key) {
resultSet.Add(key)
}
}
return resultSet
}
// returns the small and large sets according to their len
func smallLarge[T comparable](a, b Set[T]) (Set[T], Set[T]) {
small, large := b, a
if len(b) > len(a) {
small, large = a, b
}
return small, large
}
这两种方法都相当简单。在中，Union 我们只是迭代一个集合，将值添加到另一个集合。在中，Intersection 我们正在检查中的值 A 是否也在中，B 并返回一个仅包含两者中的元素的集合。
优化来自区分哪个集合是 smallLarge(a, b) 调用中较小的集合。通过这样做，我们允许循环只迭代两个集合中较小的一个。如果一个 Set 很大而另一个很小，这可能会节省很多迭代。
但是，在 Union 中，我们正在覆盖可能是 A 或 B 的大集合。如果我们想在合并时保留原始集合，我们将不得不循环遍历两个集合。
我们现在有一个功能齐全的 Set 包。通过更多的工作，我们可以为切片添加帮助器并添加更多实用方法，例如检查是否相等。
// A == B (all elements of A are in B and vice versa)
func (a Set[T]) Equals(b Set[T]) bool {
return len(a.Difference(b)) == 0 && len(b.Difference(a)) == 0
}
// Create a Set from a slice.
func SliceToSet[T comparable](s []T) Set[T] {
set := NewSet[T](len(s))
for _, item := range s {
set.Add(item)
}
return set
}
// Union two slices. The provided slices do not need to be unique. Order not guaranteed.
func SliceUnion[T comparable](a, b []T) []T {
aSet, bSet := SliceToSet(a), SliceToSet(b)
union := aSet.Union(bSet)
return union.ToSlice()
}
// Intersection of two slices. The provided slices do not need to be unique. Order not guaranteed.
func SliceIntersection[T comparable](a, b []T) []T {
aSet, bSet := SliceToSet(a), SliceToSet(b)
intersection := aSet.Intersection(bSet)
return intersection.ToSlice()
}
通过以上所有工作，我们能够执行如下所示的操作：
func TestSets(t *testing.T) {
A := SliceToSet([]int{1, 3, 5})
B := SliceToSet([]int{0, 1, 2, 3, 4})
union := A.Union(B)
fmt.Println(union) // map[0:true 1:true 2:true 3:true 4:true 5:true]
C := SliceToSet([]string{"a", "b", "noah"})
D := SliceToSet([]string{"a", "noah"})
intersection := C.Intersection(D)
fmt.Println(intersection) // map[a:true noah:true]
fmt.Println(C.Equals(D)) // false
}
我希望你发现这篇文章有帮助！同样，所有代码都可以在 GitHub 上找到。
欢迎点赞，关注，转发，Happy Coding。
网友评论