Golang Daisy-chain分析

在學習 go 并發的過程中,意外看到了菊花鏈的代碼,一開始基本上對于整體流程摸不著頭腦,經過查閱資料和自己苦思,最終找到了兩個關鍵點,捋清了整個執行過程

代碼:

func TestFunc5(t *testing.T) {/* *  利用信道菊花鏈篩法求某一個整數范圍的素數 *  篩法求素數的基本思想是:把從1開始的、某一范圍內的正整數從小到大順序排列, *  1不是素數,首先把它篩掉。剩下的數中選擇最小的數是素數,然后去掉它的倍數。 *  依次類推,直到篩子為空時結束 */const max = 100  // 找出100以內的所有素數nums := xrange() // 初始化一個整數生成器number := <-nums // 從生成器中抓一個整數(2), 作為初始化整數for number <= max { // number作為篩子,當篩子超過max的時候結束篩選fmt.Println(number)         // 打印素數, 篩子即一個素數nums = filter(nums, number) //篩掉number的倍數number = <-nums // 更新篩子}}func filter(in chan int, number int) chan int {// 輸入一個整數隊列,篩出是number倍數的, 不是number的倍數的放入輸出隊列// in:  輸入隊列out := make(chan int)go func() {for {i := <-in // 從輸入中取一個if i%number != 0 {out <- i // 放入輸出信道}}}()return out}func xrange() chan int { // 從2開始自增的整數生成器var ch chan int = make(chan int)go func() { // 開出一個goroutinefor i := 2; ; i++ {ch <- i // 直到信道索要數據,才把i添加進信道}}()return ch}

代碼是從網絡上復制,然后放在本地測試文件中進行調試的,自己運行的話可以把 TestFunc 改成 main

對于菊花鏈的代碼,從邏輯上來說并不復雜:

• 采用的是埃式篩,將 2-n 的整數按照從小到大的順序排列,以 2 為開始的素數,3/2 不能整除是素數,5/2 且 5/3 不能整除是素數,以此類推,不斷從小到大除以已經得出的素數,都不能整除,意味著它沒有可因式分解的余地,也就是素數;代碼也有改進的空間,即使用歐式篩,去除不必要的篩選(這個我還沒研究,感興趣的可以自己看看);

對于菊花鏈,對我個人而言,最關鍵的兩個點在于:

1. filter 中所有的 goroutine 都是一直存在的;
2. filter 中不斷建立 out,而 out 又通過 return 返回給 nums,nums 再通過 filter 傳參給 in;最終效果也就是每個 goroutine 中都建立了一個新的 channel,而這個 channel 都會依次傳遞給下一個 goroutine,也就是第一個的 out 第二個 in 接收,第二個的第三個接收等等,等到所有的 goroutine 依次執行完后,最后一個 goroutine 才會獲取到真正想要的那個 out,然后返回給 nums;

下面即是我捋出來的整個執行過程:

1. 通過 xrange 初始化一個 channel nums,接下來依次接收 從 2 開始不斷自增 1 的整數,將作為被篩選的數;
2. number 初始化中 nums 中獲取 2;
3. 開始循環篩選 2-max 中的素數,并首先輸出初始素數 2;
4. nums = filter(nums, number) 將 xrange channel 和 2 傳遞給 filter;
5. filter 中創建一個 out channel,生成一個 goroutine;
6. goroutine 中,i 從 xrange channel 也就是 in 中獲取到 2 的自增一 3;
7. number1 = 2,3%2 不能整除,素數,放入 out,return out;
8. nums = out,然后 number = <- nums 更新 number 為 3;
9. 循環輸出,繼續調用 filter,這時候傳入 nums 也就是 out1 和 number 3;
10. filter 新建 out2,生成 goroutine2,從 out1(in)中讀取,沒有數值,堵塞;
11. goroutine1 out1 值被消費,繼續運行,從 xrange(in)中讀取 4,number1 = 2,4%2 整除 pass,5%2 不能整除,輸出到 out1,阻塞;
12. goroutine2 從 out1(in)中順利讀取到值 5,繼續運行,number2 = 3,5%3 不能整除,素數,輸出到 out2,return;
13. ………………
14. 依次類推,從 goroutine1 開始,不斷固定的篩掉 2 的倍數、3 的倍數等等,新的 in 不斷阻塞從頭篩選獲取;在這個過程中,out 本身形成了一個鏈條,goroutine 的排序運行讓整個鏈條順利運行;
15. 最終不斷從 xrange 中獲取到超于一百的素數,return 之后判定結束運行。

值得注意的是:in2 獲取了 out1,讓 out1 不再阻塞,能夠繼續運行,但是最終還是會阻塞在輸出處 out1,直到最新的 out return,并再次調用 filter。也就是說它們的執行順序并不一直是我上面說的每次都按照順序執行,只是最終呈現的結果是順序的,并且邏輯上沒有問題

兩個關鍵點卡住了我很長時間,第一點很基礎但一時忽略了,而第二點尤為重要,讓我對整個執行過程總是隔著一層霧。還是需要更多的學習與實踐,記錄下分析結果,與君共勉。