webentwicklung-frage-antwort-db.com.de

Was ist der idiomatischste Weg, einen Iterator in Go zu erstellen?

Eine Option ist die Verwendung von Kanälen. Channels sind gewissermaßen Iteratoren, die Sie mit dem Range-Schlüsselwort durchlaufen können. Wenn Sie jedoch herausfinden, dass Sie diese Schleife nicht verlassen können, ohne dass Goroutine ausläuft, wird die Nutzung eingeschränkt.

Was ist der idiomatische Weg, um Iteratormuster in go zu erstellen?

Bearbeiten :

Das grundlegende Problem bei Kanälen ist, dass sie ein Push-Modell sind. Iterator ist ein Pull-Modell. Sie müssen dem Iterator nicht sagen, dass er aufhören soll. Ich suche nach einer Möglichkeit, Sammlungen auf eine Nizza ausdrucksstarke Weise zu durchlaufen. Ich möchte auch Iteratoren verketten (Karte, Filter, Alternativen falten).

38
Kugel

Kanäle sind nützlich, aber Verschlüsse sind oft besser geeignet.

package main

import "fmt"

func main() {
    gen := newEven()
    fmt.Println(gen())
    fmt.Println(gen())
    fmt.Println(gen())
    gen = nil // release for garbage collection
}

func newEven() func() int {
    n := 0
    // closure captures variable n
    return func() int {
        n += 2
        return n
    }
}

Spielplatz: http://play.golang.org/p/W7pG_HUOzw

Ich mag auch keine Schließungen? Verwenden Sie einen benannten Typ mit einer Methode:

package main

import "fmt"

func main() {
    gen := even(0)
    fmt.Println(gen.next())
    fmt.Println(gen.next())
    fmt.Println(gen.next())
}

type even int

func (e *even) next() int {
    *e += 2
    return int(*e)
}

Spielplatz: http://play.golang.org/p/o0lerLcAh3

Es gibt Kompromisse zwischen den drei Techniken, so dass Sie eine nicht als idiomatisch bezeichnen können. Verwenden Sie das, was Ihren Bedürfnissen am besten entspricht.

Das Verketten ist einfach, weil Funktionen erstklassige Objekte sind. Hier ist eine Erweiterung des Verschlussbeispiels. Ich habe einen Typ intGen für den Integer-Generator hinzugefügt, der deutlich macht, wo Generatorfunktionen als Argumente und Rückgabewerte verwendet werden. mapInt ist auf allgemeine Weise definiert, um beliebige Integer-Funktionen einem Integer-Generator zuzuordnen. Andere Funktionen wie Filtern und Falzen können auf ähnliche Weise definiert werden.

package main

import "fmt"

func main() {
    gen := mapInt(newEven(), square)
    fmt.Println(gen())
    fmt.Println(gen())
    fmt.Println(gen())
    gen = nil // release for garbage collection
}

type intGen func() int

func newEven() intGen {
    n := 0
    return func() int {
        n += 2
        return n
    }
}

func mapInt(g intGen, f func(int) int) intGen {
    return func() int {
        return f(g())
    }
}

func square(i int) int {
    return i * i
}

Spielplatz: http://play.golang.org/p/L1OFm6JuX0

45
Sonia

TL; DR: Vergessen Sie Schließungen und Kanäle zu langsam. Wenn die einzelnen Elemente Ihrer Sammlung über den Index erreichbar sind, sollten Sie für die klassische C-Iteration einen Array-ähnlichen Typ verwenden. Wenn nicht, implementieren Sie einen Stateful-Iterator.

