Structure des données : Ensemble - Golang

Bonjour à tous, comment allez-vous ? Aujourd'hui, je souhaite apporter du contenu lié à Go, qui consiste à créer une structure de données appelée Set. Passons à l'explication !

Après tout, qu’est-ce qu’un ensemble ?

Set est un ensemble de données linéaires qui contient une collection de valeurs non répétitives. Un ensemble peut stocker des valeurs uniques sans ordre particulier.

Après tout, existe-t-il Set in Go ?

La réponse est non. En Go, nous n'avons pas la structure de données Set ou HashSet comme en Java ou C# par exemple. Mais Hashicorp, une grande entreprise technologique propriétaire de Terraform, dispose d'une bibliothèque qui résout ce type de problème pour nous dans le monde Go. Je laisserai le lien du référentiel à la fin de l'article.

.

Quels problèmes Set résout-il ?

• Vérification des membres : définit Excel pour vérifier rapidement si un élément existe en leur sein. En effet, les ensembles utilisent souvent des techniques de hachage pour des recherches rapides, offrant une complexité temporelle moyenne de O(1) pour la vérification des membres.

• Trouver des éléments uniques : Compter ou trouver des éléments distincts dans une liste devient efficace avec des ensembles. Ajoutez simplement tous les éléments à un ensemble et celui-ci ne contiendra que des entrées uniques. Cela élimine le besoin de boucles de comparaison complexes.

