LeetCode Concurrency Go 語言詳解：Fizz Buzz Multithreaded

本次將會示範 goroutine 教學中常講到的「不要透過共享來通訊，而要透過通訊來共享」。

前言：由於 LeetCode Concurrency(併發) 還沒有 Go 語言版本，我先自行用 Go 語言來解題。為了能在 LeetCode 以外的平台獲得討論，所以我打算逐漸把自己的解題思路寫下。

本題 LeetCode 連結：

https://leetcode.com/problems/fizz-buzz-multithreaded/

本題題目

給定一個數列從 1 ~ n，依序輸出，但是:

如果 n 可以被 3 整除，輸出 “fizz”
如果 n 可以被 5 整除，輸出 “buzz”
如果 n 同時可以被 3 與 5 整除，輸出 “fizzbuzz”

實作要求：使用 4 個執行緒實現一個多執行緒版本。一個 FizzBuzz 的 instance 要被傳遞到以下四個執行緒中:

Thread A 會呼叫 fizz() 以檢查 n 是否可以被 3 整除？若可以就輸出 fizz
Thread B 會呼叫 buzz() 以檢查 n 是否可以被 5 整除？若可以就輸出 buzz
Thread C 會呼叫 fizzbuzz() 以檢查 n 是否可以被 3, 5 整除？若可以就輸出 fizzbuzz
Thread D 會呼叫 number() 照常輸出原本數字 n

本題考核難點？判斷責任去中心化！

我一開始認為「這題沒什麼難的嘛～還不就那些套路再用一次！」，所以最早的實作版本，是寫了一個中心控管的 goroutine，判斷整除條件後，再把輸出任務透過 channel 發派給其他 goroutine A, B, C, D。

直到我為了分享這題，將英文題目翻譯為中文的時候，才發現自己誤解題目了(尷尬)！題目真正的要求更困難，要各個 goroutine 自行負擔檢查整除條件的責任。所以只好重寫 XD

在過去的 LeetCode Concurrency 詳解中，我提到過很多次：

goroutine 若不刻意控制，將無法保證執行的先後順序，因此本題就是要考核對 goroutine 順序控制的能力。

但前面幾題的解法，大多是把判斷責任中心化，方便控管順序。這次，與前面幾題不同的是，這一題要求把判斷責任分散到 thread A, B, C 中，所以每個 goroutine 也無法準確得知下一個要接棒的 goroutine 是哪一個？這樣的順序控制會由於分散化，變得更加困難。

By the way，我還解過「DiningPhilosophers」這一題用的就是去中心化方法，但目前還沒寫那一題詳解。

解法與思路：

1. 所用 Channel 型態與定位？

type FizzBuzz struct {
	n           int
	wg          *sync.WaitGroup
	streamBaton chan int
}

fizzbuzz := &FizzBuzz{
	n:           testCase,
	wg:          &sync.WaitGroup{},
	streamBaton: make(chan int, 1),
}

依照題目採用一個 FizzBuzz 物件 pass 到各個 goroutine 之中，當中有 buffered channel streamBaton 長度為一，可儲存一個整數。

2. 四個 goroutine 之間，如何交接棒？

這一題在 goroutine 之間交接棒的規則更複雜，所以我決定不像之前一樣指定的交接棒，而是每一個 goroutine 都把訊息丟到同一個 channel 裡面去，大家都去「各取所需」，看看是不是符合自己的整除規則？如果不是，表示自己還沒接到棒，要把數字再寫回 channel 讓應該接這一棒的 goroutine 可以讀取到資訊。

這樣有壞處，那就是會多很多次沒有命中的 channel 讀取，若不是自己要的還得把數值還回去。做個比喻，就像老闆雇用員工吧，因為不具備識人能力，都先雇用再說，不對再趕走。（只是比喻，如有雷同，純屬巧合）

受限於 channel 的性質，看了就會改變內容，所以若沒有命中就多了「還回去」的動作，無法如同 get 存取子一樣只讀不寫。

自循環 & 外部啟動注意事項

首先，這個循環是從 0 開始，沒有人交棒給 0，所以 main() 要自己丟。

