remove - java iterator实现




在Go中创建迭代器的最惯用方法是什么? (4)

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 !!!
    
  • 有状态迭代器。 一个带有两个数据字段的简单结构,集合和游标,以及两个方法:Next()和HasNext()。 这次集合的Iterator()方法返回一个指向正确初始化迭代器结构的指针:

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

尽管我喜欢关闭,性能明智但它是一个禁忌。 至于设计模式,Gophers更喜欢“惯用的方式”这个词,这是有充分理由的。 另外grep the it source tree for iterators:如此少的文件提到名称,迭代器肯定不是Go的东西。

另请参阅此页面: http://ewencp.org/blog/golang-iterators/http://ewencp.org/blog/golang-iterators/

无论如何,接口在这里没有任何帮助,除非你想定义一些Iterable接口,但这是一个完全不同的主题。

一种选择是使用渠道。 通道在某种程度上类似于迭代器,您可以使用range关键字迭代它们。 但是当你发现你不能在没有泄漏goroutine的情况下突破这个循环时,使用会变得有限。

在go中创建迭代器模式的惯用方法是什么?

编辑

渠道的根本问题在于它们是推模型。 迭代器是拉模型。 你不必告诉iterator停止。 我正在寻找一种以一种很好的表达方式迭代集合的方法。 我还想链接迭代器(map,filter,fold alternative)。


TL; DR:迭代器在Go中不是惯用的。 将它们留给其他语言。

然后,维基百科条目“Iterator模式”开始,“在面向对象的编程中,迭代器模式是一种设计模式......”两个红色标志:首先,面向对象的编程概念通常不能很好地转化为Go第二,许多Go程序员对设计模式没有太多考虑。 第一段还包括“迭代器模式从容器中解耦算法”,但只是在声明“迭代器[访问]容器的元素之后。那么它是什么?如果算法正在访问容器的元素,那么它几乎不能声称是解耦的。许多语言中的答案涉及某种泛型,它允许语言对类似的数据结构进行推广.Go中的答案是接口。接口通过拒绝访问结构并要求所有交互都基于行为来强制执行更严格的算法和对象解耦行为意味着通过数据方法表达的能力。

对于最小迭代器类型,所需的功能是Next方法。 Go接口可以通过简单地指定此单个方法签名来表示迭代器对象。 如果希望容器类型可迭代,则必须通过实现接口的所有方法来满足迭代器接口。 (我们这里只有一个,实际上接口通常只有一个方法。)

最小的工作示例:

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/AFZzA7PRDRhttp://play.golang.org/p/AFZzA7PRDR

这是接口的基本思想,但迭代切片是荒谬的过度杀伤。 在许多情况下,您可以使用其他语言来获取迭代器,您可以使用内置语言原语编写Go代码,这些原语直接遍历基本类型。 您的代码保持清晰简洁。 如果这变得复杂,请考虑您真正需要的功能。 你需要在某些函数中从随机位置发出结果吗? 通道提供类似产量的功能,允许这样做。 您需要无限列表或懒惰评估吗? 闭包效果很好。 您是否有不同的数据类型,并且需要它们透明地支持相同的操作? 接口提供。 通道,函数和接口都是一流的对象,这些技术都很容易组合。 那么最惯用的方式是什么呢? 它是尝试不同的技术,熟悉它们,并以最简单的方式使用满足您需求的任何东西。 无论如何,面向对象意义上的迭代器几乎从不是最简单的。


这是我想用通道和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

我从Rob Pike的Go Concurrency Patterns谈起了这个想法。


通过为goroutines提供第二个控制消息通道,您可以在不泄漏的情况下突破。 在最简单的情况下,它只是一个chan bool 。 当你想要停止goroutine时,你发送这个频道。 在goroutine中,你把迭代器的通道发送到一个select中的控制通道上。

这是一个例子。

您可以通过允许不同的控制消息(例如“跳过”)来进一步实现此目的。

你的问题很抽象,所以说一个具体的例子会有所帮助。