Utiliser des ensembles avec Golang Generics | de Noah Schumacher | novembre 2022

Créez votre propre type d’ensemble entièrement fonctionnel dans Go

L’une des choses les plus frustrantes que j’ai trouvées lors de mon premier apprentissage de Go (venant principalement de Python) était le manque de types de collections tels que Sets et leurs opérations courantes. Dans cet article, nous montrerons comment l’introduction des génériques dans Go 1.18 peut nous permettre de créer notre propre type Set entièrement fonctionnel. Tous les codes ci-dessous peuvent également être trouvés sur mon Go-collections GitHub.

Vous connaissez peut-être le type de collecte de données incroyablement utile qu’est un ensemble. Un ensemble est une collection non ordonnée d’éléments uniques. En règle générale, les ensembles sont implémentés à l’aide de Hashmaps qui effectuent des recherches de valeurs O (1) (en supposant qu’il n’y a pas de collisions de hachage). Les ensembles ont 4 opérations principales qui les rendent particulièrement utiles :

1. Syndicat (UN ⋃ B) — est l’Ensemble qui contient tous les éléments des Ensembles A et B.
2. Carrefour (UN ∩ B)— est l’Ensemble qui contient tous les éléments qui sont dans l’Ensemble A et B.
3. Complément (UNc) — est l’Ensemble des éléments qui sont dans l’ensemble universel S mais qui ne sont pas dans A. Nous ignorerons le complément puisqu’il est géré par Différence.
4. Différence (UN − B) — est l’Ensemble des éléments qui sont dans UN mais ne sont pas dans B.

Commençons par définir notre type Set dans Go. Tout d’abord, nous voulons définir ce qu’est un ensemble et avec les génériques, nous pouvons utiliser des contraintes pour étendre facilement le type d’ensemble afin de gérer de nombreux types de données.

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

Dans cette première section, nous avons créé notre type Set qui utilise le type de carte intégré. Nous restreignons la clé de la carte pour qu’elle soit de type Comparable. D’après la documentation, nous savons que les types comparables incluent

(booléens, nombres, chaînes, pointeurs, canaux, tableaux de types comparables, structures dont les champs sont tous de types comparables)

Nous ajoutons également quelques méthodes de base sur notre type pour ajouter, supprimer et vérifier l’existence. Avec cela, nous ne sommes pas prêts à commencer à implémenter nos opérations Set définies ci-dessus. Commençons avec 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
}

Exemple assez simple. Nous créons simplement un nouvel ensemble avec une capacité de 0 (car nous ne savons pas quelle sera la taille du nouvel ensemble), puis nous parcourrons Set A ajouter uniquement des éléments qui ne sont pas contenus dans B.

Les deux prochaines opérations Union et Intersection suivre un schéma similaire – mais cette fois, nous ajoutons une légère (ou potentiellement importante) optimisation.

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

Ces deux méthodes sont assez simples. Dans le Union nous parcourons simplement un ensemble en ajoutant les valeurs à l’autre ensemble. Dans le Intersection nous vérifions si les valeurs dans A sont aussi dans B et renvoyer un ensemble qui ne contient que les éléments des deux.

L’optimisation vient de distinguer quel ensemble est le plus petit dans le smallLarge(a, b) appel. Ce faisant, nous permettons aux boucles de parcourir uniquement le plus petit des deux ensembles. Cela pourrait potentiellement économiser beaucoup d’itérations si un ensemble est très grand et l’autre petit.

Cependant, dans le syndicat nous écrasons le grand ensemble qui pourrait être soit UN ou B. Si nous voulons conserver les ensembles d’origine lors de l’union, nous devrions boucler sur les deux ensembles.

Nous avons maintenant un package Set entièrement fonctionnel. Avec un peu plus de travail, nous pouvons ajouter des aides pour les tranches et ajouter plus de méthodes utilitaires telles que la vérification de l’égalité.

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

Avec tout le travail ci-dessus, nous sommes en mesure d’effectuer des actions comme celles présentées ci-dessous :

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
}