在Go中,创建迭代器模式的惯用方式是什么?
编辑: 通道的根本问题在于它们是推模型(push model)而不是拉模型(pull model)。迭代器是拉模型。您不必告诉迭代器停止。我正在寻找一种以简洁明了的方式遍历集合的方法。我还希望能够链接迭代器(map,filter,fold替代方案)。
频道很有用,但闭包通常更合适。
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以通用方式定义,将任何整数函数映射到整数生成器。其他函数,如filter和fold,也可以类似地定义。
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
}
TL;DR: 忘记闭包和通道,它们太慢了。如果您的集合中的各个元素可以通过索引访问,则选择经典的C迭代数组类型。如果不能,实现一个有状态的迭代器。
我需要遍历一些集合类型,其确切的存储实现尚未确定。这以及其他无数原因使我必须将实现细节与客户端抽象分离,因此我进行了各种遍历方法的测试。完整代码在此, 包括一些使用错误作为值的实现。以下是基准测试结果:
classic C iteration over an array-like structure. The type provides the methods ValueAt() and Len():
l := Len(collection)
for i := 0; i < l; i++ { value := collection.ValueAt(i) }
// benchmark result: 2492641 ns/op
Closure style iterator. The collection's Iterator method returns a next() function (a closure over the collection and cursor) and a hasNext boolean. next() returns the next value and a hasNext boolean. Note that this runs much faster than using separate next() and hasNext() closures returning single values:
for next, hasNext := collection.Iterator(); hasNext; {
value, hasNext = next()
}
// benchmark result: 7966233 ns/op !!!
Stateful iterator. A simple struct with two data fields, the collection and a cursor, and two methods: Next() and HasNext(). This time the Iterator() method of the collection returns a pointer to a properly initialized iterator structure:
for iter := collection.Iterator(); iter.HasNext(); {
value := iter.Next()
}
// benchmark result: 4010607 ns/op
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 代码,而不是像其他语言中那样使用迭代器。您的代码保持清晰简洁。如果出现复杂情况,请考虑您真正需要哪些功能。您是否需要从某个函数的随机位置发射结果?通道提供了类似 yield 的功能,允许这样做。您是否需要无限列表或惰性求值?闭包非常适用。您是否有不同的数据类型,需要它们透明地支持相同的操作?接口提供了解决方案。由于通道、函数和接口都是第一类对象,因此这些技术都很容易组合使用。那么什么是最符合习惯用法的方式呢?尝试使用不同的技术,熟悉它们,并尽可能以最简单的方式满足您的需求。迭代器在面向对象的意义上几乎从未是最简单的。
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() {
defer close(c)
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]
}
}
}()
return c
}
我从Rob Pike的Go并发模式演讲中得到了灵感。
从container/list包中看,似乎没有办法实现这一点。如果您要迭代对象,则应使用类C的方式。
像这样:
type Foo struct {
...
}
func (f *Foo) Next() int {
...
}
foo := Foo(10)
for f := foo.Next(); f >= 0; f = foo.Next() {
...
}
chan bool
。当你想要停止goroutine时,你发送到这个通道。在goroutine内部,你将迭代器的通道发送和控制通道的监听放入select中。
这里是一个例子。
你可以进一步允许不同的控制消息,例如“跳过”。close
是一个持续发送的操作。 - Dustin我在这个主题上发表了一篇文章:
有一个相关的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)
}
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)
}
在 agilemde.co.uk/libraries.zip 中有一个 ocliterator.go 的实现,以及其他标准库组件的 Go 版本,如日期和随机数。该迭代器提供类似 Java 集合迭代器和 JavaScript generator 函数迭代器的功能。(注意,该迭代器依赖于 ocl.go 通用库)。
如果您不需要并发,请不要使用通道。它们被创建用于组织并发流程。除非您正在尝试实现线程安全的迭代器,否则其速度比任何简单实现慢10到100倍。更多详细信息请查看Go通道是如何实现的?。
我不知道惯用的方式,只想分享一些您可以遵循的想法。
可能您最喜欢的GitHub集合库已经有了一些迭代它们的方法。
以及您的应用程序可能已经具有函数式风格的Iterator
接口,例如hasNext, next := list.Iter()
。
最好只需遵循您已经拥有的代码风格。可读性和一致性是您的朋友。
就性能而言,如果您将任何重要的工作单元放在循环内部,结果将是相同的。
当您真正需要时,for循环
当然会给您更好的性能。
for循环
,遵循代码风格,并重复使用已有的抽象。我选择函数式风格来编写我的小型库,因为我没有依赖或风格限制,希望保持一切简单和美好。