数据结构和几个的基本API

package Bag

type Bag struct {
	first *node
	n     int
}

type node struct {
	item interface{}
	next *node
}

func NewBag() Bag {
	return Bag{}
}

func (b Bag) IsEmpty() bool {
	return b.n == 0
}

func (b Bag) Size() int {
	return b.n
}

func (b *Bag) Add(item interface{}) {
	oldfirst := b.first
	b.first = &node{}
	b.first.item = item
	b.first.next = oldfirst
	b.n++
}

简单的背包迭代接口

由于go语言没有提供原生的迭代接口支持，所以想使用迭代就需要自己实现，恰巧迭代是背包这个数据结构的重要方法。以下是一个简单的迭代实现：

//导出背包中的全部元素为切片
func (b Bag) Iterator() []interface{} {
	s := []interface{}{}
	p := b.first
	for i := 0; i < b.n; i++ {
		s = append(s, p.item)
		p = p.next
	}
	return s
}

这种简单的迭代实现原理是遍历链表，将其中所有的元素都导出为一个切片，然后返回，这样就可以通过go的for range迭代元素。
该方案会在迭代开始时将背包中的所有数据在内存中复制一份，这样做实现起来简单、迭代的速度很快，但是生成切片需要时间并且会占用双倍的内存，不适合数据量较大的情况。

改进后的迭代器

这一版迭代器的设计思路：在背包类中存储一个变量index，用来记录当前迭代到达的位置。

type Bag struct {
	first *node
	n     int
	index *node
}

//省略中间的方法

//初始化迭代器
func (b *Bag) InitIterator() {
	b.index = b.first
}

//检查下一个元素
func (b Bag) HasNext() bool {
	return b.index != nil
}

//获取下一个元素
func (b *Bag) Next() interface{} {
	item := b.index.item
	b.index = b.index.next
	return item
}

下面是测试迭代器的代码：

func main() {
	b := Bag.NewBag()
	b.Add(1)
	b.Add(2)
	b.Add(3)
	for b.InitIterator(); b.HasNext(); {
		fmt.Println(b.Next())
	}
}

控制台输出：

[Running] go run "/Users/bbfat/Desktop/Learn/数据结构/背包/main.go"
3
2
1

[Done] exited with code=0 in 0.231 seconds

这种迭代方式在时间效率和空间效率上表现良好，但是每次想在某个类中实现迭代功能都需要定义这三个接口，抽象成都不高。

运用协程和接口实现抽象迭代器类

go语言的一大特色就是并发性，这得益于它的协程机制，我现在就来使用协程和通道构建一个迭代器类。

package Iterator

// 协程迭代接口
// 可迭代对象需实现StartIterate方法，要求如下：
// 该方法在迭代完成前通过通道持续返回数据
// 返回nil代表迭代完成
type IteratorObj interface {
	StartIterate(ch chan interface{})
}

type Iterator struct {
	it IteratorObj
	ch chan interface{}
}

//创建一个Iterator对象
func InitIterator(it IteratorObj) Iterator {
	ch := make(chan interface{})
	go it.StartIterate(ch)
	return Iterator{it, ch}
}

//迭代时接收协程发来的数据并返回
func (it Iterator) Next() interface{} {
	return <-it.ch
}

StartIterate 接口方法

可迭代类需要实现这个接口才能用Iterator进行迭代，这个接口方法将作为一个协程启动，可迭代类运用自身的逻辑进行迭代，将每次迭代的结果传入无缓冲通道ch。

InitIterator 函数

此函数接收一个IteratorObj接口类型作为参数，创建一个接口类型通道，然后启动协程，返回一个Iterator对象。

Next 方法

此方法作用在Iterator对象上，该方法负责接收ch通道传回的数据并返回。

背包实现IteratorObj接口

在Bag类下面增加一个方法

//实现迭代类接口
func (b Bag) StartIterate(ch chan interface{}) {
	index := b.first
	for {
		if index == nil {
			ch <- nil
			break
		} else {
			ch <- index.item
			index = index.next
		}
	}
}

就是普通的链表遍历，在其中增加了通道传输数据。

