Struktur Data: Set - Golang

Salam semua, apa khabar? Hari ini saya ingin membawa kandungan yang berkaitan dengan Go, yang terdiri daripada mencipta struktur data yang dipanggil Set. Mari kita ke penjelasan!

Lagipun, apa itu Set?

Set ialah set data linear yang mempunyai koleksi nilai tidak berulang. Satu Set boleh menyimpan nilai unik tanpa susunan tertentu.

Lagipun, adakah Set in Go?

Jawapannya tidak. Dalam Go, kami tidak mempunyai struktur data Set atau HashSet seperti dalam Java atau C#, sebagai contoh. Tetapi Hashicorp, sebuah syarikat teknologi besar yang memiliki Terraform, mempunyai perpustakaan yang menyelesaikan masalah jenis ini untuk kami di dunia Go. Saya akan meninggalkan pautan repositori di penghujung artikel.

Apakah masalah yang Set selesaikan?

• Semakan keahlian: Menetapkan kecemerlangan dalam menyemak dengan cepat sama ada unsur wujud di dalamnya. Ini kerana set sering menggunakan teknik pencincangan untuk carian pantas, menawarkan purata kerumitan masa O(1) untuk semakan keahlian.

• Mencari elemen unik: Mengira atau mencari elemen berbeza dalam senarai menjadi cekap dengan set. Hanya tambahkan semua elemen pada set, dan ia hanya akan mengandungi entri unik. Ini menghapuskan keperluan untuk gelung perbandingan yang kompleks.

• Operasi Set: Set menawarkan fungsi terbina dalam untuk operasi seperti kesatuan (menggabungkan elemen daripada dua set), persilangan (mencari elemen sepunya kepada dua set) dan perbezaan (elemen dalam satu set tetapi bukan set yang lain) . Operasi ini sangat berguna untuk manipulasi dan analisis data.

• Berikut ialah beberapa contoh khusus masalah di mana set boleh menjadi pilihan yang bagus:

• Cari elemen pendua dalam senarai: Tambahkan semua elemen pada set. Jika saiz set lebih kecil daripada saiz senarai asal, terdapat pendua.
  Cari persilangan dua senarai: Gunakan operasi persimpangan yang ditetapkan untuk mencari elemen yang terdapat dalam kedua-dua senarai.

• Mengenal pasti unsur yang kerap dalam set data: Tambahkan elemen pada set dan kira kejadiannya. Set ini menghapuskan pendua, membolehkan anda menumpukan pada elemen unik dan kekerapannya.

• Semak sama ada rentetan ialah palindrom: Tukar rentetan itu kepada set dan semak saiznya. Jika saiz kekal sama selepas mengalih keluar pendua, ia adalah palindrom (semua aksara muncul sekali sahaja).

Okay, saya akan menerangkan kod dengan pendekatan baharu, iaitu menerangkan aliran dalam kod melalui komen.

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

• Respons konsol

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]

Saya bercadang untuk membawa bahagian kedua bercakap mengenai Intersect dan Union, yang merupakan subjek yang sangat menarik.

Itu sahaja untuk hari ini kawan-kawan, saya harap anda faham sedikit lagi tentang cara menggunakan Sets in Go atau anda juga faham topik ini. Saya bercadang untuk membuat Bahagian 2 mengenai perkara ini. Selamat malam dan jumpa lagi pada masa akan datang!

• Pautan Repositori Hashicorp: https://github.com/hashicorp/go-set
• Tapak web untuk lebih memahami BigO: https://www.bigochheatsheet.com/
• Saya sedang mencipta CLI yang berfungsi sebagai alat untuk mempercepatkan produktiviti anda dalam Go, sila lihat: https://github.com/YlanzinhoY/tooling_golang

Atas ialah kandungan terperinci Struktur Data: Set - Golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!