iterator - Goでイテレータを作成する最も慣用的な方法は何ですか？

Question

1つのオプションは、チャネルを使用することです。チャネルはある意味でイテレータのようなものであり、rangeキーワードを使用してチャネルを反復処理できます。しかし、ゴルーチンをリークせずにこのループから抜け出すことはできないことがわかった場合、使用は制限されます。

goでイテレータパターンを作成する慣用的な方法は何ですか？

編集：

チャネルの基本的な問題は、チャネルがプッシュモデルであるということです。イテレータはプルモデルです。イテレータに停止するように指示する必要はありません。表現力豊かな方法でコレクションを反復処理する方法を探しています。また、イテレータ（マップ、フィルター、フォールドの選択肢）をチェーンしたいと思います。

score 68 · Accepted Answer

チャネルは便利ですが、多くの場合、クロージャーの方が適しています。

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
    }
}

遊び場： http： //play.golang.org/p/W7pG_HUOzw

クロージャも好きではありませんか？メソッドで名前付きタイプを使用します。

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)
}

遊び場： http： //play.golang.org/p/o0lerLcAh3

3つの手法にはトレードオフがあるため、1つを慣用的なものとして指定することはできません。ニーズに最適なものを使用してください。

関数はファーストクラスのオブジェクトであるため、連鎖は簡単です。これがクロージャーの例の拡張です。整数ジェネレーターのタイプintGenを追加しました。これにより、ジェネレーター関数が引数および戻り値として使用される場所が明確になります。mapIntは、任意の整数関数を整数ジェネレーターにマップするための一般的な方法で定義されます。フィルタやフォールドなどの他の関数も同様に定義できます。

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
}

遊び場： http： //play.golang.org/p/L1OFm6JuX0

score 30 · Accepted Answer

TL; DR：クロージャとチャネルを忘れてください。遅すぎます。コレクションの個々の要素にインデックスでアクセスできる場合は、配列のようなタイプで従来のC反復を実行します。そうでない場合は、ステートフルイテレータを実装します。

正確なストレージの実装がまだ決まっていないコレクションタイプを繰り返す必要がありました。これに加えて、クライアントから実装の詳細を抽象化する他の無数の理由により、さまざまな反復法を使用していくつかのテストを行うことになります。ここに完全なコードがあり、エラーを値として使用するいくつかの実装が含まれています。ベンチマーク結果は次のとおりです。

配列のような構造に対する古典的なCの反復。このタイプは、ValueAt（）メソッドとLen（）メソッドを提供します。
```
l := Len(collection)
for i := 0; i < l; i++ { value := collection.ValueAt(i) }
// benchmark result: 2492641 ns/op
```
クロージャスタイルのイテレータ。コレクションのIteratorメソッドは、next（）関数（コレクションとカーソルのクロージャー）とhasNextブール値を返します。next（）は、次の値とhasNextブール値を返します。これは、単一の値を返す個別のnext（）およびhasNext（）クロージャを使用するよりもはるかに高速に実行されることに注意してください。
```
for next, hasNext := collection.Iterator(); hasNext; {
    value, hasNext = next()
}
// benchmark result: 7966233 ns/op !!!
```
ステートフルイテレータ。コレクションとカーソルの2つのデータフィールドと、Next（）とHasNext（）の2つのメソッドを持つ単純な構造体。今回は、コレクションのIterator（）メソッドが、適切に初期化されたイテレーター構造体へのポインターを返します。
```
for iter := collection.Iterator(); iter.HasNext(); {
    value := iter.Next()
}
// benchmark result: 4010607 ns/op
```

私がクロージャが好きなのと同じくらい、パフォーマンスの面ではそれはノーゴーです。デザインパターンに関しては、Gophersは、正当な理由から「慣用的な方法」という用語を好みます。また、イテレータのgoソースツリーをgrepします。名前に言及しているファイルが非常に少ないため、イテレータは間違いなくGoではありません。

このページもチェックしてください：http：//ewencp.org/blog/golang-iterators/

とにかく、Iterableインターフェースを定義したい場合を除いて、インターフェースはここではまったく役に立ちませんが、これは完全に異なる主題です。

score 20 · Accepted Answer

TL; DR：イテレータはGoでは慣用的ではありません。それらを他の言語に任せてください。

次に、Wikipediaのエントリ「Iteratorpattern」が始まります。「オブジェクト指向プログラミングでは、Iteratorパターンはデザインパターンです...」2つの危険信号：まず、オブジェクト指向プログラミングの概念は、Goにうまく変換されないことがよくあります。、そして第二に、多くのGoプログラマーはデザインパターンについてあまり考えていません。その最初の段落には「イテレータパターンがコンテナからアルゴリズムを分離する」も含まれていますが、「イテレータはコンテナの要素に[アクセス]します。それはどちらですか？アルゴリズムがコンテナの要素にアクセスしている場合、分離されているとはほとんど言えません。多くの言語での答えには、言語が同様のデータ構造を一般化できるようにするある種のジェネリックが含まれます。Goでの答えはインターフェイスです。インターフェイスは、構造へのアクセスを拒否し、すべての対話が動作に基づくことを要求することにより、アルゴリズムとオブジェクトのより厳密な分離を強制します。行動とは、データの方法で表現された潜在能力を意味します。

