Warum werden Listen in Go selten verwendet?

Ich bin neu in Go und ziemlich aufgeregt darüber. Aber in allen Sprachen, mit denen ich ausgiebig gearbeitet habe: Delphi, C #, C ++, Python - Listen sind sehr wichtig, da sie im Gegensatz zu Arrays dynamisch in der Größe geändert werden können.

In Golang gibt es zwar eine list.ListStruktur, aber ich sehe nur sehr wenig Dokumentation darüber - ob in Go By Example oder in den drei Go-Büchern, die ich habe - Summerfield, Chisnal und Balbaert - sie alle verbringen viel Zeit mit Arrays und Slices und Fahren Sie dann mit den Karten fort. In Quellcodebeispielen finde ich auch wenig oder gar keine Verwendung list.List.

Es scheint auch, dass im Gegensatz zu Python Rangefür List - großer Nachteil IMO nicht unterstützt wird. Vermisse ich etwas

Slices sind sicherlich nett, aber sie müssen immer noch auf einem Array mit einer fest codierten Größe basieren. Hier kommt List ins Spiel. Gibt es eine Möglichkeit, ein Array / Slice in Go ohne eine fest codierte Arraygröße zu erstellen? Warum wird List ignoriert?

Fast immer, wenn Sie an eine Liste denken - verwenden Sie stattdessen ein Slice in Go. Slices werden dynamisch in der Größe geändert. Darunter liegt ein zusammenhängender Speicherabschnitt, dessen Größe sich ändern kann.

Sie sind sehr flexibel, wie Sie sehen werden, wenn Sie die SliceTricks-Wiki-Seite lesen .

Hier ist ein Auszug: -

Kopieren

b = make([]T, len(a))
copy(b, a) // or b = append([]T(nil), a...)

Schnitt

a = append(a[:i], a[j:]...)

Löschen

a = append(a[:i], a[i+1:]...) // or a = a[:i+copy(a[i:], a[i+1:])]

Löschen, ohne die Reihenfolge beizubehalten

a[i], a = a[len(a)-1], a[:len(a)-1]

Pop

x, a = a[len(a)-1], a[:len(a)-1]

drücken

a = append(a, x)

Update : Hier ist ein Link zu einem Blog-Beitrag über Slices des Go-Teams selbst, in dem die Beziehung zwischen Slices und Arrays sowie Slice-Interna gut erklärt wird.

Ich habe diese Frage vor einigen Monaten gestellt, als ich anfing, Go zu untersuchen. Seitdem habe ich jeden Tag über Go gelesen und in Go codiert.

Da ich auf diese Frage keine eindeutige Antwort erhalten habe (obwohl ich eine Antwort akzeptiert hatte), werde ich sie jetzt selbst beantworten, basierend auf dem, was ich gelernt habe, seit ich sie gestellt habe:

Gibt es eine Möglichkeit, ein Array / Slice in Go ohne eine fest codierte Arraygröße zu erstellen?

Ja. Für Slices ist kein fest codiertes Array erforderlich, um slicevon:

var sl []int = make([]int,len,cap)

Dieser Code slweist Slice lenmit einer Größe von cap- lenund capVariablen zu, die zur Laufzeit zugewiesen werden können.

Warum wird list.Listignoriert?

Es scheint, dass die Hauptgründe list.List, die in Go wenig Beachtung finden, folgende sind:

• Wie in der Antwort von @Nick Craig-Wood erläutert wurde, gibt es praktisch nichts, was mit Listen gemacht werden kann, die nicht mit Slices gemacht werden können, oft effizienter und mit einer saubereren, eleganteren Syntax. Zum Beispiel das Bereichskonstrukt:

  for i:=range sl {
    sl[i]=i
  }
  

  kann nicht mit list verwendet werden - ein C-Stil für die Schleife ist erforderlich. In vielen Fällen muss die Syntax des C ++ - Sammlungsstils für Listen verwendet werden: push_backusw.

