Olá Pessoal, tudo bem? Hoje quero trazer um conteúdo relacionado a Go, que consiste em criar uma estrutura de dados chamada Set. Vamos para a explicação!
Afinal, o que é um Set?
Set é um conjunto de dados linear que possui uma coleção de valores que não se repetem. Um Set pode armazenar valores exclusivos sem qualquer ordem específica.
Afinal, existe Set em Go?
A resposta é não. Em Go, não temos a estrutura de dados Set ou HashSet igual em Java ou C#, por exemplo. Mas a Hashicorp, uma grande empresa de tecnologia dona do Terraform, tem uma biblioteca que resolve esse tipo de problema para nós no mundo Go. Vou deixar o link do repositório no final do artigo.
Quais problemas Set resolve?
Verificação de pertinência: Conjuntos se sobressaem em verificar rapidamente se um elemento existe dentro deles. Isso ocorre porque os conjuntos geralmente usam técnicas de hash para pesquisas rápidas, oferecendo uma complexidade de tempo média de O(1) para verificação de pertinência.
Encontrando elementos únicos: Contar ou encontrar elementos distintos em uma lista se torna eficiente com conjuntos. Simplesmente adicione todos os elementos a um conjunto, e ele só conterá entradas exclusivas. Isso elimina a necessidade de loops de comparação complexos.
Operações de conjuntos: Conjuntos oferecem funções integradas para operações como união (combinar elementos de dois conjuntos), interseção (encontrar elementos comuns a dois conjuntos) e diferença (elementos em um conjunto, mas não no outro). Essas operações são muito úteis para manipulação e análise de dados.
Aqui estão alguns exemplos específicos de problemas onde os conjuntos podem ser uma ótima opção:
Encontrar elementos duplicados em uma lista: Adicione todos os elementos a um conjunto. Se o tamanho do conjunto for menor que o tamanho da lista original, há duplicados.
Encontrar a interseção de duas listas: Use a operação de interseção de conjuntos para encontrar elementos presentes em ambas as listas.Identificando elementos frequentes em um conjunto de dados: Adicione elementos a um conjunto e conte suas ocorrências. O conjunto elimina duplicados, permitindo que você se concentre em elementos únicos e sua frequência.
Verificar se uma string é um palíndromo: Converta a string em um conjunto e verifique seu tamanho. Se o tamanho permanecer igual após remover duplicados, é um palíndromo (todos os caracteres aparecem apenas uma vez).
Certo, a explicação do código eu vou com uma abordagem nova que é explicar o fluxo dentro do código através dos comentários.
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)
}
- Resposta do 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]
Pretendo trazer uma segunda parte falando sobre Intersect e Union, que é um assunto bastante interessante.
Por hoje é isso pessoal, espero que vocês tenham compreendido um pouco mais como utilizar os Sets em Go ou que também tenham entendido esse tema. Pretendo fazer uma Parte 2 sobre esse assunto. Boa noite e até a próxima!
- Link do Repositório da Hashicorp: https://github.com/hashicorp/go-set
- Site para entender melhor sobre BigO: https://www.bigocheatsheet.com/
- Estou criando uma CLI que serve como uma ferramenta para acelerar sua produtividade em Go, dê uma olhada: https://github.com/YlanzinhoY/Sollievo
Top comments (1)
Parabens mano, muito boa a explicacao, nao fazia ideia o que era isso!!!