Golang, warum haben wir keine festgelegte Datenstruktur? [geschlossen]

129

Ich versuche, die Übung Nr. 1.4 "Die Go-Programmiersprache" zu lösen, für die ich ein Set haben muss. Ich kann einen Set-Typ erstellen, aber warum kommt die Sprache nicht mit einem? go, nachdem sie von Google gekommen waren, wo auch Guave entstand, warum haben sich die Sprachdesigner nicht dafür entschieden, Unterstützung für grundlegende Datenstrukturen hinzuzufügen? Warum sollten Sie Ihre Benutzer dazu zwingen, ihre eigenen Implementierungen für etwas so Grundlegendes wie ein Set zu erstellen?

data-structures go set anjanb
quelle
11
Hmmm. Fragen Sie sich, warum die negativen Stimmen? Ich komme aus der Java-Welt, in der wir fast von Anfang an ein Set hatten, auch ohne Generika. Also, ich finde dieses Verhalten ein
bisschen

Antworten:

83

Zum Teil, weil Go keine Generika hat (Sie würden also für jeden Typ einen Satztyp benötigen oder auf Reflexion zurückgreifen, was ziemlich ineffizient ist).

Zum Teil, weil Sie, wenn Sie nur "einzelne Elemente zu einer Menge hinzufügen / entfernen" und "relativ platzsparend" benötigen, ein gutes Stück davon erhalten können, indem Sie einfach a verwenden map[yourtype]bool(und den Wert truefür jedes Element in der Menge auf setzen ) oder, um die Raumeffizienz zu erhöhen, können Sie eine leere Struktur als Wert verwenden und die _, present = the_setoid[key]Anwesenheit prüfen.

Vatine
quelle
1
Es scheint auch im Geiste von Go zu sein, es einfach in Ihren eigenen Code zu schreiben, indem Sie entweder den Satz in einen anderen Code "einfügen" oder bei Bedarf Ihren eigenen Satztyp definieren. Wie auch immer, die Verwendung von std :: set <T> in C ++ geschieht immer als Teil einer Funktionsimplementierung oder der Implementierung einer anderen Datenstruktur. Implementieren Sie daher einfach diese andere Datenstruktur direkt mithilfe von Karten und Slices und allen anderen benötigten Bausteinen, jedoch ohne eingebauten Satz. Jede Verwendung eines Sets wird es sowieso etwas anders verwenden :)
Bjarke Ebert
1
Aber normalerweise brauchen Sie nicht wirklich eine Menge <Foo> für sich, sondern eine Menge <Foo>, um etwas Größeres zu implementieren. Ich habe Tonnen von Code gesehen, in denen die Dinge, die Sie tun müssen, um eine "wiederverwendbare" Komponente einzuschließen, viel schlimmer sind, als nur die Notwendigkeit zu vermeiden. Hier haben wir also eine Menge <Foo>, diese Funktion dort drüben braucht eine Menge <Bar>, hoppla, haben wir noch Kovarianz, oder wie wäre es, eine WrapperFactory zu erstellen, damit dieses Ding so aussieht wie dieses Ding usw. Vielleicht diese andere Funktion braucht wirklich nur eine Schnittstelle, die auf Mitgliedschaft prüfen kann, also sende ihr kein Set <Foo>.
Bjarke Ebert
42
Wenn es also keine Generika gibt, wie wird die "generische" Karte überhaupt implementiert?
Fermin Silva
26
Beachten Sie, dass Sie map[T]struct{}anstelle von Bytes anstelle von verwenden können map[T]bool.
Emersion
4
Werfen
emersion
69

Ein Grund ist, dass es einfach ist, ein Set aus einer Karte zu erstellen:

s := map[int]bool{5: true, 2: true}
_, ok := s[6] // check for existence
s[8] = true // add element 
delete(s, 2) // remove element

Union

s_union := map[int]bool{}
for k, _ := range s1{
    s_union[k] = true
}
for k, _ := range s2{
    s_union[k] = true
}