通过背包测试协程迭代

func main() {
	b := Bag.NewBag()
	for i := 0; i < 100; i++ {
		b.Add(i)
	}

    //以下为迭代的具体使用方法
	it := Iterator.InitIterator(b)
	for v := it.Next(); v != nil; v = it.Next() {
		fmt.Println(v)
	}
}

测试输出：

[Running] go run "/Users/bbfat/Desktop/Learn/数据结构/背包/main.go"
99
98
//中间省略
1
0

[Done] exited with code=0 in 0.26 seconds

测试成功！

测试比较不同迭代方式的性能差异

1.生成切片法

func main() {
	b := Bag.NewBag()
	for i := 0; i < 10000000; i++ {
		b.Add(i)
	}
	for _, i := range b.Iterator() {
		fmt.Print(i)
	}
}
测试编号用时(s)
13.091
22.606
32.486
42.478
52.538
63.031
平均2.075

2.直接迭代法

func main() {
	b := Bag.NewBag()
	for i := 0; i < 10000000; i++ {
		b.Add(i)
	}
	for b.InitIterator(); b.HasNext(); {
		fmt.Print(b.Next())
	}
}
测试编号用时(s)
11.183
21.131
31.426
41.584
51.139
61.085
平均1.258

3.协程迭代法

func main() {
	b := Bag.NewBag()
	for i := 0; i < 10000000; i++ {
		b.Add(i)
	}
	it := Iterator.InitIterator(b)
	for v := it.Next(); v != nil; v = it.Next() {
		fmt.Print(v)
	}
}
测试编号用时(s)
11.154
21.555
31.491
41.541
51.526
61.544
平均1.468

综述

生成切片的迭代方法不是一个好的选择，它不光占用内存大，而且消耗时间也长，直接迭代法效率最高，但是实现起来比较麻烦，协程迭代法效率和直接迭代仅差一点点，但是实现起来非常舒适，所以我的选择是使用协程迭代法，这也是go这门语言的魅力所在。

协程迭代法的改进

当前的协程迭代方法有一个缺陷——无法优雅地退出协程，如果迭代进行到一半无法强制结束，负责迭代的协程会一直在堆栈中保持阻塞状态，这非常不爽，接下来我就尝试改进这个问题。

给IteratorObj升级

type IteratorObj interface {
	StartIterate(ch chan interface{}, stop chan bool)
}

增加了一个可以控制协程终止的通道，所以背包类的接口实现也需要进行调整：

//实现迭代类接口
func (b Bag) StartIterate(ch chan interface{}, stop chan bool) {
	index := b.first
	for {
		select {
		case <-stop:
			return
		default:
			if index == nil {
				ch <- nil
				return
			} else {
				ch <- index.item
				index = index.next
			}
		}
	}
}

select语句

这是go语言为了更好地支持协程的特有的语句，它类似常见的switch，但是每个case后必须是通信相关的表达式，go的switch于其他语言一个不同点就是自带break，select也是一样。
当收到stop通道传来的消息的时候函数返回，协程优雅退出，其他情况下继续执行之前的迭代逻辑。

Finish函数

此函数用于向迭代协程发出退出信号。

//停止迭代协程
func (it Iterator) Finish() {
	mutex := sync.Mutex{}
	mutex.Lock()
	<-it.ch
	it.stop <- true
	mutex.Unlock()
}

这其中使用了互斥锁，它可以保证在Lock()和Unlock()之间的代码不会被其他协程中断。
这样我们先上锁，然后拿出ch通道阻塞的数据，再将信号发送等到stop通道，最后解锁，让迭代协程继续执行，此时迭代协程就会监测到stop通道传来的信号，这样它就会执行return退出。

测试

func main() {
	b := Bag.NewBag()
	for i := 0; i < 10; i++ {
		b.Add(i)
	}
	it := Iterator.InitIterator(b)
	for v := it.Next(); v != nil; v = it.Next() {
		fmt.Print(v)
		if v.(int) == 5 {
			it.Finish()
			return
		}
	}
}

控制台输出：

API server listening at: 127.0.0.1:6347
98765

测试成功！