Ich musste einen Sammeltyp durchlaufen, für den die genaue Speicherimplementierung noch nicht in Stein gemeißelt ist. Dies und die unzähligen anderen Gründe, die Implementierungsdetails vom Client abzugrenzen, veranlassen mich dazu, einige Tests mit verschiedenen Iterationsmethoden durchzuführen. Vollständiger Code hier , einschließlich einiger Implementierungen, die Fehler als Werte verwenden . Hier sind die Benchmark-Ergebnisse:

  • klassische C-Iteration über eine Array-ähnliche Struktur. Der Typ stellt die Methoden ValueAt () und Len () bereit:

    l := Len(collection)
    for i := 0; i < l; i++ { value := collection.ValueAt(i) }
    // benchmark result: 2492641 ns/op
    
  • Verschluss-Iterator. Die Iterator-Methode der Auflistung gibt eine next () - Funktion (eine Schließung über der Auflistung und den Cursor) und ein boolesches hasNext-Objekt zurück. next () gibt den nächsten Wert und einen Booleschen Wert für hasNext zurück. Beachten Sie, dass dies viel schneller abläuft als die Verwendung separater next () - und hasNext () - Schließungen, die einzelne Werte zurückgeben:

    for next, hasNext := collection.Iterator(); hasNext; {
        value, hasNext = next()
    }
    // benchmark result: 7966233 ns/op !!!
    
  • Stateful Iterator. Eine einfache Struktur mit zwei Datenfeldern, der Collection und einem Cursor, und zwei Methoden: Next () und HasNext (). Dieses Mal gibt die Iterator () - Methode der Auflistung einen Zeiger auf eine ordnungsgemäß initialisierte Iteratorstruktur zurück:

    for iter := collection.Iterator(); iter.HasNext(); {
        value := iter.Next()
    }
    // benchmark result: 4010607 ns/op
    

So sehr ich Verschlüsse mag, ist die Leistung ein No-Go. Nun, bei Designmustern bevorzugen Gophers aus gutem Grund den Begriff "idiomatische Art zu tun". Grep auch den Go-Source-Tree für Iteratoren: Mit so wenigen Dateien, die den Namen erwähnen, sind Iteratoren definitiv keine Go-Sache.

Schauen Sie sich auch diese Seite an: http://ewencp.org/blog/golang-iterators/

Schnittstellen helfen hier jedoch in keiner Weise, es sei denn, Sie möchten eine Iterable-Schnittstelle definieren. Dies ist jedoch ein völlig anderes Thema.

14
wldsvc

TL; DR: Iteratoren sind in Go nicht idiomatisch. Überlassen Sie sie anderen Sprachen.

In der Tiefe beginnt dann der Wikipedia-Eintrag "Iterator Pattern". "In der objektorientierten Programmierung ist das Iterator-Pattern ein Entwurfsmuster ..." Zwei rote Fahnen dort: Erstens werden objektorientierte Programmierungskonzepte oft nicht gut in Go übersetzt und zweitens denken viele Go-Programmierer nicht viel an Designmuster. Dieser erste Absatz enthält auch "Das Iteratormuster entkoppelt Algorithmen von Containern", aber nur nachdem "ein Iterator [auf] die Elemente des Containers zugreift". Nun, was ist es? Die Antwort in vielen Sprachen beinhaltet eine Art von Generik, mit der die Sprache über ähnliche Datenstrukturen generalisiert werden kann: Die Antwort in Go sind Schnittstellen: Schnittstellen erzwingen eine strengere Entkopplung von Algorithmen und Objekten, indem der Zugriff auf die Struktur verweigert wird und alle Interaktionen auf Verhalten beruhen Verhalten bedeutet Fähigkeiten, die durch Methoden der Daten ausgedrückt werden.

Für einen minimalen Iteratortyp ist die erforderliche Funktion eine Next-Methode. Eine Go-Schnittstelle kann ein Iteratorobjekt darstellen, indem einfach diese einzige Methodensignatur angegeben wird. Wenn ein Containertyp iterierbar sein soll, muss er die Iteratorschnittstelle satisf durch Implementieren aller Methoden der Schnittstelle _ definieren. (Wir haben hier nur eine, und in der Tat haben Schnittstellen nur eine einzige Methode.)

Ein minimales Arbeitsbeispiel:

package main

import "fmt"

// IntIterator is an iterator object.
// yes, it's just an interface.
type intIterator interface {
    Next() (value int, ok bool)
}

// IterableSlice is a container data structure
// that supports iteration.
// That is, it satisfies intIterator.
type iterableSlice struct {
    x int
    s []int
}

// iterableSlice.Next implements intIterator.Next,
// satisfying the interface.
func (s *iterableSlice) Next() (value int, ok bool) {
    s.x++
    if s.x >= len(s.s) {
        return 0, false
    }
    return s.s[s.x], true
}

// newSlice is a constructor that constructs an iterable
// container object from the native Go slice type.
func newSlice(s []int) *iterableSlice {
    return &iterableSlice{-1, s}
}