1	fizzbuzz.streamBaton <- 0 //啟動交棒

再來，本題不像之前有清楚的交接棒順序，不預設哪一個 goroutine 會收尾，所以需要用 sync.WaitGroup 同步 4 個 goroutine 結束時間。

最後，由於最後一個 print 交出去的棒子沒 goroutine 接，所以要記得關閉通道，否則在交棒點會發生 deadlock。（你想知道後果的話，可以在下面原始碼自行把 close 這行註解掉看看）

1	close(fizzbuzz.streamBaton)

交接棒流程：PrintLoop() 視角

這一次採用去中心化的交棒決策，所以每一個 goroutine 的流程都是相同的，因此我將各自的「整除條件」PassCondition(i int)bool與「字串輸出」PrintString(i int)取出，以下列程式碼 PrintFizz() 為例：

func (this *FizzBuzz) PrintFizz() {
	PassCondition := func(i int) bool { return (0 == i%3) && (0 != i%5) }
	PrintString := func(i int) { fmt.Printf("Fizz(%d), ", i) }

	this.PrintLoop(PassCondition, PrintString)
}

其他的 PrintBuzz()、PrintFizzBuzz()、PrintNumber() 也都比照辦理。剩下都抽象為 PrintLoop() 以達到程式碼的 DRY，如下列程式碼：

func (this *FizzBuzz) PrintLoop(passCondition func(int) bool, printString func(int)) {
	defer this.wg.Done()

	for i := 0; i <= this.n; i++ {
		if passCondition(i) {
			nextNum := <-this.streamBaton //接棒
			if i == nextNum {
				printString(i)
				this.streamBaton <- i + 1 //交棒
			} else {
				this.streamBaton <- nextNum //把數字還回去
				i--
			}
			runtime.Gosched()
		}
	}
}

for loop 會獨自判斷 0~n 每一個數字是否滿足自己要輸出的條件？

若滿足，就去公共的 channel streamBaton 裡頭看看，有沒有剛好與 i 相同的數字？
- 若有，表示有某未知 goroutine 交棒給自己了，便可以輸出。輸出以後要交棒，只知道下一棒的數字會+1，但並不知道誰接棒？反正把棒子丟回去公共的 channel streamBaton 讓該接棒的自己接棒。
- 若無，表示這次讀取沒命中、表示自己還沒接到棒，要把數字再寫回 channel 讓應該接這一棒的 goroutine 可以讀取到這筆資訊。i-- 使 for loop 不會前進，繼續原地等待接棒。
動作完成後，要執行 runtime.Gosched()，使自己不會獨佔 CPU，令其他 goroutine 有機會可以動作。

3.「不要透過共享來通訊，而要透過通訊來共享」

過去幾次解題都用 unbuffered channel 的原因是，並沒有要共享什麼資料，就只要在 goroutine 之間交接棒，這個棒子上不需要帶其他訊息，因此 channel 用的也比較多，因為「交棒給誰？」的訊息用多個不同 topic 的 channel 區別。

這一次採用 buffered channel，是因為不只要交接棒了，還要透過一個 int 來指定下一個交接對象，這就是「透過通訊來共享」。

當我們要把一件事講清楚，除了講「應該是什麼」，最好也把「不應該是什麼」說明白，正反例都有更有助於建立清晰的認知。

那麼，要是我就故意反著做，硬要「透過共享來通訊」呢？很簡單，把 chan int 改成 int，其他部分做些相應修改就是了。兩個版本的程式碼都會放在下面的 The Go Playground 連結。

但是這兩種方法，在本題的執行結果卻完全相同！花費時間也沒有明顯差異。所以「透過通訊來共享」的優越性到底在哪裡？或許本題的要求不夠嚴苛，不足以展示出差異，而筆者自己也學藝不精，尚未參透。如果有讀者能說得清楚，歡迎在本文底下留言，筆者會非常感謝你。

完整解題程式碼：

「透過通訊來共享」版本（使用 chan int）:
https://play.golang.org/p/nHZtkI-pGs5

「透過共享來通訊」版本（使用 int）:
https://play.golang.org/p/92wshFYlPG3

LKY 只有原創內容的 Blog