データ構造: セット - Golang

みなさんこんにちは、お元気ですか？今日は、Set と呼ばれるデータ構造の作成からなる Go に関連した内容を説明していきたいと思います。

結局のところ、セットとは何でしょうか?

セットは、非反復値のコレクションを含む線形データ セットです。 Set は、特定の順序に関係なく一意の値を保存できます。

結局のところ、Go には Set があるのでしょうか?

答えはノーです。 Go には、たとえば Java や C# のような Set または HashSet データ構造がありません。しかし、Terraform を所有する大手テクノロジー企業である Hashicorp は、Go の世界におけるこの種の問題を解決するライブラリを持っています。記事の最後にリポジトリのリンクを残しておきます。

Set はどのような問題を解決しますか?

• メンバーシップ チェック: Excel 内に要素が存在するかどうかをすばやくチェックするように設定します。これは、セットでは高速検索にハッシュ技術がよく使用され、メンバーシップ チェックの平均時間計算量が O(1) になるためです。

• 一意の要素の検索: セットを使用すると、リスト内の個別の要素を数えたり検索したりすることが効率的になります。すべての要素をセットに追加するだけで、一意のエントリのみが含まれます。これにより、複雑な比較ループが不要になります。

• 集合演算: 集合は、和集合 (2 つの集合の要素を結合する)、交差 (2 つの集合に共通する要素を見つける)、および差分 (一方の集合にあるがもう一方の集合にはない要素) などの演算のための組み込み関数を提供します。 。これらの操作は、データの操作と分析に非常に役立ちます。

• セットが優れた選択肢となり得る問題の具体例をいくつか示します:

• リスト内の重複要素を検索: すべての要素をセットに追加します。設定されたサイズが元のリストのサイズより小さい場合、重複があります。
  2 つのリストの共通部分を検索します。交差集合演算を使用して、両方のリストに存在する要素を検索します。

• データセット内の頻繁な要素の特定: 要素をセットに追加し、その出現数をカウントします。このセットでは重複が排除され、固有の要素とその頻度に焦点を当てることができます。

• 文字列が回文であるかどうかを確認する: 文字列をセットに変換し、そのサイズを確認します。重複を削除してもサイズが変わらない場合、それは回文です (すべての文字が 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]

非常に興味深いテーマであるインターセクトとユニオンについて話す第 2 部を用意するつもりです。

今日はここまでです。Go での Set の使用方法についてもう少し理解していただけたでしょうか、あるいはこのトピックについても理解していただけたでしょうか。このテーマについてはパート 2 を行う予定です。おやすみ、また次回お会いしましょう!

• Hashicorp リポジトリ リンク: https://github.com/bashicorp/go-set
• BigO をより深く理解するための Web サイト: https://www.bigochheatsheet.com/
• Go の生産性を向上させるツールとして機能する CLI を作成しています。ご覧ください: https://github.com/YlanzinhoY/tooling_golang

以上がデータ構造: セット - Golangの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。