Data Structure: Set - Golang

Hello everyone, how are you? Today I want to bring content related to Go, which consists of creating a data structure called Set. Let's get to the explanation!

After all, what is a Set?

Set is a linear data set that has a collection of non-repeating values. A Set can store unique values ​​in no particular order.

After all, is there Set in Go?

The answer is no. In Go, we do not have the Set or HashSet data structure like in Java or C#, for example. But Hashicorp, a large technology company that owns Terraform, has a library that solves this type of problem for us in the Go world. I'll leave the repository link at the end of the article.

What problems does Set solve?

• Membership check: Sets excel at quickly checking whether an element exists within them. This is because sets often use hashing techniques for fast lookups, offering an average time complexity of O(1) for membership checking.

• Finding unique elements: Counting or finding distinct elements in a list becomes efficient with sets. Simply add all the elements to a set, and it will only contain unique entries. This eliminates the need for complex comparison loops.

• Set Operations: Sets offer built-in functions for operations such as union (combining elements from two sets), intersection (finding elements common to two sets), and difference (elements in one set but not the other). These operations are very useful for data manipulation and analysis.

• Here are some specific examples of problems where sets can be a great option:

• Find duplicate elements in a list: Add all elements to a set. If the set size is smaller than the original list size, there are duplicates.
  Find the intersection of two lists: Use the set intersection operation to find elements present in both lists.

• Identifying frequent elements in a dataset: Add elements to a set and count their occurrences. The set eliminates duplicates, allowing you to focus on unique elements and their frequency.

• Check if a string is a palindrome: Convert the string to a set and check its size. If the size remains the same after removing duplicates, it is a palindrome (all characters appear only once).

Okay, I'm going to explain the code with a new approach, which is to explain the flow within the code through comments.

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

• Console response

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]

I intend to bring a second part talking about Intersect and Union, which is a very interesting subject.

That's it for today guys, I hope you understood a little more about how to use Sets in Go or that you also understood this topic. I intend to do a Part 2 on this subject. Good night and see you next time!

• Hashicorp Repository Link: https://github.com/hashicorp/go-set
• Website to better understand BigO: https://www.bigochheatsheet.com/
• I'm creating a CLI that serves as a tool to speed up your productivity in Go, take a look: https://github.com/YlanzinhoY/tooling_golang

The above is the detailed content of Data Structure: Set - Golang. For more information, please follow other related articles on the PHP Chinese website!