• Vielleicht noch wichtiger ist, dass list.Listes nicht stark typisiert ist - es ist Pythons Listen und Wörterbüchern sehr ähnlich, die es ermöglichen, verschiedene Typen in der Sammlung miteinander zu mischen. Dies scheint dem Go-Ansatz zu widersprechen. Go ist eine sehr stark typisierte Sprache - zum Beispiel müssen implizite Typkonvertierungen, die in Go niemals zulässig sind, selbst ein upCast von intbis int64muss explizit sein. Aber alle Methoden für list.List nehmen leere Schnittstellen - alles geht.

  Einer der Gründe, warum ich Python aufgegeben und zu Go gewechselt habe, ist diese Art von Schwäche im Python-Typsystem, obwohl Python behauptet, "stark typisiert" zu sein (IMO ist es nicht). Go's list.Listscheint eine Art "Mischling" zu sein, der aus C ++ vector<T>und Pythons geboren List()wurde und in Go selbst vielleicht etwas fehl am Platz ist.

Es würde mich nicht überraschen, wenn wir irgendwann in nicht allzu ferner Zukunft eine Liste finden. Die Liste in Go ist veraltet, obwohl sie möglicherweise bestehen bleibt, um den seltenen Situationen Rechnung zu tragen, in denen selbst mit guten Entwurfspraktiken ein Problem am besten gelöst werden kann mit einer Sammlung, die verschiedene Typen enthält. Oder vielleicht ist es da, um Entwicklern der C-Familie eine "Brücke" zu bieten, damit sie sich mit Go vertraut machen können, bevor sie die Nuancen von Slices kennenlernen, die nur für Go, AFAIK, gelten. (In mancher Hinsicht scheinen Slices Stream-Klassen in C ++ oder Delphi ähnlich zu sein, aber nicht vollständig.)

Obwohl ich aus einem Delphi / C ++ / Python-Hintergrund stamme, war ich bei meiner ersten Begegnung mit Go list.Listvertrauter als Go's Slices, da ich mich mit Go besser vertraut gemacht habe. Ich bin zurückgegangen und habe alle meine Listen in Slices geändert. Ich habe noch nichts gefunden sliceund / oder maperlaube es mir nicht, so dass ich es verwenden muss list.List.

Ich denke, das liegt daran, dass es nicht viel zu sagen gibt, da das container/listPaket ziemlich selbsterklärend ist, wenn Sie die Hauptsprache für die Arbeit mit generischen Daten aufgenommen haben.

In Delphi (ohne Generika) oder in C würden Sie Zeiger oder TObjects in der Liste speichern und sie dann beim Abrufen aus der Liste auf ihre realen Typen zurücksetzen. In C ++ sind STL-Listen Vorlagen und daher nach Typ parametrisiert, und in C # (heutzutage) sind Listen generisch.

container/listSpeichert in Go Werte vom Typ, bei interface{}denen es sich um einen speziellen Typ handelt, der Werte eines anderen (realen) Typs darstellen kann, indem ein Paar von Zeigern gespeichert wird: einer auf die Typinfo des enthaltenen Werts und ein Zeiger auf den Wert (oder den Wert direkt, wenn seine Größe nicht größer als die Größe eines Zeigers ist). Wenn Sie also ein Element zur Liste hinzufügen möchten, tun Sie dies einfach, wenn Funktionsparameter vom Typ interface{}Werte für jeden Typ akzeptieren. Wenn Sie jedoch Werte aus der Liste extrahieren und wissen , was mit ihren realen Typen zu tun ist, müssen Sie sie entweder typisieren oder umschalten - beide Ansätze sind nur unterschiedliche Methoden, um im Wesentlichen dasselbe zu tun.

Hier ist ein Beispiel von hier :

package main

import ("fmt" ; "container/list")

func main() {
    var x list.List
    x.PushBack(1)
    x.PushBack(2)
    x.PushBack(3)

    for e := x.Front(); e != nil; e=e.Next() {
        fmt.Println(e.Value.(int))
    }
}

Hier erhalten wir den Wert eines Elements mit e.Value()und geben ihn dann als intTyp des ursprünglich eingefügten Werts ein.

Informationen zu Typzusicherungen und Typschaltern finden Sie in "Effective Go" oder einem anderen Einführungsbuch. In container/listder Dokumentation des Pakets werden alle unterstützten Methodenlisten zusammengefasst.

