Go素數篩選分析

1. 素數篩選介紹

學習Go語言的過程中，遇到素數篩選的問題。這是一個經典的並行程式設計問題，是某大佬的程式碼，短短几行程式碼就實現了素數篩選。但是自己看完原理和程式碼後一臉懵逼（僅此幾行能實現素數篩選），然後在網上查詢相關資料，依舊似懂非懂。經過1天的分析偵錯，目前基本上掌握了的原理。在這裡介紹一下學習理解的過程。

素數篩選基本原理如下圖：

就原理來說還是比較簡單的，首先生成從 2 開始的遞增自然數，然後依次對生成的第 1, 2, 3, ...個素數 整除，經過全部整除仍有餘數的自然數，將會是素數。

大佬的程式碼如下：

// 返回生成自然數序列的管道: 2, 3, 4, ...
// GenerateNatural 函數內部啟動一個 Goroutine 生產序列，返回對應的管道
func GenerateNatural() chan int {
	ch := make(chan int)
	go func() {
		for i := 2; ; i++ {
			ch <- i
		}
	}()
	return ch
}
// 管道過濾器: 將輸入序列中是素數倍數的數淘汰，並返回新的管道
// 函數內部啟動一個 Goroutine 生產序列，返回過濾後序列對應的管道
func PrimeFilter(in <-chan int, prime int) chan int {
	out := make(chan int)
	go func() {
		for {
			if i := <-in; i%prime != 0 {
				out <- i
			}
		}
	}()
	return out
}
func main() {
	ch := GenerateNatural() // 自然數序列: 2, 3, 4, ...
	for i := 0; i < 100; i++ {
		prime := <-ch // 新出現的素數
		fmt.Printf("%v: %v\n", i+1, prime)
		ch = PrimeFilter(ch, prime) // 基於新素數構造的過濾器
	}
}

main()函數先是呼叫 GenerateNatural() 生成最原始的從 2 開始的自然數序列。然後開始一個 100 次迭代的迴圈，希望生成 100 個素數。在每次迴圈迭代開始的時候，管道中的第一個數必定是素數，我們先讀取並列印這個素數。然後基於管道中剩餘的數列，並以當前取出的素數為篩子過濾後面的素數。不同的素數篩子對應的管道是串聯在一起的。

執行程式碼，程式正確輸出如下：

1: 2
2: 3
3: 5
......
......
98: 521
99: 523
100: 541

2. 程式碼分析

之前在課本中學習到：chan底層結構是一個指標，所以我們能在函數間直接傳遞 channel，而不用傳遞 channel 的指標。

上述程式碼fun GenerateNatural()中建立了管道ch := make(chan int)，並建立一個協程（為了便於描述，該協程稱為Gen）持續向ch中寫入漸增自然數。

當i=0時，main()中prime := <-ch讀取該ch（此時prime=2，輸出素數2），接著將ch傳入PrimeFilter(ch, prime)中。PrimeFilter(ch, prime)建立新協程（稱為PF(ch, 2)）持續讀取傳入的ch（ch中2之前已被取出，從3依次往後讀取），同時返回一個新的chan out（當通過過濾器的i向out寫入時，此時out僅有寫入而沒有讀取操作，PF(ch, 2)將阻塞在第1次寫chan out操作）。與此同時main()中ch = PrimeFilter(ch, 2)將out賦值給ch，此操作給ch賦了新變數。到這裡，重點來了：由於在隨後的時間裡，協程Gen、PF(ch, 2)中仍需要不停寫入和讀取ch，這裡將out賦值給ch的操作是否會更改Gen、PF(ch, 2)兩協程中ch的值了？

直接給出答案（後面會給出程式碼測試），此時ch賦新值不影響Gen、PF(ch, 2)兩協程，僅影響main() for迴圈體隨後對chan的操作。（本人認為go中channel引數傳遞採用了channel指標的拷貝，後續給channel賦新值相當於將該channel重新指向了另外一個地址，該channel與之前協程中使用的channel分別指向不同地址，是完全不同的變數）。為了便於後面分析，這裡將ch = PrimeFilter(ch, 2)賦值後的ch稱為ch_2。

