資料結構：集合 - Golang

大家好，你們好嗎？今天我想帶來Go相關的內容，其中包括建立一個名為Set的資料結構。

畢竟，什麼是 Set？

集合是一個線性資料集，具有非重複值的集合。 Set 可以以無特定順序儲存唯一值。

畢竟，Go 中有 Set 嗎？

答案是否定的。例如，在 Go 中，我們沒有像 Java 或 C# 中的 Set 或 HashSet 資料結構。但是擁有 Terraform 的大型科技公司 Hashicorp 有一個庫可以在 Go 世界中為我們解決此類問題。我將在文章末尾留下存儲庫連結。

Set解決了什麼問題？

• 成員資格檢查：設定擅長快速檢查其中是否存在元素。這是因為集合經常使用哈希技術進行快速查找，為成員資格檢查提供 O(1) 的平均時間複雜度。

• 尋找唯一元素：使用集合來計算或尋找清單中的不同元素變得有效率。只需將所有元素新增到一個集合中，它就只包含唯一的條目。這消除了對複雜比較循環的需求。

• 集合運算：集合提供內建運算函數，例如並集（組合兩個集合中的元素）、交集（找出兩個集合中共有的元素）和差值（一個集合中的元素，但不是另一個集合中的元素） 。這些操作對於資料操作和分析非常有用。

• 以下是一些具體的問題範例，其中集合可能是一個不錯的選擇：

• 尋找清單中的重複元素：將所有元素加入集合。如果集合大小小於原始清單大小，則存在重複。
  尋找兩個清單的交集：使用集合交集運算來尋找兩個清單中都存在的元素。

• 辨識資料集中的頻繁元素：將元素加入集合中並計算它們的出現次數。此集合消除了重複項，讓您專注於獨特的元素及其頻率。

• 檢查字串是否為回文：將字串轉換為集合並檢查其大小。如果去重後大小不變，則為回文（所有字元只出現一次）。

好吧，我將用一種新的方式來解釋程式碼，即透過註解來解釋程式碼內部的流程。

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

• 控制台響應

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]

我打算用第二部分來討論相交和並集，這是一個非常有趣的主題。

今天就這樣了，希望你們對如何在 Go 中使用 Set 有了更多的了解，或者也了解了這個主題。我打算寫一個關於這個主題的第二部分。晚安，我們下次再見！

• Hashicorp 儲存庫連結：https://github.com/hashicorp/go-set
• 更了解BigO的網站：https://www.bigochheatsheet.com/
• 我正在創建一個 CLI，作為提高 Go 生產力的工具，請查看：https://github.com/YlanzinhoY/tooling_golang

以上是資料結構：集合 - Golang的詳細內容。更多資訊請關注PHP中文網其他相關文章！