第Go素數(shù)篩選分析詳解目錄Go素數(shù)篩選分析1.素數(shù)篩選介紹2.代碼分析3.代碼驗證4.總結(jié)

Go素數(shù)篩選分析

1.素數(shù)篩選介紹

學習Go語言的過程中，遇到素數(shù)篩選的問題。這是一個經(jīng)典的并發(fā)編程問題，是某大佬的代碼，短短幾行代碼就實現(xiàn)了素數(shù)篩選。但是自己看完原理和代碼后一臉懵逼（僅此幾行能實現(xiàn)素數(shù)篩選），然后在網(wǎng)上查詢相關(guān)資料，依舊似懂非懂。經(jīng)過1天的分析調(diào)試，目前基本上掌握了的原理。在這里介紹一下學習理解的過程。

素數(shù)篩選基本原理如下圖：

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

大佬的代碼如下：

//返回生成自然數(shù)序列的管道:2,3,4,...

//GenerateNatural函數(shù)內(nèi)部啟動一個Goroutine生產(chǎn)序列，返回對應的管道

funcGenerateNatural()chanint{

ch:=make(chanint)

gofunc(){

fori:=2;;i++{

ch-i

returnch

//管道過濾器:將輸入序列中是素數(shù)倍數(shù)的數(shù)淘汰，并返回新的管道

//函數(shù)內(nèi)部啟動一個Goroutine生產(chǎn)序列，返回過濾后序列對應的管道

funcPrimeFilter(in-chanint,primeint)chanint{

out:=make(chanint)

gofunc(){

for{

ifi:=i%prime!=0{

out-i

returnout

funcmain(){

ch:=GenerateNatural()//自然數(shù)序列:2,3,4,...

fori:=0;i100;i++{

prime:=-ch//新出現(xiàn)的素數(shù)

fmt.Printf("%v:%v\n",i+1,prime)

ch=PrimeFilter(ch,prime)//基于新素數(shù)構(gòu)造的過濾器

}

main()函數(shù)先是調(diào)用GenerateNatural()生成最原始的從2開始的自然數(shù)序列。然后開始一個100次迭代的循環(huán)，希望生成100個素數(shù)。在每次循環(huán)迭代開始的時候，管道中的第一個數(shù)必定是素數(shù)，我們先讀取并打印這個素數(shù)。然后基于管道中剩余的數(shù)列，并以當前取出的素數(shù)為篩子過濾后面的素數(shù)。不同的素數(shù)篩子對應的管道是串聯(lián)在一起的。

運行代碼，程序正確輸出如下：

1:2

2:3

3:5

......

......

98:521

99:523

100:541

2.代碼分析

之前在課本中學習到：chan底層結(jié)構(gòu)是一個指針，所以我們能在函數(shù)間直接傳遞channel，而不用傳遞channel的指針。

上述代碼funGenerateNatural()中創(chuàng)建了管道ch:=make(chanint)，并創(chuàng)建一個協(xié)程（為了便于描述，該協(xié)程稱為Gen）持續(xù)向ch中寫入漸增自然數(shù)。

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

直接給出答案（后面會給出代碼測試），此時ch賦新值不影響Gen、PF(ch,2)兩協(xié)程，僅影響main()for循環(huán)體隨后對chan的操作。（本人認為go中channel參數(shù)傳遞采用了channel指針的拷貝，后續(xù)給channel賦新值相當于將該channel重新指向了另外一個地址，該channel與之前協(xié)程中使用的channel分別指向不同地址，是完全不同的變量）。為了便于后面分析，這里將ch=PrimeFilter(ch,2)賦值后的ch稱為ch_2。

當i=1時，main()for循環(huán)讀取前一次產(chǎn)生新的ch_2賦值給prime（此時prime=3，輸出素數(shù)3），接著將ch_2傳入PrimeFilter(ch,prime)并創(chuàng)建新協(xié)程（稱為PF(ch,3)），而后ch=PrimeFilter(ch,3)將新產(chǎn)生的out賦值給ch，稱為ch_3。與此同時協(xié)程Gen持續(xù)向ch中寫入直至阻塞，攜程PF(ch,2)持續(xù)讀取ch值并寫入ch_2直至阻塞，新協(xié)程PF(ch,3)持續(xù)讀取ch_2值并輸出至chanout（即ch_3）（此時ch_3僅有寫入而沒有讀取操作，PF(ch,3)將阻塞在第1次寫ch_3操作）。

當i繼續(xù)增加時，后面的結(jié)果以此類推。

總結(jié)一下：main()函數(shù)中，每循環(huán)1次，會增加一個協(xié)程PF(ch,prime)，且協(xié)程Gen與新增加的協(xié)程之間是串聯(lián)的關(guān)系（即前一個協(xié)程的輸出，作為下一個協(xié)程的輸入，二者通過channel交互），協(xié)程main每次循環(huán)讀取最后一個channel的第1個值，獲取prime素數(shù)?；驹砣缦聢D所示。

3.代碼驗證

(1)channel參數(shù)傳遞驗證

funcmain(){

ch1:=make(chanint)

gowrite(ch1)

goread(ch1)

time.Sleep(time.Second*3)

fmt.Println("main()1",ch1)

ch2=make(chanint)

ch1=ch2

fmt.Println("main()2",ch1)

time.Sleep(time.Second*3)

funcread(ch1chanint){

for{

time.Sleep(time.Second)

fmt.Println("read",-ch1,ch1)

funcwrite(ch1chanint){

for{

time.Sleep(time.Second)

fmt.Println("write",ch1)

ch1-5

}

測試代碼比較簡單，在main()中創(chuàng)建chanch1，后創(chuàng)建兩個協(xié)程write、read分別對ch1不間斷寫入與讀取，持續(xù)一段時間后，main()新創(chuàng)建ch2，并賦值給ch1，查看協(xié)程write、read是否受到影響。

...

write0xc000048120

read50xc000048120

main()10xc000048120

main()20xc000112000

write0xc000048120

read50xc000048120

...

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

(2)素數(shù)篩選代碼驗證

在之前素數(shù)篩選源碼的基礎(chǔ)上，添加一些調(diào)試打印代碼，以便更容易分析代碼，如下所示。

packagemain

import(

"fmt"

"runtime"

"sync/atomic"

vartotaluint32

//返回生成自然數(shù)序列的管道:2,3,4,...

funcGenerateNatural()chanint{

ch:=make(chanint)

gofunc(){

goRoutineId:=atomic.AddUint32(total,1)

fori:=2;;i++{

//fmt.Println("beforegenerate",i)

ch-i

fmt.Printf("[routineId:%.4v]----generatei=%v,ch=%v\n",goRoutineId,i,ch)

returnch

//管道過濾器:刪除能被素數(shù)整除的數(shù)

funcPrimeFilter(in-chanint,primeint)chanint{

out:=make(chanint)

gofunc(){

goRoutineId:=atomic.AddUint32(total,1)

for{

i:=-in

ifi%prime!=0{

fmt.Printf("[routineId:%.4v]----readi=%v,in=%v,out=%v\n",goRoutineId,i,in,out)

out-i

returnout

funcmain(){

goRoutineId:=atomic.AddUint32(total,1)

ch:=GenerateNatural()//自然數(shù)序列:2,3,4,...

fori:=0;i100;i++{

//fmt.Println("--------beforereadprime")

prime:=-ch//新出現(xiàn)的素數(shù)

fmt.Printf("[routineId:%.4v]----maini=%v;prime=%v,ch=%v,total=%v\n",goRoutineId,i+1,prime,ch,runtime.NumGoroutine())

ch=PrimeFilter(ch,prime)//基于新素數(shù)構(gòu)造的過濾器

}

1）打印協(xié)程id

由于Go語言沒有直接把獲取go程id的接口暴露出來，這里采用atomic.AddUint32原子操作，每次新建1個協(xié)程時，將atomic.AddUint32(total,1)的值保存下來，作為該協(xié)程的唯一id。

2）輸出結(jié)果分析

[routineId:0002]----generatei=2,ch=0xc000018180

[routineId:0001]----maini=1;prime=2,ch=0xc000018180,total=2

[routineId:0003]----readi=3,in=0xc000018180,out=0xc000090000

[routineId:0002]----generatei=3,ch=0xc000018180

[routineId:0001]----maini=2;prime=3,ch=0xc000090000,total=3

[routineId:0002]----generatei=4,ch=0xc000018180

[routineId:0002]----generatei=5,ch=0xc000018180

[routineId:0003]----readi=5,in=0xc000018180,out=0xc000090000

[routineId:0002]----generatei=6,ch=0xc000018180

[routineId:0002]----generatei=7,ch=0xc000018180

......

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

首先，單獨查看GenerateNatural協(xié)程輸出，如下?？梢钥闯?，此協(xié)程就是在寫入阻塞交替間往ch=0xc000018180中寫入數(shù)據(jù)。

[routineId:0002]----generatei=2,ch=0xc000018180

[routineId:0002]----generatei=3,ch=0xc000018180

[routineId:0002]----generatei=4,ch=0xc000018180

[routineId:0002]----generatei=5,ch=0xc000018180

[routineId:0002]----generatei=6,ch=0xc000018180

[routineId:0002]----generatei=7,ch=0xc000018180

[routineId:0002]----generatei=8,ch=0xc000018180

[routineId:0002]----generatei=9,ch=0xc000018180

......

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

[routineId:0003]----readi=3,in=0xc000018180,out=0xc000090000

......

[routineId:0004]----readi=5,in=0xc000090000,out=0xc0000181e0

......

[routineId:0005]----readi=7,in=0xc0000181e0,out=0xc00020a000

......

[routineId:0006]----readi=11,in=0xc00020a000,out=0xc00020a060

......

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

最后，查看main線程，其id=1，可見main每次循環(huán)讀取最后一個channel的第1個