Golang Iterator 設計與實現
【導讀】go 語言實現迭代器模式有什麼思路？本文介紹了 4 種迭代器實現。
在學習《算法》這本書時，第一章有一個 Bag 的數據結構，它定義爲不能刪除元素的集合。之前看到一篇文章，說數據結構底層結構其實只有數組與鏈表，所以在實現 Bag 時想使用數組和鏈表分別實現。
但是在設計 Bag API 時發現，該如何提供一個通用的遍歷方式給第三方調用？因爲不像 Java，Golang 並未提供一個迭代接口，只是原生語法上支持對一些容器的遍歷，如下所示：
// 如果 container 是數組或者 Slice，那麼 k => index，v => 數組元素；
// 如果 container 是 Map，那麼 k => key，v => value；
for k, v := range container {
}
// 對於 channel 也是使用 range 方式，但是返回值不同
for item := range channel {
}所以對於自定義結構，需要設計一個通用的 API 進行遍歷，即 Iterator 模式。對於 Golang 來實現一些數據結構，Iterator 模式是比較重要的。
這裏先設定 Bag 兩種不同底層存儲結構的定義：
// 使用數組做底層存儲
type arrBag struct {
data []interface{}
size int
}
// 使用鏈表做底層存儲
type node struct {
data interface{}
next *node
}
type linkBag struct {
node *node
size int
}在參考了幾篇博主的文章後，基於自身理解想到以下幾種實現方式。
模式 1：回調機制
定義一個 Iterable 接口，如下：
// if need to break, return error
type IterableCallback func(interface{}) error
type Iterable interface {
Iterator(IterableCallback)
}然後在對象中實現對應的 Iterator() 方法，改方法接受 callback 函數作爲參數，默認會把 Bag 的每個數據迭代然後作爲 callbak 參數傳入，如果 callback 返回 error，那麼就會中斷迭代。
// Array Bag
func (b *arrBag) Iterator(cb IterableCallback) {
var err error
for i := 0; i < len(b.data); i++ { // b.data => []interface{}
if err = cb(b.data[i]); err != nil {
break
}
}
}
// Link Bag
func (b *linkBag) Iterator(cb IterableCallback) {
var err error
for item := b.first; item != nil; item = item.next {
if err = cb(item); err != nil {
break
}
}
}那麼對於調用方來說，把對迭代操作通過 callback 函數傳遞過來即可。
b := NewBag()
// case 1: find a item
var found interface{}
b.Iterator(func(item interface{}) error {
if item == matched {
found = item
return errors.New("iterator break")
}
return nil
})
// case 2: sum
var sum int
b.Iterator(func(i interface{}) error {
item := i.(int)
sum += item
return nil
})這種實現方式簡單明瞭，很好的利用 Golang 的函數編程特性，但有一個不好的點是需預先定義好函數類型以及參數類型，不太好擴展。不過整體看這個無傷大雅，畢竟大部分情況是可以滿足的。
模式 2：閉包
類似 Python 或 JavaScript 的 generator 方式，使用閉包來控制迭代進度。
// For Array underlying implementation
func (b *arrBag) Iterator() (func() (interface{}, bool), bool) {
index := 0
var item interface{}
return func() (interface{}, bool) {
if index < a.size {
item = a.data[index]
index++
} else {
item = nil
}
return item, index < a.size
}, index < a.size
}
// For Link underlying implementation
func (b *linkBag) Iterator() (func() (interface{}, bool), bool) {
item := b.node
return func() (interface{}, bool) {
current := item
if current != nil {
item = current.next
}
return current, item != nil
}, item != nil && item.next != nil
}使用示例：
it, hasNext := a.Iterator()
for hasNext {
item, hasNext = it()
fmt.Printf("%v\n", item)
}模式 3：使用 chan
從開頭我們知道，除了 slice 和 map 的 for-range 形式外，Golang 也提供對 channel 的 for-range 語句操作。根據此特性，也可以通過 channel 來實現迭代。
首先定義一個通用的 interface：
type ChanIterable interface {
Chan(context.Context) chan interface{}
}這裏的 context 主要是爲了控制終止迭代，也可以使用特定的 chan，譬如 stop := make(chan struct{})，把 stop 傳入。雖然 Golang 推薦使用 context 作爲 API 設計的第一個參數，但是這裏感覺其實使用 chan 更好，因爲調用者會有意識的做 close(chan) 動作，而對於 context，估計會漏掉 cancel context 操作。
方法定義：
// For Array underlying implementation
func (b *arrBag) Chan(ctx context.Context) <-chan interface{} {
buf := make(chan interface{})
go func() {
defer close(buf)
for _, item := range b.data {
select {
case <-ctx.Done():
return
default:
buf <- item
}
}
}()
return buf
}
// For Link underlying implementation
func (b *linkBag) Chan(ctx context.Context) <-chan interface{} {
buf := make(chan interface{})
node := b.node
go func() {
defer close(buf)
for node != nil {
select {
case <-ctx.Done():
return
default:
buf <- node.data
node = node.next
}
}
}()
return buf
}那麼使用上，可以這樣：
ctx, cancel := context.WithCancel(context.Background())
// defer cancel() // 如果需要遍歷所有，可以把 cancel() 放到 defer 處
for item := range ab.Chan(ctx) {
if item == matched {
cancel() // 保證中斷遍歷，資源回收
return
}
}這裏的實現是無緩衝的 chan，爲了提高性能，也可以使用有緩衝。但是對於有緩衝的 chan，我們在控制內部 close 後需要消費掉緩衝區內的數據，否則依然有內存浪費。所以對於有緩衝，雖然性能提升（做了 benchmark，可以看到性能提升的不高），但需要多餘的循環，同時不好控制何時結束，所以這裏不建議使用有緩衝 channel。
模式 4：有狀態的遍歷
有狀態其實是參考 Java 這種面向對象模式設計，創建一個單獨指向源數據區的指針，並且記錄遍歷的進度。
type IteratorObj interface {
HasNext() bool
Next() interface{}
}然後，定義一個 Iterable 接口，對於對象就需要實現此接口，它會生成一個新的對象。使用上，每次需要遍歷時，都需要創建一個新的 IteratorObj。
type Iterable interface {
GenIterator() IteratorObj
}代碼示例如下：
// 底層採用數組存儲數據
type objArrayIterator struct {
index int
data []interface{}
}
func (b *arrBag) GenIterator() iterable.IteratorObj {
return &objArrayIterator{
index: 0,
data: b.data,
}
}
func (it *objArrayIterator) HasNext() bool {
return it.index < len(it.data)
}
func (it *objArrayIterator) Next() interface{} {
var result interface{}
if it.index < len(it.data) {
result = it.data[it.index]
it.index++
}
return result
}
// 底層採用鏈表存儲數據
type objLinkIterator struct {
iNode *node
}
func (b *linkBag) GenIterator() iterable.IteratorObj {
return &objLinkIterator{
iNode: b.first,
}
}
func (it *objLinkIterator) HasNext() bool {
return it.iNode != nil
}
func (it *objLinkIterator) Next() interface{} {
result := it.iNode
if it.iNode != nil {
it.iNode = it.iNode.next
}
return result
}使用示例如下：
ab := newArrBag(10)
it := ab.GenIterator()
for it.HasNext() {
fmt.Printf("%v\t", it.Next())
}這種方式實現相對前三種有點囉嗦，不過從 Java 這類編程語言過來的同學可能會感覺比較熟悉。
總結
從最初的目的：實現統一的 iterator API 來看，以上四種實現方式從 API 設計上都無可挑剔。
在參考的幾篇文章裏，有些實現方法都有一個通用問題，就是該如何保證中斷遍歷時能很好的回收資源，譬如使用 chan 模式的時候，內部實現改如何在最後 close 掉。但在上面實現的幾種模式裏，都保證最後能資源回收，不會出現此類問題。
最後通過 Golang 的 benchmark 來對比四種實現方式哪種更優。
# go test -benchmem -bench ^Benchmark -run ^$
BenchmarkIterateBag_Callback_Array-8 429 2500652 ns/op 0 B/op 0 allocs/op
BenchmarkIterateBag_Callback_Link-8 375 3479282 ns/op 0 B/op 0 allocs/op
BenchmarkIterateBag_Channel_Array-8 6 220628550 ns/op 176 B/op 1 allocs/op
BenchmarkIterateBag_Channel_Link-8 5 207023700 ns/op 200 B/op 2 allocs/op
BenchmarkIterateBag_Closure_Array-8 243 4789662 ns/op 56 B/op 3 allocs/op
BenchmarkIterateBag_Closure_Link-8 351 3945431 ns/op 24 B/op 2 allocs/op
BenchmarkIterateBag_Objective_Array-8 278 4335142 ns/op 32 B/op 1 allocs/op
BenchmarkIterateBag_Objective_Link-8 240 4364060 ns/op 8 B/op 1 allocs/op從性能上看，使用 callback 方式更優，且沒有額外的內存分配，並且 interface 設計更爲簡單、優雅。
對於使用 chan 性能更差，覺得主要原因是雖然只有兩個 goroutine 存在，但是對於 chan 的分配以及 goroutine 調度，對性能還是有點影響。
轉自：
segmentfault.com/a/1190000022293531
Go 開發大全
參與維護一個非常全面的 Go 開源技術資源庫。日常分享 Go, 雲原生、k8s、Docker 和微服務方面的技術文章和行業動態。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/R_7eN-moXiLVHAECPxwKXA