Utilizing Sets With Golang Generics | by Noah Schumacher | Nov, 2022 - Exotic Digital Access
  • Kangundo Road, Nairobi, Kenya
  • support@exoticdigitalaccess.co.ke
  • Opening Time : 07 AM - 10 PM
Utilizing Sets With Golang Generics | by Noah Schumacher | Nov, 2022

Utilizing Sets With Golang Generics | by Noah Schumacher | Nov, 2022

Build your own fully-functional Set type in Go

Utilizing Sets With Golang Generics | by Noah Schumacher | Nov, 2022

One of the more frustrating things I found when first learning Go (coming from mostly Python) was the lack of collection types such as Sets and their common operations. In this article, we will show how the introduction of Generics in Go 1.18 can allow us to build our own fully functioning Set type. All code below can also be found at my GitHub go-collections.

You might be familiar with the incredibly useful data collection type that is a Set. A Set is an unordered collection of unique items. Typically sets are implemented using Hashmaps that make look-ups of values O(1) (assuming no hash collisions). Sets have 4 main operations that make them particularly useful:

  1. Union (A B) — is the Set that contains all the elements in Set A and B.
  2. Intersection (A B)— is the Set that contains all the elements that are in Set A and B.
  3. Complement (Ac) — is the Set of elements that are in the universal set S but are not in A. We will ignore complement since it is handled by Difference.
  4. Difference (A B) is the Set of the elements that are in A but are not in B.

Let’s get started with defining our Set type in Go. First, we want to define what a Set is and with Generics we can utilize constraints to easily extend the Set type to handle lots of data types.

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]
}

In this first section, we created our Set type which utilizes the built-in map type. We restrict the key of the map to be of type Comparable. From the documentation, we know Comparable types include

(booleans, numbers, strings, pointers, channels, arrays of comparable types, structs whose fields are all comparable types)

We also add some basic methods on our type for adding, removing, and checking for existence. With this, we are not ready to start implementing our Set operations defined above. Let’s start with 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
}

Fairly simple example. We simply create a new Set with 0 capacity (because we do not know how large the new Set will be) and then iterate over Set A only adding elements that are not contained in B.

The next two operations Union and Intersection follow a similar pattern — but this time we add a slight (or potentially large) optimization.

// 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
}

Both of these methods are fairly simple. In the Union we are just iterating over one Set adding the values to the other set. In the Intersection we are checking if the values in A are also in B and returning a set that only contains the elements in both.

The optimization comes from distinguishing which set is the smaller one in the smallLarge(a, b) call. By doing so we allow the loops to only iterate over the smaller of the two sets. This could potentially save a lot of iterations if one Set is very large and the other small.

However, in the Union we are overwriting the large set which could be either A or B. If we want to preserve the original Sets when unioning we would have to loop over both Sets.

We now have a fully functioning Set package. With a little more work we can add helpers for slices and add more utility methods such as one checking for equality.

// 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()
}

With all the work above we are able to perform actions like those shown below:

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
}


Source link

Leave a Reply