Beachten Sie, dass Go-Slices über die append()integrierte Funktion erweitert werden können. Dies erfordert manchmal das Erstellen einer Kopie des Hintergrundarrays, geschieht jedoch nicht jedes Mal, da Go das neue Array überdimensioniert und ihm eine größere Kapazität als die angegebene Länge verleiht. Dies bedeutet, dass ein nachfolgender Anhängevorgang ohne eine weitere Datenkopie abgeschlossen werden kann.

Während Sie am Ende mehr Datenkopien haben als mit gleichwertigem Code, der mit verknüpften Listen implementiert ist, müssen Sie die Elemente in der Liste nicht einzeln zuordnen und die NextZeiger aktualisieren . Für viele Anwendungen bietet die Array-basierte Implementierung eine bessere oder ausreichend gute Leistung, so dass dies in der Sprache hervorgehoben wird. Interessanterweise ist der Standardtyp von Python listauch Array-gestützt und weist ähnliche Leistungsmerkmale beim Anhängen von Werten auf.

Es gibt jedoch Fälle, in denen verknüpfte Listen die bessere Wahl sind (z. B. wenn Sie Elemente am Anfang / in der Mitte einer langen Liste einfügen oder entfernen müssen), weshalb eine Standardbibliotheksimplementierung bereitgestellt wird. Ich denke, sie haben keine speziellen Sprachfunktionen hinzugefügt, um mit ihnen zu arbeiten, da diese Fälle weniger häufig sind als diejenigen, in denen Slices verwendet werden.

Sofern das Slice nicht viel zu oft aktualisiert wird (Löschen, Hinzufügen von Elementen an zufälligen Stellen), bietet die Speicherkontiguität von Slices im Vergleich zu verknüpften Listen eine hervorragende Cache-Trefferquote.

Scott Meyers Vortrag über die Bedeutung des Cache. Https://www.youtube.com/watch?v=WDIkqP4JbkE

list.Listwird als doppelt verknüpfte Liste implementiert. Array-basierte Listen (Vektoren in C ++ oder Slices in Golang) sind unter den meisten Bedingungen die bessere Wahl als verknüpfte Listen, wenn Sie nicht häufig in die Mitte der Liste einfügen. Die amortisierte Zeitkomplexität für das Anhängen beträgt O (1) sowohl für die Array-Liste als auch für die verknüpfte Liste, obwohl die Array-Liste die Kapazität erweitern und über vorhandene Werte kopieren muss. Array-Listen haben einen schnelleren Direktzugriff, einen geringeren Speicherbedarf und sind vor allem für den Garbage Collector geeignet, da keine Zeiger in der Datenstruktur vorhanden sind.

Von: https://groups.google.com/forum/#!msg/golang-nuts/mPKCoYNwsoU/tLefhE7tQjMJ

Es hängt sehr von der Anzahl der Elemente in Ihren Listen ab.
 ob eine echte Liste oder ein Slice effizienter ist
 wenn Sie viele Löschungen in der Mitte der Liste vornehmen müssen.

# 1
Je mehr Elemente, desto weniger attraktiv wird eine Scheibe. 

# 2
Wenn die Reihenfolge der Elemente nicht wichtig ist,
 Es ist am effizientesten, ein Slice und zu verwenden
 Löschen eines Elements durch Ersetzen durch das letzte Element im Slice und
 Schneiden Sie die Scheibe erneut, um die Länge um 1 zu verringern
 (wie im SliceTricks-Wiki erklärt)

So
verwendet Scheibe
1. Wenn die Reihenfolge der Elemente in der Liste ist nicht wichtig, und Sie brauchen nur zu löschen,
verwenden Sie tauscht Liste das Element mit dem letzten Elemente zu löschen, und re-Scheibe (Länge-1)
2. wenn Elemente sind ( was auch immer mehr bedeutet)

There are ways to mitigate the deletion problem --
e.g. the swap trick you mentioned or
just marking the elements as logically deleted.
But it's impossible to mitigate the problem of slowness of walking linked lists.

So
verwenden Scheibe
1. Wenn Sie benötigen Geschwindigkeit in Traversal