面试题实战：给一个数 n，使用 Go 打印交替顺序零与奇偶数

这是我写的第三题 LeetCode Concurrency(并发) Go 语言详解，技术比前面两题都要复杂。为了解释到我自认够清楚，写的时间多花了好几倍（1x = 2hr）。

本题 LeetCode 链接：

https://leetcode.com/problems/print-zero-even-odd/

本题题目

The same instance of ZeroEvenOdd will be passed to three different threads:

ZeroEvenOdd

Thread A will call zero() which should only output 0's. Thread B will call even() which should only ouput even numbers. Thread C will call odd() which should only output odd numbers.

zero()even()odd()

Each of the threads is given a printNumber method to output an integer. Modify the given program to output the series 010203040506... where the length of the series must be 2n.

printNumber()

完整中文说明如下：

假设有这么一个类：

class ZeroEvenOdd {
  public ZeroEvenOdd(int n) { ... }      // 构造函数
  public void zero(printNumber) { ... }  // 仅打印出 0
  public void even(printNumber) { ... }  // 仅打印出 偶数
  public void odd(printNumber) { ... }   // 仅打印出 奇数
}

相同的一个 ZeroEvenOdd 类实例将会传递给三个不同的线程：

1. 线程 A 将调用 zero()，它只输出 0 。
2. 线程 B 将调用 even()，它只输出偶数。
3. 线程 C 将调用 odd()，它只输出奇数。

每个线程都有一个 printNumber 方法来输出一个整数。请修改给出的代码以输出整数序列 010203040506... ，其中序列的长度必须为 2n。

示例 1：

输入：n = 2
输出："0102"
说明：三条线程异步执行，其中一个调用 zero()，另一个线程调用 even()，最后一个线程调用odd()。正确的输出为 "0102"。

示例 2：

输入：n = 5
输出："0102030405"

本题考核难点？

在一个未知长度的序列中，依照“0-奇数-0-偶数”的顺序将数字印出，且一种元素只能由一个执行绪印出，代表各个执行绪之间要依照这个数列的规则沟通。

goroutine 若不刻意控制，将无法保证执行的先后顺序，因此本题就是要考核对 goroutine 顺序控制的能力。

与前面几题不同的是，这一题最后工作的 thread 具有不确定性，视数列最后一个元素为奇数或偶数来决定，这点小小的提高了难度。

解法与思路：

1. 所用 Channel 型态与定位？

ZeroEvenOdd

type ZeroEvenOdd struct {
	n                int
	streamEvenToZero chan struct{}
	streamOddToZero  chan struct{}
	streamZeroToEven chan struct{}
	streamZeroToOdd  chan struct{}
	streamZeroToEnd  chan struct{}
}

var zeo = &ZeroEvenOdd{
	n:                testNum,
	streamEvenToZero: make(chan struct{}),
	streamOddToZero:  make(chan struct{}),
	streamZeroToEven: make(chan struct{}),
	streamZeroToOdd:  make(chan struct{}),
	streamZeroToEnd:  make(chan struct{}),
}

定位分别是:

streamEvenToZeroEven()Zero()streamOddToZeroOdd()Zero()streamZeroToEvenZero()Even()streamZeroToOddZero()Odd()streamZeroToEndZero()

2. 五个 goroutine 之间，如何交接棒？

自循环 & 外部启动注意事项

PrintZeroEvenOdd()goroutinezeo.streamEvenToZero <- struct{}{}main()Even()Zero()

go func() { zeo.streamEvenToZero <- struct{}{} }() //给起头的火种
go zeo.Zero(PrintNumber)
go zeo.Even(PrintNumber)
go zeo.Odd(PrintNumber)

要特别注意的是，这个“启动火种”也要写成 goroutine，否则会由于执行当下尚未等到消费者“出世”，发生 deadlock！

另外一种不用 goroutine 启动的做法，也可以让消费者先“出世”，在 goroutine 的阻塞中等待时，再给“启动火种”。具体代码如下：

go zeo.Zero(PrintNumber)
go zeo.Even(PrintNumber)
go zeo.Odd(PrintNumber)
func() { zeo.streamEvenToZero <- struct{}{} }() //给起头的火种

交接棒流程：Zero() 视角

Zero()Even()Odd()

func (this *ZeroEvenOdd) Zero(printNumber func(int)) {
	for i := 0; i < this.n; i++ {
		select {
		case <-this.streamOddToZero:
			printNumber(0)
			this.streamZeroToEven <- struct{}{}
		case <-this.streamEvenToZero:
			printNumber(0)
			this.streamZeroToOdd <- struct{}{}
		default:
			runtime.Gosched()
			//<-time.After(time.Microsecond)
			i--
		}
	}

	if 0 == this.n%2 {
		<-this.streamEvenToZero //等待 Even() 结束，自己再结束
	} else {
		<-this.streamOddToZero //等待 Odd() 结束，自己再结束
	}
}

