Datenstruktur: Set – Golang

Hallo zusammen, wie geht es euch? Heute möchte ich Inhalte im Zusammenhang mit Go vorstellen, die darin bestehen, eine Datenstruktur namens Set zu erstellen. Kommen wir zur Erklärung!

Was ist schließlich ein Set?

Set ist ein linearer Datensatz, der eine Sammlung sich nicht wiederholender Werte enthält. Ein Set kann eindeutige Werte in keiner bestimmten Reihenfolge speichern.

Gibt es schließlich Set in Go?

Die Antwort ist nein. In Go gibt es keine Set- oder HashSet-Datenstruktur wie beispielsweise in Java oder C#. Aber Hashicorp, ein großes Technologieunternehmen, dem Terraform gehört, verfügt über eine Bibliothek, die diese Art von Problemen für uns in der Go-Welt löst. Ich lasse den Repository-Link am Ende des Artikels.

Welche Probleme löst Set?

• Mitgliedschaftsprüfung: Legt Excel fest, um schnell zu prüfen, ob ein Element darin vorhanden ist. Dies liegt daran, dass Sätze häufig Hashing-Techniken für schnelle Suchvorgänge verwenden und eine durchschnittliche Zeitkomplexität von O(1) für die Überprüfung der Mitgliedschaft bieten.

• Eindeutige Elemente finden: Das Zählen oder Finden unterschiedlicher Elemente in einer Liste wird mit Mengen effizienter. Fügen Sie einfach alle Elemente zu einem Satz hinzu, und dieser enthält nur eindeutige Einträge. Dadurch entfallen komplexe Vergleichsschleifen.

• Mengenoperationen: Mengen bieten integrierte Funktionen für Operationen wie Vereinigung (Elemente aus zwei Mengen kombinieren), Schnittmenge (Elemente finden, die zwei Mengen gemeinsam sind) und Differenz (Elemente in einer Menge, aber nicht in der anderen). . Diese Operationen sind sehr nützlich für die Datenbearbeitung und -analyse.

• Hier sind einige konkrete Beispiele für Probleme, bei denen Sets eine gute Option sein können:

• Duplikate Elemente in einer Liste finden: Alle Elemente zu einem Satz hinzufügen. Wenn die eingestellte Größe kleiner als die ursprüngliche Listengröße ist, gibt es Duplikate.
  Finden Sie den Schnittpunkt zweier Listen: Verwenden Sie die Operation „Schnittpunkt festlegen“, um Elemente zu finden, die in beiden Listen vorhanden sind.

• Identifizieren häufiger Elemente in einem Datensatz: Fügen Sie Elemente zu einem Satz hinzu und zählen Sie deren Vorkommen. Das Set eliminiert Duplikate, sodass Sie sich auf einzigartige Elemente und deren Häufigkeit konzentrieren können.

• Überprüfen Sie, ob eine Zeichenfolge ein Palindrom ist: Konvertieren Sie die Zeichenfolge in eine Menge und überprüfen Sie ihre Größe. Bleibt die Größe nach dem Entfernen von Duplikaten gleich, handelt es sich um ein Palindrom (alle Zeichen kommen nur einmal vor).

Okay, ich werde den Code mit einem neuen Ansatz erklären, der darin besteht, den Fluss innerhalb des Codes durch Kommentare zu erklären.

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

• Konsolenantwort

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]

Ich beabsichtige, einen zweiten Teil über Intersect und Union zu bringen, was ein sehr interessantes Thema ist.

Das war's für heute, Leute. Ich hoffe, ihr habt etwas mehr über die Verwendung von Sets in Go verstanden oder auch dieses Thema verstanden. Ich habe vor, einen zweiten Teil zu diesem Thema zu schreiben. Gute Nacht und bis zum nächsten Mal!

• Hashicorp-Repository-Link: https://github.com/hashicorp/go-set
• Website zum besseren Verständnis von BigO: https://www.bigochheatsheet.com/
• Ich erstelle eine CLI, die als Tool zur Beschleunigung Ihrer Produktivität in Go dient. Schauen Sie sich das an: https://github.com/YlanzinhoY/tooling_golang

Das obige ist der detaillierte Inhalt vonDatenstruktur: Set – Golang. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!