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

  • 2020 年 2 月 20 日
  • 笔记

这是我写的第三题 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:

同一个 instance ZeroEvenOdd 会被传到三个 thread 里面:

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.

Thread A 将会呼叫 zero() 并且只会输出 0 Thread B 将会呼叫 even() 并且只会输出偶数 Thread C 将会呼叫 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.

每一个 thread 都会被传入一个 printNumber() 以输出一个整数。修改已给的代码，使其输出序列为 010203040506…，该序列长度必须为 2n。

完整中文说明如下：

假设有这么一个类：

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 型态与定位？

本题采用五个 unbuffered 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{}),  }

定位分别是:

  • streamEvenToZero: Even() 交棒给 Zero()
  • streamOddToZero: Odd() 交棒给 Zero()
  • streamZeroToEven: Zero() 交棒给 Even()
  • streamZeroToOdd: Zero() 交棒给 Odd()
  • streamZeroToEnd: Zero() 交棒给启动它的 goroutine

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

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

以前的文章说过，由于本题解法采用各个 goroutine 彼此循环交棒的方式，因此不能自行启动，需要外界给讯号，所以在包住一整题的 PrintZeroEvenOdd() 执行各个 goroutine 同时以 zeo.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() 做控管中心，遍历 0 to n 每一个数字，印完自己责任该印的 "0" 以后，根据数字性质决定要把棒子交给 Even() 或 Odd()。此处会用到 select-case-default。具体代码如下：

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() 交棒（send to chan）以后，就会在 for-select 里无穷回圈，每一次 select{} 都会随机选择一个 case 或 default，也就是以乱枪打鸟的方式 polling 是谁交棒给自己？

谜之声：“难道有不是中心化的流程吗？”，有喔！我解决“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() 其中一个，都有可能是最后印出字元的 goroutine，若让这两者去收尾，流程上的不确定性比较大。因此，几经考虑后，还是决定让 Zero() 去收尾。

让 Zero() 去收尾的套路，之前的详解也写过，就是先 return 的 goroutine 最后都要 send to chan 到负责收尾的 goroutine，收尾 goroutine 在最后一一将这些 chan 都 receive 掉。

但由于本题特性，可由题目给定数字的奇偶判断，Zero() 会从哪个 channnel 收到收尾讯号？因此在 Zero() 最后段的 receive，是以奇偶数判断要在何处等待。具体的局部代码如下：

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

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

主程式为了等待 goroutine 都结束才往下的同步情况，往往会用 sync.WaitGroup.Wait()。根据本文前面所介绍，我已经将流程结束的不确定性减少，使得一定会由 Zero() 负责收尾，因此只要在主程式阻塞一个 chan receive，由 Zero() 结束前 send 一下，便可以将主程式打通，继续往下。

具体的局部代码如下：

goroutine Zero() 结束前 send 一下，交棒出去。

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

在主程式启动完其他 goroutine 之后，阻塞一个 chan receive，等待被 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

示意图：

VirMach 便宜 VPS

QNews

QNews