func main() {
    // Ds is just intIterator type.
    // It has no access to any data structure.
    var ds intIterator

    // Construct.  Assign the concrete result from newSlice
    // to the interface ds.  ds has a non-nil value now,
    // but still has no access to the structure of the
    // concrete type.
    ds = newSlice([]int{3, 1, 4})

    // iterate
    for {
        // Use behavior only.  Next returns values
        // but without insight as to how the values
        // might have been represented or might have
        // been computed.
        v, ok := ds.Next()
        if !ok {
            break
        }
        fmt.Println(v)
    }
}

Spielplatz: http://play.golang.org/p/AFZzA7PRDR

Dies ist die Grundidee von Interfaces, aber es ist ein absurder Overkill für das Durchlaufen einer Slice. In vielen Fällen, in denen Sie nach einem Iterator in anderen Sprachen suchen würden, schreiben Sie Go-Code mit integrierten Sprachprimitiven, die direkt über Basistypen iterieren. Ihr Code bleibt klar und präzise. Wo das kompliziert wird, überlegen Sie, welche Funktionen Sie wirklich benötigen. Müssen Sie in einer Funktion Ergebnisse von zufälligen Orten ausgeben? Kanäle bieten eine ertragsähnliche Funktion, die dies ermöglicht. Benötigen Sie unendliche Listen oder faule Bewertungen? Verschlüsse funktionieren großartig. Haben Sie unterschiedliche Datentypen und benötigen diese, um dieselben Vorgänge transparent zu unterstützen? Schnittstellen liefern. Mit Kanälen, Funktionen und Schnittstellen, die alle erstklassigen Objekte sind, lassen sich diese Techniken leicht zusammenstellen. Was ist nun der idiomatischste Weg? Experimentieren Sie mit verschiedenen Techniken, machen Sie sich mit ihnen vertraut und nutzen Sie das, was Ihren Bedürfnissen am einfachsten ist. Iteratoren sind im objektorientierten Sinne sowieso fast nie die einfachsten.

13
Sonia

Sie können ohne Leckagen ausbrechen, indem Sie Ihren Goroutinen einen zweiten Kanal für Kontrollmeldungen geben. Im einfachsten Fall ist es nur ein chan bool. Wenn Sie möchten, dass die Goroutine stoppt, senden Sie diesen Kanal. Innerhalb der Goroutine setzen Sie den Kanal des Iterators send und das Listening des Steuerkanals in einen Select.

Hier ist ein Beispiel.

Sie können dies weiter ausführen, indem Sie verschiedene Kontrollmeldungen zulassen, z. B. "Überspringen".

Ihre Frage ist ziemlich abstrakt. Ein konkretes Beispiel wäre hilfreich.

4
Thomas Kappler

Ich habe mir überlegt, wie ich das mit Kanälen und Goroutinen machen soll:

package main

import (
    "fmt"
)

func main() {
    c := nameIterator(3)
    for batch := range c {
        fmt.Println(batch)
    }
}

func nameIterator(batchSize int) <-chan []string {
    names := []string{"Cherry", "Cami", "Tildy", "Cory", "Ronnie", "Aleksandr", "Billie", "Reine", "Gilbertina", "Dotti"}

    c := make(chan []string)

    go func() {
        for i := 0; i < len(names); i++ {
            startIdx := i * batchSize
            endIdx := startIdx + batchSize

            if startIdx > len(names) {
                continue
            }
            if endIdx > len(names) {
                c <- names[startIdx:]
            } else {
                c <- names[startIdx:endIdx]
            }
        }

        close(c)
    }()

    return c
}

https://play.golang.org/p/M6NPT-hYPNd

Die Idee kam von Rob Pikes Go Concurrency Patterns talk.

1
user9772923

Wenn Sie sich das Container-/Listenpaket anschauen, scheint es keine Möglichkeit zu geben. C-like-Methode sollte verwendet werden, wenn Sie über ein Objekt iterieren.

Etwas wie das.

type Foo struct {
...
}

func (f *Foo) Next() int {
...
}

foo := Foo(10)

for f := foo.Next(); f >= 0; f = foo.Next() {
...
}

Wie andere Kollegen sagten, können Sie mit Kanälen arbeiten, um das gewünschte Generator-Entwurfsmuster zu implementieren.