• Opérations sur les ensembles : les ensembles offrent des fonctions intégrées pour les opérations telles que l'union (combinaison d'éléments de deux ensembles), l'intersection (recherche d'éléments communs à deux ensembles) et la différence (éléments dans un ensemble mais pas dans l'autre). . Ces opérations sont très utiles pour la manipulation et l'analyse des données.

• Voici quelques exemples spécifiques de problèmes pour lesquels les ensembles peuvent être une excellente option :

• Rechercher des éléments en double dans une liste : ajoutez tous les éléments à un ensemble. Si la taille définie est inférieure à la taille de la liste d'origine, il y a des doublons.
  Rechercher l'intersection de deux listes : utilisez l'opération d'intersection définie pour rechercher les éléments présents dans les deux listes.

• Identifier les éléments fréquents dans un ensemble de données : ajoutez des éléments à un ensemble et comptez leurs occurrences. L'ensemble élimine les doublons, vous permettant de vous concentrer sur des éléments uniques et leur fréquence.

• Vérifiez si une chaîne est un palindrome : convertissez la chaîne en un ensemble et vérifiez sa taille. Si la taille reste la même après suppression des doublons, c'est un palindrome (tous les caractères n'apparaissent qu'une seule fois).

D'accord, je vais expliquer le code avec une nouvelle approche, qui consiste à expliquer le flux dans le code à travers des commentaires.

import "fmt"

// Criamos nossa estrutura para definir um map
type Set struct {
    integerMap map[int]bool
}

// Criamos nosso "construtor" para inicializar o map
func (s *Set) newSet() {
    s.integerMap = make(map[int]bool)
}

// Aqui temos a função que vai verificar se o elemento é false, por padrão é sempre falso, e se o elemento retornar false é porque esse valor não existe no nosso map e então podemos adicioná-lo. Mas se essa função retornar true, no nosso addElement ele nem vai adicionar ao mapa.
func (s *Set) containsElement(el int) bool {
    var exists bool
    _, exists = s.integerMap[el]
    return exists
}

// Responsável pela adição do elemento no mapa.
// Aqui, esse if verifica se o elemento contido é falso; se for falso, ele não tem uma duplicata e então pode ser adicionado à lista.
// Agora, se o resultado de contains for true, ele nem vai cair dentro desse if e por tanto não vai adicionar a lista.
func (s *Set) addElement(el int) {
    if !s.containsElement(el) {
        s.integerMap[el] = true
    }
}

// Aqui um delete simples
func (s *Set) deleteEl(el int) {
    delete(s.integerMap, el)
}

// Aqui damos um findAll que lista todos os elementos, sendo seu Big O O(n)
func (s *Set) allElements() {
    for k := range s.integerMap {
        fmt.Println(k)
    }
}

// Aqui temos a função que tem o length, que vai ser o tamanho do nosso integerMap, e a variável c, que pode ser chamada de collection, pois vai ser nossa coleção das chaves do nosso map, ou seja, uma lista.
// Dentro do nosso for, fazemos esse loop para descobrir se c[x] é maior do que c[n + 1], ou seja, a próxima posição na nossa lista.
// Criamos o initialValue que vai ser o valor em relação à posição da lista.
// Depois, atribuimos a c[x] o próximo valor da iteração, ou seja, c[x+1].
// E por fim, atribuimos o valor de c[x+1] = initialValue.
// Assim, fazemos com que os maiores valores da lista sejam trocados, jogando os maiores para o final da lista. O maior número SEMPRE tem que estar no fim da lista.
// Em outros termos, estamos fazendo uma ordenação por bolha ou bubblesort.
// Seu Big O é de O(n) no melhor caso e no pior caso é O(n^2).
// Mas sua complexidade espacial é muito boa, sendo O(1).
func (s *Set) maximumElements() {
    length := len(s.integerMap)

    c := s.allElements()

    for n := 0; x < length-1; x++ {
        if c[x] > c[x+1] {
            initialValue := c[x]
            c[x] = c[x+1]
            c[x+1] = initialValue
        }
    }
    maximumValue := c[length-1]
    fmt.Printf("MaximumValue: %d\n", maximumValue)
}

// Com a explicação do maximumElements, aqui é a mesma coisa,só que o menor número também tem que estar no final da lista.
func (s *Set) minumumElements() {

    c := s.allElements()
    length := len(s.integerMap)

    for x := 0; x < length-1; x++ {
        if c[x] < c[x+1] {
            initialValue := c[x]
            c[x] = c[x+1]
            c[x+1] = initialValue
        }
    }

    m := c[length-1]
    fmt.Printf("Minimum value %d\n", m)
}

// aqui temos nosso sizeOfSet que basicamente vai printar na tela o tamanho do nossa lista
func (s *Set) sizeOfSet() {
    fmt.Printf("Length of List: %v\n", len(s.allElements()))
}

func printValues(values []int) {

    fmt.Printf("List of Values: %v\n", values)
}

func main() {
    set := &Set{}
    set.newSet()
    set.addElement(3)
    set.addElement(6)
    set.addElement(8)
    set.addElement(9)
    set.addElement(10)
    set.addElement(14)
    set.addElement(3)
    set.addElement(2)
    set.addElement(14)

    values := set.allElements()
    printValues(values)

    set.maximumElements()
    set.minumumElements()

    fmt.Printf("Contains Value: %v\n", set.containsElement(1))

    set.sizeOfSet()

    set.deleteElements(14)
    set.deleteElements(2)
    fmt.Println("--------------------------------")
    valuesAfterDelete := set.allElements()
    set.maximumElements()
    set.minumumElements()
    printValues(valuesAfterDelete)
}

• Réponse de la console

List of Values: [8 9 10 14 2 3 6]
MaximumValue: 14
Minimum value: 2
Contains Value: false
Length of List: 7
--------------------------------
MaximumValue: 10
Minimum value: 3
List of Values: [9 10 3 6 8]

J'ai l'intention d'apporter une deuxième partie parlant d'Intersect et d'Union, qui est un sujet très intéressant.

C'est tout pour aujourd'hui les gars, j'espère que vous avez compris un peu plus comment utiliser Sets in Go ou que vous avez également compris ce sujet. J'ai l'intention de faire une partie 2 sur ce sujet. Bonne nuit et à la prochaine fois !

• Lien du référentiel Hashicorp : https://github.com/hashicorp/go-set
• Site Internet pour mieux comprendre BigO : https://www.bigochheatsheet.com/
• Je crée une CLI qui sert d'outil pour accélérer votre productivité dans Go, jetez un œil : https://github.com/YlanzinhoY/tooling_golang

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!