當i=1時，main() for迴圈讀取前一次產生新的ch_2賦值給prime（此時prime=3，輸出素數3），接著將ch_2傳入PrimeFilter(ch, prime)並建立新協程（稱為PF(ch, 3)），而後ch = PrimeFilter(ch, 3)將新產生的out賦值給ch，稱為ch_3。與此同時協程Gen持續向ch中寫入直至阻塞，攜程PF(ch, 2)持續讀取ch值並寫入ch_2直至阻塞，新協程PF(ch, 3)持續讀取ch_2值並輸出至chan out（即ch_3）（此時ch_3僅有寫入而沒有讀取操作，PF(ch, 3)將阻塞在第1次寫ch_3操作）。

當i繼續增加時，後面的結果以此類推。

總結一下：main()函數中，每回圈1次，會增加一個協程PF(ch, prime)，且協程Gen與新增加的協程之間是串聯的關係（即前一個協程的輸出，作為下一個協程的輸入，二者通過channel互動），協程main每次迴圈讀取最後一個channel的第1個值，獲取prime素數。基本原理如下圖所示。

3. 程式碼驗證

(1) channel引數傳遞驗證

func main() {
	ch1 := make(chan int)
	go write(ch1)
	go read(ch1)
	time.Sleep(time.Second * 3)
	fmt.Println("main() 1", ch1)
	ch2 = make(chan int)
    ch1 = ch2
	fmt.Println("main() 2", ch1)
	time.Sleep(time.Second * 3)
}

func read(ch1 chan int) {
	for {
		time.Sleep(time.Second)
		fmt.Println("read", <-ch1, ch1)
	}
}
func write(ch1 chan int) {
	for {
		time.Sleep(time.Second)
		fmt.Println("write", ch1)
		ch1 <- 5
	}
}

測試程式碼比較簡單，在main()中建立chan ch1，後建立兩個協程write、read分別對ch1不間斷寫入與讀取，持續一段時間後，main()新建立ch2，並賦值給ch1，檢視協程write、read是否受到影響。

...
write 0xc000048120
read 5 0xc000048120
main() 1 0xc000048120
main() 2 0xc000112000
write 0xc000048120
read 5 0xc000048120
...

程式輸出如上，可以看到ch1地址為0xc000048120，ch2地址為0xc000112000。main()中ch1的重新賦值不會影響到其他協程對ch1的讀寫。

(2) 素數篩選程式碼驗證

在之前素數篩選原始碼的基礎上，新增一些偵錯列印程式碼，以便更容易分析程式碼，如下所示。

package main

import (
   "fmt"
   "runtime"
   "sync/atomic"
)

var total uint32

// 返回生成自然數序列的管道: 2, 3, 4, ...
func GenerateNatural() chan int {
   ch := make(chan int)
   go func() {
      goRoutineId := atomic.AddUint32(&total, 1)
      for i := 2; ; i++ {
         //fmt.Println("before generate", i)
         ch <- i
         fmt.Printf("[routineId: %.4v]----generate i=%v, ch=%v\n", goRoutineId, i, ch)
      }
   }()
   return ch
}

// 管道過濾器: 刪除能被素數整除的數
func PrimeFilter(in <-chan int, prime int) chan int {
   out := make(chan int)
   go func() {
      goRoutineId := atomic.AddUint32(&total, 1)
      for {
         i := <-in
         if i%prime != 0 {
            fmt.Printf("[routineId: %.4v]----read i=%v, in=%v, out=%v\n", goRoutineId, i, in, out)
            out <- i
         }
      }
   }()
   return out
}

func main() {
   goRoutineId := atomic.AddUint32(&total, 1)
   ch := GenerateNatural() // 自然數序列: 2, 3, 4, ...
   for i := 0; i < 100; i++ {
      //fmt.Println("--------before read prime")
      prime := <-ch // 新出現的素數
      fmt.Printf("[routineId: %.4v]----main i=%v; prime=%v, ch=%v, total=%v\n", goRoutineId, i+1, prime, ch, runtime.NumGoroutine())
      ch = PrimeFilter(ch, prime) // 基於新素數構造的過濾器
   }
}

1）列印協程`id`

由於Go語言沒有直接把獲取go程id的介面暴露出來，這裡採用atomic.AddUint32原子操作，每次新建1個協程時，將atomic.AddUint32(&total, 1)的值儲存下來，作為該協程的唯一id。