最小限のイテレータタイプの場合、必要な機能はNextメソッドです。Goインターフェースは、この単一のメソッドシグネチャを指定するだけでイテレータオブジェクトを表すことができます。コンテナタイプを反復可能にする場合は、インターフェイスのすべてのメソッドを実装することにより、イテレータインターフェイスを満たす必要があります。（ここには1つしかありません。実際、インターフェイスには1つのメソッドしかないのが一般的です。）

最小限の作業例：

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)
    }
}

遊び場： http： //play.golang.org/p/AFZzA7PRDR

これはインターフェースの基本的な考え方ですが、スライスを反復処理するのはばかげたやり過ぎです。他の言語のイテレータにたどり着く多くの場合、基本型を直接反復する組み込みの言語プリミティブを使用してGoコードを記述します。コードは明確で簡潔なままです。それが複雑になる場合は、本当に必要な機能を検討してください。いくつかの関数のランダムな場所から結果を出す必要がありますか？チャネルは、それを可能にする歩留まりのような機能を提供します。無限のリストまたは遅延評価が必要ですか？クロージャはうまく機能します。異なるデータ型があり、同じ操作を透過的にサポートするためにそれらが必要ですか？インターフェイスが提供します。チャネル、関数、およびインターフェイスがすべてファーストクラスのオブジェクトであるため、これらの手法はすべて簡単に構成できます。では、最も慣用的なものは何ですか仕方？さまざまなテクニックを試し、それらに慣れ、ニーズに合ったものを可能な限り簡単な方法で使用することです。とにかく、オブジェクト指向の意味でのイテレータは、ほとんど決して単純ではありません。

score 3 · Accepted Answer

ゴルーチンに制御メッセージ用の2番目のチャネルを与えることで、リークすることなくブレークアウトできます。最も単純なケースでは、それはただのchan boolです。ゴルーチンを停止したい場合は、このチャネルで送信します。ゴルーチン内では、イテレーターのチャネル送信とリッスンを選択内の制御チャネルに配置します。

これが例です。

「スキップ」などのさまざまな制御メッセージを許可することで、これをさらに進めることができます。

あなたの質問はかなり抽象的なので、もっと言えば、具体的な例が役立つでしょう。

score 1 · Accepted Answer

コンテナ/リストパッケージを見ると、それを行う方法がないように見えます。オブジェクトを反復処理する場合は、Cのような方法を使用する必要があります。

このようなもの。

type Foo struct {
...
}

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

foo := Foo(10)

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

score 1 · Accepted Answer

これが私がチャンネルとゴルーチンでそれをすることを考えた方法です：

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

私はRobPikeのGoConcurrencyPatternsの話からアイデアを得ました。

score 1 · Accepted Answer

ここに非常に多くの一見異なる解決策があるという事実は、それを行うための慣用的な方法ではないように思われることを意味します。私は囲碁で自分の道を歩み始めています、そして私はrange物事の力を利用する方法があるだろうと思いました。悲しいことに、違います。

これが私が思いついたものです（これは上記の解決策のいくつかに似ています）

// 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
}

これが私がそれを使う方法です：

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

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

または、おそらくよりエレガントなソリューション：

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

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

score 1 · Accepted Answer

私はこのテーマに関する記事を公開しました：

https://serge-hulne.medium.com/iterators-map-filter-reduce-and-list-processing-in-go-golang-implementing-python-functional-2d24d780051f

関連するGitリポジトリがあります：https ：//github.com/serge-hulne/iter/tree/main/iterate

主なアイデアは：

func Fib(n int) chan int {
    out := make(chan int)
    go func() {
        defer close(out)
        for i, j := 0, 1; i < n; i, j = i+j, i {
            out <- i
        }
    }()
    return out
}

使用されます：

fibs = Fib(100)
for i := range Map(fibs) {
    fmt.Printf("i = %6v\n", i)
}

score 0 · Accepted Answer

他の仲間が言ったように、あなたはあなたが探しているものであるジェネレータデザインパターンを実装するためにチャンネルと協力することができます。

ジェネレーター機能

チャネルとゴルーチンは、ジェネレーター機能を使用してプロデューサー/プロデューサーパターンの形式を実装するための自然な基盤を提供します。このアプローチでは、ゴルーチンは、関数によって返されるチャネルを介して送信される値を生成する関数にラップされます。コンシューマーゴルーチンは、生成時にこれらの値を受け取ります。

実世界のGoデザインパターンから抽出された例

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

この例では、func words（data [] string）<-chan stringとして宣言されたジェネレーター関数は、文字列要素の受信専用チャネルを返します。コンシューマー関数（この例ではmain（））は、ジェネレーター関数によって発行されたデータを受け取ります。このデータは、for…rangeループを使用して処理されます。

このデザインパターンの改良版：

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

NextやErrorなどのメソッドを追加する：

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 }
}

iterator - Goでイテレータを作成する最も慣用的な方法は何ですか？

9 に答える 9

Related

Reference