Zero()Zero()

谜之声：“难道有不是中心化的流程吗？”，有喔！我解决“DiningPhilosophers”这一题用的就是去中心化方法，但目前还没写那一题详解。

交接棒流程：Even() & Odd() 视角

Even()Odd()Zero()Zero()

唯一比较复杂的部分，就是数字“递增”与“终点”的控制：

• “递增”每一次都是 += 2，不必解释。
• “终点”一开始就算好题目下的奇数上限、偶数上限，算法看代码也很清楚了，不解释。超过终点就直接结束。

Even()

func (this *ZeroEvenOdd) Even(printNumber func(int)) {
	evenUpper := this.n - this.n%2
	// fmt.Println("evenUpper:", evenUpper)
	for i := 2; i <= evenUpper; {
		<-this.streamZeroToEven
		printNumber(i)
		i += 2
		this.streamEvenToZero <- struct{}{}
	}
}

Zero()

Even()Odd()Zero()

Zero()

Zero()Zero()

if 0 == this.n%2 {
	<-this.streamEvenToZero //等待 Even() 结束，自己再结束
} else {
	<-this.streamOddToZero //等待 Odd() 结束，自己再结束
}

收尾之二：代替 sync.WaitGroup.Wait() 的“chan receive 阻塞法”

sync.WaitGroup.Wait()Zero()Zero()

具体的局部代码如下：

Zero()

func (this *ZeroEvenOdd) Zero(printNumber func(int)) {
	//.....略过多行
	this.streamZeroToEnd <- struct{}{}
}

Zero()

go zeo.Zero(PrintNumber)
go zeo.Even(PrintNumber)
go zeo.Odd(PrintNumber)
<-zeo.streamZeroToEnd //等待 Zero() 送出结束讯号

完整解题代码：

// LeetCode in Coucurrency：Print Zero Even Odd
// Solution by unbuffered chan, without time delay.

package main

import (
	"fmt"
	"runtime"
)

type ZeroEvenOdd struct {
	n                int
	streamEvenToZero chan struct{}
	streamOddToZero  chan struct{}
	streamZeroToEven chan struct{}
	streamZeroToOdd  chan struct{}
	streamZeroToEnd  chan struct{}
}

func (this *ZeroEvenOdd) Zero(printNumber func(int)) {
	for i := 0; i < this.n; i++ {
		select {
		case <-this.streamOddToZero:
			printNumber(0)
			this.streamZeroToEven <- struct{}{}
		case <-this.streamEvenToZero:
			printNumber(0)
			this.streamZeroToOdd <- struct{}{}
		default:
			runtime.Gosched()
			//<-time.After(time.Microsecond)
			i--
		}
	}

	if 0 == this.n%2 {
		<-this.streamEvenToZero //等待 Even() 結束，自己再結束
	} else {
		<-this.streamOddToZero //等待 Odd() 結束，自己再結束
	}

	this.streamZeroToEnd <- struct{}{}
}

func (this *ZeroEvenOdd) Even(printNumber func(int)) {
	evenUpper := this.n - this.n%2
	// fmt.Println("evenUpper:", evenUpper)
	for i := 2; i <= evenUpper; {
		<-this.streamZeroToEven
		printNumber(i)
		i += 2
		this.streamEvenToZero <- struct{}{}
	}
}

func (this *ZeroEvenOdd) Odd(printNumber func(int)) {
	oddUpper := ((this.n + 1) - (this.n+1)%2) - 1
	for i := 1; i <= oddUpper; i += 2 {
		<-this.streamZeroToOdd
		printNumber(i)
		this.streamOddToZero <- struct{}{}
	}
}

func PrintNumber(x int) {
	fmt.Printf("%d", x)
}

func main() {
	var PrintZeroEvenOdd = func(testNum int) {
		var zeo = &ZeroEvenOdd{
			n:                testNum,
			streamEvenToZero: make(chan struct{}),
			streamOddToZero:  make(chan struct{}),
			streamZeroToEven: make(chan struct{}),
			streamZeroToOdd:  make(chan struct{}),
			streamZeroToEnd:  make(chan struct{}),
		}

		go func() { zeo.streamEvenToZero <- struct{}{} }() //給起頭的火種
		go zeo.Zero(PrintNumber)
		go zeo.Even(PrintNumber)
		go zeo.Odd(PrintNumber)
		<-zeo.streamZeroToEnd //等待 Zero() 送出結束訊號
		fmt.Println()
	}

	for testNum := range [14]int{} {
		fmt.Printf("Case %2d: ", testNum)
		PrintZeroEvenOdd(testNum)
	}
}

https://play.golang.org/p/K5ZpQsHxlfN

示意图：