2）輸出結果分析

[routineId: 0002]----generate i=2, ch=0xc000018180
[routineId: 0001]----main i=1; prime=2, ch=0xc000018180, total=2
[routineId: 0003]----read i=3, in=0xc000018180, out=0xc000090000
[routineId: 0002]----generate i=3, ch=0xc000018180
[routineId: 0001]----main i=2; prime=3, ch=0xc000090000, total=3
[routineId: 0002]----generate i=4, ch=0xc000018180
[routineId: 0002]----generate i=5, ch=0xc000018180
[routineId: 0003]----read i=5, in=0xc000018180, out=0xc000090000
[routineId: 0002]----generate i=6, ch=0xc000018180
[routineId: 0002]----generate i=7, ch=0xc000018180
......

輸出結果如上，main協程id=1，GenerateNatural協程id=2，PrimeFilter(ch, prime)協程id從3開始遞增。這裡還是不太容易看明白，下面分類闡述輸出結果。

首先，單獨檢視GenerateNatural協程輸出，如下。可以看出，此協程就是在寫入阻塞交替間往ch=0xc000018180中寫入資料。

[routineId: 0002]----generate i=2, ch=0xc000018180
[routineId: 0002]----generate i=3, ch=0xc000018180
[routineId: 0002]----generate i=4, ch=0xc000018180
[routineId: 0002]----generate i=5, ch=0xc000018180
[routineId: 0002]----generate i=6, ch=0xc000018180
[routineId: 0002]----generate i=7, ch=0xc000018180
[routineId: 0002]----generate i=8, ch=0xc000018180
[routineId: 0002]----generate i=9, ch=0xc000018180
......

接著，檢視PrimeFilter(ch, prime)協程，如下。每輸出1個素數，將增加1個PrimeFilter(ch, prime)協程，且協程id號從3開始遞增。

[routineId: 0003]----read i=3, in=0xc000018180, out=0xc000090000
......
[routineId: 0004]----read i=5, in=0xc000090000, out=0xc0000181e0
......
[routineId: 0005]----read i=7, in=0xc0000181e0, out=0xc00020a000
......
[routineId: 0006]----read i=11, in=0xc00020a000, out=0xc00020a060
......

可以看出，協程[routineId: 0003]讀取GenerateNatural協程ch=0xc000018180值作為輸入，並將out=0xc000090000輸出作為[routineId: 0004]協程輸入。以此類推，從id>=2開始的多個協程是通過channel管道串聯在一起的，且前一個協程的輸出作為後一個協程的輸入。與前述分析一致。

最後，檢視main執行緒，其id=1，可見main每次迴圈讀取最後一個channel的第1個值，且該值為素數。與前述分析一致。

[routineId: 0002]----generate i=2, ch=0xc000018180
[routineId: 0001]----main i=1; prime=2, ch=0xc000018180, total=2
[routineId: 0003]----read i=3, in=0xc000018180, out=0xc000090000
......
[routineId: 0001]----main i=2; prime=3, ch=0xc000090000, total=3
......
[routineId: 0004]----read i=5, in=0xc000090000, out=0xc0000181e0
......
[routineId: 0001]----main i=3; prime=5, ch=0xc0000181e0, total=4
[routineId: 0005]----read i=7, in=0xc0000181e0, out=0xc00020a000
[routineId: 0001]----main i=4; prime=7, ch=0xc00020a000, total=5

4. 總結

對Go不同協程中chan的傳遞原理了解不深，且素數篩選程式碼中多個協程統一使用了ch名稱，特別是對於main()中ch的重新賦值會不會影響其他協程不甚瞭解，導致理解混亂。
經深入分析程式碼後理解了素數篩選的內部原理，可謂知其所以然，然如果讓自己來設計，程式碼肯定會臃腫非常多，對於大佬能用如此簡單的程式碼實現功能，萬分欽佩！

Go素數篩選分析

Go素數篩選分析

1. 素數篩選介紹

2. 程式碼分析

3. 程式碼驗證

(1) channel引數傳遞驗證

(2) 素數篩選程式碼驗證

1）列印協程id

2）輸出結果分析

4. 總結

1）列印協程`id`