## 4.13\. 生成素數 這里我們要給出一個并行處理程序及之間的通信。這是一個非常大的課題，我們這里只是給出一些要點。 素數篩選是一個比較經典的問題（這里側重于Eratosthenes素數篩選算法的并行特征）。它以全部的 自然后為篩選對象。首選從第一個素數2開始，后續數列中是已經素數倍數的數去掉。每次篩選可以得到 一個新的素數，然后將新的素數加入篩選器，繼續篩選后面的自然數列（這里要參考算法的描述調整）。 這里是算法工作的原理圖。每個框對應一個素數篩選器，并且將剩下的數列傳給下一個素數篩進行篩選。  為了產生整數序列，我們使用管道。管道可以用于連接兩個并行的處理單。在Go語言中， 管道由運行時庫管理，可以用"make"來創建新的管道。 這是"progs/sieve.go"程序的第一個函數： ``` 09 // Send the sequence 2, 3, 4, ... to channel 'ch'. 10 func generate(ch chan int) { 11 for i := 2; ; i++ { 12 ch <- i // Send 'i' to channel 'ch'. 13 } 14 } ``` 函數"generate"用于生成2, 3, 4, 5, ...自然數序列，然后依次發送到管道。 這里用到了二元操作符"&lt;-"， 它用于向管道發送數據。當管道沒有接受者的時候 會阻塞，直到有接收者從管道接受數據為止。 過濾器函數有三個參數：輸入輸出管道和用于過濾的素數。當輸入管道讀出來的數不能被 過濾素數整除時，則將當前整數發送到輸出管道。這里用到了"&lt;-"操作符，它用于從 管道讀取數據。 ``` 16 // Copy the values from channel 'in' to channel 'out', 17 // removing those divisible by 'prime'. 18 func filter(in, out chan int, prime int) { 19 for { 20 i := <-in // Receive value of new variable 'i' from 'in'. 21 if i % prime != 0 { 22 out <- i // Send 'i' to channel 'out'. 23 } 24 } 25 } ``` 整數生成器generator函數和過濾器filters是并行執行的。Go語言有自己的并發 程序設計模型，這個和傳統的進程/線程/輕量線程類似。為了區別，我們把Go語言 中的并行程序稱為goroutines。如果一個函數要以goroutines方式并行執行， 只要用"go"關鍵字作為函數調用的前綴即可。goroutines和它的啟動線程并行執行， 但是共享一個地址空間。例如，以goroutines方式執行前面的sum函數： ``` go sum(hugeArray); // calculate sum in the background ``` 如果想知道計算什么時候結束，可以讓sum用管道把結果返回： ``` ch := make(chan int); go sum(hugeArray, ch); // ... do something else for a while result := &lt;-ch; // wait for, and retrieve, result ``` 再回到我們的素數篩選程序。下面程序演示如何將不同的素數篩鏈接在一起： ``` 28 func main() { 29 ch := make(chan int) // Create a new channel. 30 go generate(ch) // Start generate() as a goroutine. 31 for { 32 prime := <-ch 33 fmt.Println(prime) 34 ch1 := make(chan int) 35 go filter(ch, ch1, prime) 36 ch = ch1 37 } 38 } ``` 29行先調用"generate"函數，用于產生最原始的自然數序列（從2開始）。然后 從輸出管道讀取的第一個數為新的素數，并以這個新的素數生成一個新的過濾器。 然后將新創建的過濾器添加到前一個過濾器后面，新過濾器的輸出作為新的輸出 管道。 sieve程序還可以寫的更簡潔一點。這里是"generate"的改進，代碼在 "progs/sieve1.go"中： ``` 10 func generate() chan int { 11 ch := make(chan int) 12 go func(){ 13 for i := 2; ; i++ { 14 ch <- i 15 } 16 }() 17 return ch 18 } ``` 新完善的generate函數在內部進行必須的初始化操作。它創建輸出管道，然后 啟動goroutine用于產生整數序列，最后返回輸出管道。它類似于一個并發程序 的工廠函數，完成后返回一個用于鏈接的管道。 第12-16行用go關鍵字啟動一個匿名函數。需要注意的是，generate函數的"ch" 變量對于匿名函數是可見，并且"ch"變量在generate函數返回后依然存在（因為 匿名的goroutine還在運行）。 這里我們采用過濾器"filter"來篩選后面的素數： ``` 21 func filter(in chan int, prime int) chan int { 22 out := make(chan int) 23 go func() { 24 for { 25 if i := <-in; i % prime != 0 { 26 out <- i 27 } 28 } 29 }() 30 return out 31 } ``` 函數"sieve"對應處理的一個主循環，它只是依次將數列交給后面的素數篩選器進行篩選。 如果遇到新的素數，再輸出素數后以該素數創建信的篩選器。 ``` 33 func sieve() chan int { 34 out := make(chan int) 35 go func() { 36 ch := generate() 37 for { 38 prime := <-ch 39 out <- prime 40 ch = filter(ch, prime) 41 } 42 }() 43 return out 44 } ``` 主函數入口啟動素數生成服務器，然后打印從管道輸出的素數： ``` 46 func main() { 47 primes := sieve() 48 for { 49 fmt.Println(<-primes) 50 } 51 } ```