Какой самый идиоматический способ создания итератора в Go?

Ответ 1

Каналы полезны, но замыкания часто более подходят.

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

Существуют три компромисса между тремя методами, поэтому вы не можете выдвигать их как идиоматические. Используйте все, что наилучшим образом соответствует вашим потребностям.

Цепочки легко, потому что функции являются объектами первого класса. Здесь - расширение примера замыкания. Я добавил тип 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

Ответ 2

TL; DR: Итераторы не являются идиоматическими в Go. Оставьте их на других языках.

В глубине затем начинается запись в Википедии "Итераторский шаблон": "В объектно-ориентированном программировании шаблон итератора является шаблоном проектирования...". Два красных флажка: во-первых, объектно-ориентированные концепции программирования часто не переводят хорошо в Go, и во-вторых, многие программисты Go не думают много о шаблонах дизайна. Этот первый абзац также включает в себя: "Итератор-шаблон отделяет алгоритмы от контейнеров", но только после указания "итератора [обращается] к элементам контейнера. Ну, а это? Если алгоритм обращается к элементам контейнера, он вряд ли может претендовать на развязку. Ответ на многих языках включает в себя некие генерики, которые позволяют обобщить язык по сравнению с аналогичными структурами данных. Ответ в Go - это интерфейсы. Интерфейсы обеспечивают более строгую развязку алгоритмов и объектов, лишая доступ к структуре и требуя, чтобы все взаимодействия были основаны на поведении Поведение означает возможности, выраженные посредством методов данных.

Для минимального типа итератора необходимая возможность - это метод Next. Интерфейс Go может представлять объект итератора, просто указывая эту подпись одного метода. Если вы хотите, чтобы тип контейнера был итерируемым, он должен удовлетворять интерфейсу итератора, реализуя все методы интерфейса. (У нас здесь только один, и на самом деле для интерфейсов обычно существует только один метод.)

Минимальный рабочий пример:

package main

import "fmt"

// IntIterator is an iterator object.
// yes, it 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 с использованием встроенных языковых примитивов, которые передаются непосредственно по базовым типам. Ваш код остается четким и кратким. Если это усложняется, подумайте о том, какие функции вам действительно нужны. Вам нужно испускать результаты из случайных мест в какой-то функции? Каналы обеспечивают возможность выхода, которая позволяет это. Вам нужны бесконечные списки или ленивая оценка? Закрытие отлично работает. У вас разные типы данных, и вам нужно, чтобы они прозрачно поддерживали одни и те же операции? Поставляются интерфейсы. С каналами, функциями и интерфейсами все объекты первого класса эти методы легко скомпилируются. Так что же тогда самый идиоматический путь? Это эксперимент с различными приемами, удобство с ними и использование любого, что отвечает вашим потребностям самым простым способом. Итераторы, в объектно-ориентированном смысле, почти никогда не просты.

Ответ 3

TL; DR: Забудьте о закрытиях и каналах, слишком медленных. Если отдельные элементы вашей коллекции доступны по индексу, перейдите к классической итерации по типу массива. Если нет, выполните итератор с сохранением состояния.

Мне нужно было перебирать некоторый тип коллекции, для которого точная реализация хранилища еще не задана. Это, плюс циллионы, другие причины абстрагировать детали реализации от клиента, заставляют меня выполнять некоторые тесты с помощью различных методов итерации. Полный код здесь, включая некоторые реализации, которые используют ошибки как значения. Вот результаты тестов:

• классическая итерация по массивной структуре. Тип предоставляет методы ValueAt() и Len():

  l := Len(collection)
  for i := 0; i < l; i++ { value := collection.ValueAt(i) }
  // benchmark result: 2492641 ns/op
  

• Итератор стиля закрытия. Метод Iterator коллекции возвращает функцию next() (замыкание по коллекции и курсору) и hasNext boolean. next() возвращает следующее значение и hasNext boolean. Обратите внимание, что это выполняется намного быстрее, чем использование отдельных next() и hasNext() замыканий, возвращающих одиночные значения:

  for next, hasNext := collection.Iterator(); hasNext; {
      value, hasNext = next()
  }
  // benchmark result: 7966233 ns/op !!!
  

• Истинный итератор. Простая структура с двумя полями данных, коллекцией и курсором и двумя методами: Next() и HasNext(). На этот раз метод Iterator() коллекции возвращает указатель на правильно инициализированную структуру итератора:

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

Насколько мне нравится закрытие, производительность мудрая - это не-Go. Что касается шаблонов дизайна, то Гофер предпочитает термин "идиоматический способ", чтобы не на что основать. Также grep дерево исходного дерева для итераторов: с таким количеством файлов, в которых упоминается имя, итераторы определенно не являются идеей Go.

Также ознакомьтесь с этой страницей: http://ewencp.org/blog/golang-iterators/

В любом случае, интерфейсы здесь никак не помогают, если вы не хотите определять какой-либо интерфейс Iterable, но это совершенно другой предмет.

Ответ 4

Вы можете выйти из строя, не просачиваясь, предоставив вашим гортанам второй канал для управляющих сообщений. В простейшем случае это просто a chan bool. Когда вы хотите, чтобы goroutine остановился, вы отправляете этот канал. Внутри goroutine вы помещаете канал канала итератора и слушаете канал управления внутри выбранного.

Вот пример.

Вы можете сделать это дальше, разрешив различные управляющие сообщения, такие как "пропустить".

Ваш вопрос довольно абстрактный, так сказать, конкретный пример был бы полезен.

Ответ 5

Глядя на пакет контейнера/списка, похоже, что нет никакого способа сделать это. C-образный способ следует использовать, если вы перебираете объект.

Что-то вроде этого.

type Foo struct {
...
}

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

foo := Foo(10)

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

Ответ 6

Вот способ, которым я думал сделать это с помощью каналов и goroutines:

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

Я получил идею из выступления Роба Пайка Go Concurrency Patterns.

Ответ 7

Тот факт, что здесь так много разных, казалось бы, разных решений, означает, что это не кажется идиоматическим способом сделать это. Я начинаю свой путь в Го, и я подумал, что будет способ задействовать силу вещи 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)
}

Ответ 8

Как говорили другие партнеры, вы можете работать с каналами для реализации шаблона проектирования Generator, который вам нужен.

Функции генератора

Каналы и горутины обеспечивают естественный субстрат для реализации формы шаблон производитель/производитель с использованием функций генератора. При таком подходе горутин обернут в функцию, которая генерирует значения, которые отправляются через канал, возвращаемый функция. Потребительская программа получает эти значения по мере их создания.

Пример извлечен из Go Design Patterns для реального мира

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) & lt; - 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 }
}