Generatorfunktionen

Kanäle und Goroutinen bieten ein natürliches Substrat für die Implementierung einer Form von Erzeuger/Erzeugermuster unter Verwendung von Generatorfunktionen. Bei diesem Ansatz wird eine Goroutine in eine Funktion eingeschlossen, die Werte generiert, die über einen von der Funktion zurückgegebenen Kanal gesendet werden. Die Consumer-Goroutine erhält diese Werte beim Erzeugen.

Beispiel extrahiert aus Go Design Patterns For Real-World

package main

import (
    "fmt"
    "strings"
    )

func main() {
    data := []string{"Sphinx of black quartz, judge my vow", 
             "The sky is blue and the water too", 
             "Cozy lummox gives smart squid who asks for job pen",
             "Jackdaws love my big sphinx of quartz",
             "The quick onyx goblin jumps over the lazy dwarf"}
    histogram := make(map[string]int)
    words := words(data) // returns handle to data channel
    for Word := range words { // Reads each Word from channel every time
        histogram[Word]++
    }   
    fmt.Println(histogram)
}

// Generator function that produces data
func words(data []string) <-chan string {
    out := make(chan string)
    // Go Routine
    go func() {
        defer close(out) // closes channel upon fn return
        for _, line := range data {
            words := strings.Split(line, " ")
            for _, Word := range words {
                Word = strings.ToLower(Word)
                out <- Word // Send Word to channel 
            }
        }
     }()
     return out
}

https://play.golang.org/p/f0nynFWbEam

In diesem Beispiel gibt die Generatorfunktion, die als func words (data [] string) <- chan string deklariert ist, einen Nur-Empfangs-Kanal von Zeichenfolgenelementen zurück. Die Consumer-Funktion, in diesem Fall main (), empfängt die von der Generatorfunktion ausgegebenen Daten, die mit einer for… range -Schleife verarbeitet werden.

Eine verbesserte Version dieses Entwurfsmusters:

https://play.golang.org/p/uyUfz3ALO6J

Hinzufügen von Methoden wie Weiter und Fehler:

type iterator struct {
    valueChan   <-chan interface{}
    okChan      <-chan bool
    errChan     <-chan error
    err     error
}

func (i *iterator) next() (interface{}, bool) {
    var (
        value   interface{}
        ok  bool
    )
    value, ok, i.err = <-i.valueChan, <-i.okChan, <-i.errChan
    return value, ok
}

func (i *iterator) error() error {
    return i.err
}

// Generator function that produces data
func NewIterator(data []string) iterator {
    out := make(chan interface{})
    ok := make(chan bool)
    err := make(chan error)
    // Go Routine
    go func() {
        defer close(out) // closes channel upon fn return
        for _, line := range data {
            words := strings.Split(line, " ")
            for _, Word := range words {
                Word = strings.ToLower(Word)
                out <- Word // Send Word to channel and waits for its reading
                ok <- true
                err <- nil // if there was any error, change its value
            }
        }
        out <- ""
        ok <- false
        err <- nil
     }()

     return iterator{ out, ok, err, nil }
}
0
omotto

Die Tatsache, dass es hier so viele scheinbar unterschiedliche Lösungen gibt, bedeutet, dass dies keine idiomatische Methode zu sein scheint. Ich beginne meinen Weg in Go und dachte, es gäbe eine Möglichkeit, die Macht der range - Sache zu nutzen. Traurigerweise Nein.

Folgendes habe ich mir ausgedacht (es ähnelt einigen der oben genannten Lösungen):

// Node Basically, this is the iterator (or the head of it) 
// and the scaffolding for your itterable type
type Node struct {
    next *Node
}

func (node *Node) Next() (*Node, bool) {
    return node.next, node.next != nil
}

// Add add the next node
func (node *Node) Add(another *Node) {
    node.next = another
}

und so benutze ich es:

node := &Node{}
node.Add(&Node{})

for goOn := true; goOn; node, goOn = node.Next() {
    fmt.Println(node)
}

Oder wahrscheinlich eine elegantere Lösung:

...
func (node *Node) Next() *Node {
    return node.next
}
...

for ; node != nil; node = node.Next() {
    fmt.Println(node)
}
0
Ibolit