Legt die Datenstruktur in Golang fest

69

Ich mag Google Golang wirklich, aber könnte jemand erklären, warum die Implementierer eine grundlegende Datenstruktur, wie z. B. Mengen aus der Standardbibliothek, weggelassen haben?

Cobie
quelle
8
Die Sprache heißt eigentlich Go, nicht Golang
jozefg
92
Aber "Golang" ist mehr durchsuchbar
Matt
18
Viel durchsuchbarer. Googeln "go set" liefert Bilder von einem Holzbrett mit schwarzen und weißen Stücken.
Doug Richardson

Antworten:

68

Ein möglicher Grund für diese Auslassung ist, dass es sehr einfach ist, Sets mit einer Karte zu modellieren.

Um ehrlich zu sein, denke ich, dass es auch ein bisschen ein Versehen ist, wenn man sich jedoch Perl ansieht, ist die Geschichte genau dieselbe. In Perl erhalten Sie Listen und Hashtabellen, in Go erhalten Sie Arrays, Slices und Maps. In Perl verwenden Sie in der Regel eine Hash-Tabelle für alle Probleme, die sich auf eine Menge beziehen. Dasselbe gilt für Go.

Beispiel

Um eine Menge von Ints in Go zu imitieren, definieren wir eine Karte:

set := make(map[int]bool)

Etwas hinzuzufügen ist so einfach wie:

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

Etwas zu löschen ist einfach

delete(set, i)

Und die potentielle Unbeholfenheit dieses Konstrukts wird leicht beseitigt:

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
}

Und löschen und erhalten können in ähnlicher Weise definiert werden, ich habe die vollständige Umsetzung hier . Der Hauptnachteil hierbei ist die Tatsache, dass go keine Generika hat. Es ist jedoch möglich, dies zu tun. In diesem interface{}Fall hätten Sie die Ergebnisse von get gewirkt.

jozefg
quelle
3
Hier ist meine leicht überarbeitete Version mit den Methoden "Enthält" und "Größe": play.golang.org/p/tDdutH672-
Rick-777
19
Stattdessen map[int]boolkann man map[int]struct{}stattdessen verwenden. Ich bevorzuge den letzten.
pepper_chico
20
map[int]struct{}.. Das struct{}dauert 0 Bytes.
Boopathi Rajaa
2
github.com/fatih/set ist eine Implementierung von my basierend auf Maps und leeren Strukturen. Es ist threadsicher und hat eine einfache API.
Fatih Arslan
6
Mit können map[int]struct{}Sie nicht if mymap["key"] {auf Mitgliedschaft prüfen. Google empfiehlt die Verwendung vonbool (Suche nach "Ein Satz kann implementiert werden").
Timmmm
3

Ich denke, das hat mit golangEinfachheit zu tun . sets wurde wirklich nützlich mit difference, intersection, union, issubset, und so weiter .. Methoden. Vielleicht hat das golangTeam das Gefühl, dass es für eine Datenstruktur zu viel ist. Aber ansonsten eine "dumme Menge", die nur hat add, containsund removemit der leicht nachgebildet werden kann, mapwie von @jozefg erklärt.

Akavall
quelle
ich stimme dir nicht zu. Ein Set wird hauptsächlich für Mitgliedschaftsüberprüfungen und Eindeutigkeitssemantik verwendet. Eine Set-Implementierung wäre ohne diese Methoden perfekt verwendbar. Abgesehen davon sind sie auch trivial zu implementieren.
Sedat Kapanoglu
2

Die vorherige Antwort funktioniert NUR, WENN der Schlüssel ein eingebauter Typ ist. Als Ergänzung zur vorherigen Antwort können Sie hier eine Menge implementieren, deren Elemente benutzerdefinierte Typen sind:

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
quelle
8
"funktioniert NUR, WENN die Schlüssel ein eingebauter Typ sind" ist falsch . type mySet map[IntPoint]boolfunktioniert einwandfrei. Für den in einer Karte verwendeten Schlüsseltyp ist nur erforderlich, dass er ==und enthält!= . Die Gleichheit der Strukturtypen ist gut definiert, Ihre EqualsMethode sollte gerecht sein p1 == p2.
Dave C
1
Es ist richtig, dass die Gleichheit für Strukturen klar definiert ist. Wenn die Struktur jedoch Maps oder Slices als Felder enthält, werden diese nicht nach Wert, sondern nach Referenz verglichen. Dies ist möglicherweise nicht das, was Sie wollen.
Chaim-Leib Halbert
1
Ich habe ein Problem mit dieser Lösung, weil sie Containslinear und aMap[]konstant ist, unabhängig von der Anzahl der Mitglieder. Eine bessere Lösung würde intern einen eindeutigen Schlüssel erstellen, der auf dem Inhalt jedes Mitglieds basiert, und die vom mapTyp bereitgestellte Abfrage mit konstanter Zeit nutzen . Es gibt auch noch schnellere Lösungen, die das Cache-Verhalten usw. berücksichtigen.
Chaim-Leib Halbert