Ustawia strukturę danych w Golang

69

Naprawdę lubię google golang, ale czy ktoś mógłby wyjaśnić, jakie są uzasadnienia dla implementatorów, którzy opuścili podstawową strukturę danych, taką jak zestawy ze standardowej biblioteki?

cobie
źródło
8
Język nazywa się Go, a nie golang
jozefg
92
Ale „golang” jest bardziej przeszukiwalny
Matt
18
O wiele łatwiejsze do przeszukiwania. Googling „go set” zwraca obrazy drewnianej deski z czarno-białymi elementami.
Doug Richardson

Odpowiedzi:

68

Jednym z potencjalnych powodów tego pominięcia jest to, że bardzo łatwo jest modelować zestawy za pomocą mapy.

Szczerze mówiąc, myślę, że to trochę przeoczenie, ale patrząc na Perla, historia jest dokładnie taka sama. W Perlu dostajesz listy i tablice skrótów, w Go - tablice, plastry i mapy. W Perlu na ogół używasz tablicy mieszającej dla wszystkich problemów związanych z zestawem, to samo dotyczy Go.

Przykład

aby naśladować zbiór int w Go, definiujemy mapę:

set := make(map[int]bool)

Dodanie czegoś jest tak proste jak:

i := valueToAdd()
set[i] = true

Usunięcie czegoś jest po prostu

delete(set, i)

Potencjalną niezręczność tego konstruktu łatwo można oderwać:

type IntSet struct {
    set map[int]bool
}

func (set *IntSet) Add(i int) bool {
    _, found := set.set[i]
    set.set[i] = true
    return !found   //False if it existed already
}

I usunąć i uzyskać można zdefiniować podobnie, mam pełną realizację tutaj . Główną wadą tutaj jest fakt, że go nie ma leków generycznych. Można to jednak zrobić interface{}w takim przypadku, w którym uzyskałbyś wyniki get.

jozefg
źródło
3
Oto moja nieco poprawiona wersja z metodami Contains and Size: play.golang.org/p/tDdutH672-
Rick-777
19
Zamiast map[int]booljednego można użyć map[int]struct{}zamiast tego. Wolę ostatni.
pepper_chico
20
map[int]struct{}.. struct{}Zajmuje 0 bajtów.
Boopathi Rajaa
2
github.com/fatih/set jest implementacją mojej opartej na mapach i pustych strukturach. Jest bezpieczny dla wątków i ma prosty interfejs API.
Fatih Arslan
6
Dzięki map[int]struct{}nie możesz zrobić, if mymap["key"] {aby sprawdzić członkostwo. Google zaleca użyciebool (wyszukaj „Zestaw można zaimplementować”).
Timmmm
3

Myślę, że ma to związek z golangprostotą. sety stają się bardzo użyteczne z difference, intersection, union, issubset, i tak dalej .. metod. Być może golangzespół uznał, że to za dużo dla jednej struktury danych. Ale poza tym jest „głupi zestaw”, który tylko ma add, containsi removemoże być łatwo powielane z mapjak wyjaśnił @jozefg.

Akavall
źródło
nie zgadzam się. zestaw służy głównie do sprawdzania członkostwa i semantyki unikalności. wdrożenie zestawu byłoby idealnie użyteczne bez tych metod. Biorąc to pod uwagę, są one również łatwe do wdrożenia.
Sedat Kapanoglu
2

Poprzednia odpowiedź działa TYLKO JEŻELI klucz jest wbudowany. Aby uzupełnić poprzednią odpowiedź, oto sposób na zaimplementowanie zestawu, którego elementami są typy zdefiniowane przez użytkownika:

package math

// types

type IntPoint struct {
    X, Y int
}

// set implementation for small number of items
type IntPointSet struct {
    slice []IntPoint 
}

// functions

func (p1 IntPoint) Equals(p2 IntPoint) bool {
    return (p1.X == p2.X) && (p1.Y == p2.Y)
}

func (set *IntPointSet) Add(p IntPoint) {
    if ! set.Contains(p) {
        set.slice = append(set.slice, p)
    }
}

func (set IntPointSet) Contains(p IntPoint) bool {
  for _, v := range set.slice {
    if v.Equals(p) {
      return true
    }
  }
  return false
}

func (set IntPointSet) NumElements() int {
    return len(set.slice)
}

func NewIntPointSet() IntPointSet {
  return IntPointSet{(make([]IntPoint, 0, 10))}
}
amahfouz
źródło
8
„działa TYLKO JEŚLI klucz jest wbudowany” jest niepoprawne . type mySet map[IntPoint]booldziała doskonale. Wszystko, co jest wymagane od typu klucza używanego na mapie, to , że ma ==i!= . Równość typów struktur jest dobrze zdefiniowana, twoja Equalsmetoda powinna być sprawiedliwa p1 == p2.
Dave C
1
Prawdą jest, że równość struktur jest dobrze zdefiniowana, ale jeśli struktura zawiera mapy lub plastry jako pola, zostaną one porównane przez odniesienie, a nie przez wartość. To może nie być to, czego chcesz.
Chaim-Leib Halbert
1
Podchodzę trochę do tego rozwiązania, ponieważ Containszajmuje czas liniowy, a aMap[]trwa cały czas, niezależnie od liczby członków. Lepsze rozwiązanie stworzyłoby wewnętrznie unikatowy klucz oparty na zawartości każdego elementu i wykorzystywałby zapytania w trybie ciągłym mapdostarczane przez ten typ. Istnieją nawet szybsze rozwiązania, które uwzględniają zachowanie pamięci podręcznej itp.
Chaim-Leib Halbert