Überschneidung

s_intersection := map[int]bool{}
for k,_ := range s1 { 
  if s2[k] {
    s_intersection[k] = true
  }
}

Es ist nicht wirklich schwer, alle anderen Set-Operationen zu implementieren.

Salvador Dali
quelle
10
Die Überprüfung der Existenz indiziert einfach die Karte. Denn wenn es nicht drin ist, falsesagt der Nullwert (der ist ) das richtig. Zum Testen ist die Komma-OK-Sprache nicht erforderlich.
icza
2
Die Implementierung für die Kreuzung sieht für den Unterschied so aus.
Musiphil
1
@ Kittsil danke. Aktualisiert.
Salvador Dali
34
Es ist optimaler zu verwenden map[int]struct{}als bool, da eine leere Struktur 0 Bytes im Speicher belegt. Ich habe vor kurzem einen Kern für diesen gist.github.com/bgadrian/cb8b9344d9c66571ef331a14eb7a2e80
BG Adrian
13
Das ist nicht ganz so einfach. Nur diesen Code überall dort schreiben zu müssen, wo man ein Set verwenden muss, erscheint mir heutzutage lächerlich. Die Unterstützung für Sammlungen sollte in jeder Sprache erfolgen. Eine bessere Antwort ist, dass Go noch nicht so ausgereift ist. Ich bin mir sicher, dass es bald Bibliotheken geben wird, die das abdecken.
Stef
5

Wie Vatine schrieb: Da go keine Generika hat, müsste es Teil der Sprache und nicht der Standardbibliothek sein. Dafür müssten Sie dann die Sprache mit Schlüsselwörtern setzen, Vereinigung, Schnittmenge, Differenz, Teilmenge ...

Der andere Grund ist, dass es überhaupt nicht klar ist, was die "richtige" Implementierung eines Sets ist:

  1. Es gibt einen funktionalen Ansatz:

    func IsInEvenNumbers(n int) bool {
    if n % 2 == 0 {
        return true
    }
   return false
}

Dies ist eine Menge aller geraden Ints. Es hat eine sehr effiziente Suche und Vereinigung, Schnittmenge, Differenz und Teilmenge kann leicht durch funktionale Zusammensetzung erfolgen.

  1. Oder du machst einen has-ähnlichen Ansatz, wie Dali gezeigt hat.

Eine Karte hat dieses Problem nicht, da Sie etwas speichern, das dem Wert zugeordnet ist.

0x434D53
quelle
2
Um Buit-In-Mengen zu verarbeiten, überlädt Pascal eine Reihe von binären Operatoren (mit zwei Argumenten): +für Vereinigung, -Differenz, *Schnittmenge, <=Teilmenge, >=Obermenge, =Gleichheit, <>Ungleichheit und inMitgliedschaft. In Go wäre es also nur ein einziges neues Schlüsselwort - in. Andererseits funktionieren Pascals eingebaute Mengen nur für "Ordnungszahlen" - das heißt für jeden Typ, dem ein ganzzahliger Wert einer bestimmten Größe zugrunde liegt.
Kostix
9
Die Tatsache, dass es mehrere Möglichkeiten gibt, einen Satz zu implementieren, hat viele andere Sprachen nicht davon abgehalten, sie bereitzustellen.
August
@kostix: Go könnte sogar die Syntax s[key](als ob sa map[T]bool) anstelle von verwenden key in s.
Musiphil
2
Gibt es einen Grund, nicht einfach zurückzukehren n % 2 == 0?
João Andrade
4

Eine andere Möglichkeit besteht darin, Bitsätze zu verwenden, für die es mindestens ein Paket gibt, oder Sie können das integrierte große Paket verwenden. In diesem Fall müssen Sie grundsätzlich eine Möglichkeit definieren, Ihr Objekt in einen Index zu konvertieren.

Will Fitzgerald
quelle
1
Ich sollte beachten, dass ich die Originalversion des oben genannten Bitset-Pakets geschrieben habe.
Will Fitzgerald