Go素數(shù)篩選分析詳解
Go素數(shù)篩選分析
1. 素數(shù)篩選介紹
學(xué)習(xí)Go語言的過程中，遇到素數(shù)篩選的問題。這是一個經(jīng)典的并發(fā)編程問題，是某大佬的代碼，短短幾行代碼就實現(xiàn)了素數(shù)篩選。但是自己看完原理和代碼后一臉懵逼（僅此幾行能實現(xiàn)素數(shù)篩選），然后在網(wǎng)上查詢相關(guān)資料，依舊似懂非懂。經(jīng)過1天的分析調(diào)試，目前基本上掌握了的原理。在這里介紹一下學(xué)習(xí)理解的過程。
素數(shù)篩選基本原理如下圖：
就原理來說還是比較簡單的，首先生成從 2 開始的遞增自然數(shù)，然后依次對生成的第 1, 2, 3, ...個素數(shù) 整除，經(jīng)過全部整除仍有余數(shù)的自然數(shù)，將會是素數(shù)。
大佬的代碼如下：
// 返回生成自然數(shù)序列的管道: 2, 3, 4, ...
// GenerateNatural 函數(shù)內(nèi)部啟動一個 Goroutine 生產(chǎn)序列，返回對應(yīng)的管道
func GenerateNatural() chan int {
ch := make(chan int)
go func() {
for i := 2; ; i++ {
ch <- i
}
}()
return ch
}
// 管道過濾器: 將輸入序列中是素數(shù)倍數(shù)的數(shù)淘汰，并返回新的管道
// 函數(shù)內(nèi)部啟動一個 Goroutine 生產(chǎn)序列，返回過濾后序列對應(yīng)的管道
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() // 自然數(shù)序列: 2, 3, 4, ...
for i := 0; i < 100; 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ù)列，并以當(dāng)前取出的素數(shù)為篩子過濾后面的素數(shù)。不同的素數(shù)篩子對應(yīng)的管道是串聯(lián)在一起的。
運行代碼，程序正確輸出如下：
1: 2
2: 3
3: 5
......
......
98: 521
99: 523
100: 541
2. 代碼分析
之前在課本中學(xué)習(xí)到：chan底層結(jié)構(gòu) 是一個指針，所以我們能在函數(shù)間直接傳遞 channel，而不用傳遞 channel 的指針。
上述代碼fun GenerateNatural()中創(chuàng)建了管道ch := make(chan int)，并創(chuàng)建一個協(xié)程（為了便于描述，該協(xié)程稱為Gen）持續(xù)向ch中寫入漸增自然數(shù)。
當(dāng)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依次往后讀取），同時返回一個新的chan out（當(dāng)通過過濾器的i向out寫入時，此時out僅有寫入而沒有讀取操作，PF(ch, 2)將阻塞在第1次寫chan out操作）。與此同時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的操作。（本人認(rèn)為go中channel參數(shù)傳遞采用了channel指針的拷貝，后續(xù)給channel賦新值相當(dāng)于將該channel重新指向了另外一個地址，該channel與之前協(xié)程中使用的channel分別指向不同地址，是完全不同的變量）。為了便于后面分析，這里將ch = PrimeFilter(ch, 2)賦值后的ch稱為ch_2。
當(dāng)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值并輸出至chan out（即ch_3）（此時ch_3僅有寫入而沒有讀取操作，PF(ch, 3)將阻塞在第1次寫ch_3操作）。
當(dāng)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ù)傳遞驗證
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()中創(chuàng)建chan ch1，后創(chuàng)建兩個協(xié)程write、read分別對ch1不間斷寫入與讀取，持續(xù)一段時間后，main()新創(chuàng)建ch2，并賦值給ch1，查看協(xié)程write、read是否受到影響。
... write 0xc000048120 read 5 0xc000048120 main() 1 0xc000048120 main() 2 0xc000112000 write 0xc000048120 read 5 0xc000048120 ...
程序輸出如上，可以看到ch1地址為0xc000048120，ch2地址為0xc000112000。main()中ch1的重新賦值不會影響到其他協(xié)程對ch1的讀寫。
(2) 素數(shù)篩選代碼驗證
在之前素數(shù)篩選源碼的基礎(chǔ)上，添加一些調(diào)試打印代碼，以便更容易分析代碼，如下所示。
package main
import (
"fmt"
"runtime"
"sync/atomic"
)
var total uint32
// 返回生成自然數(shù)序列的管道: 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
}
// 管道過濾器: 刪除能被素數(shù)整除的數(shù)
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() // 自然數(shù)序列: 2, 3, 4, ...
for i := 0; i < 100; i++ {
//fmt.Println("--------before read prime")
prime := <-ch // 新出現(xiàn)的素數(shù)
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) // 基于新素數(shù)構(gòu)造的過濾器
}
}1）打印協(xié)程id
由于Go語言沒有直接把獲取go程id的接口暴露出來，這里采用atomic.AddUint32原子操作，每次新建1個協(xié)程時，將atomic.AddUint32(&total, 1)的值保存下來，作為該協(xié)程的唯一id。
2）輸出結(jié)果分析
[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
......
輸出結(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]----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)協(xié)程，如下。每輸出1個素數(shù)，將增加1個PrimeFilter(ch, prime)協(xié)程，且協(xié)程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 ......
可以看出，協(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個值，且該值為素數(shù)。與前述分析一致。
[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. 總結(jié)
- 對
Go不同協(xié)程中chan的傳遞原理了解不深，且素數(shù)篩選代碼中多個協(xié)程統(tǒng)一使用了ch名稱，特別是對于main()中ch的重新賦值會不會影響其他協(xié)程不甚了解，導(dǎo)致理解混亂。 - 經(jīng)深入分析代碼后理解了素數(shù)篩選的內(nèi)部原理，可謂知其所以然，然如果讓自己來設(shè)計，代碼肯定會臃腫非常多，對于大佬能用如此簡單的代碼實現(xiàn)功能，萬分欽佩！
到此這篇關(guān)于Go素數(shù)篩選分析的文章就介紹到這了,更多相關(guān)Go素數(shù)篩選內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
go json數(shù)據(jù)轉(zhuǎn)發(fā)的實現(xiàn)代碼
這篇文章主要介紹了go json數(shù)據(jù)轉(zhuǎn)發(fā)的實現(xiàn)代碼，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
Golang10進(jìn)制轉(zhuǎn)16進(jìn)制的幾種方法代碼示例
這篇文章主要給大家介紹了關(guān)于Golang10進(jìn)制轉(zhuǎn)16進(jìn)制的幾種方法,進(jìn)制轉(zhuǎn)換是Golang的一些基本操作,文中通過實例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-07-07
這篇文章主要介紹了golang監(jiān)聽文件變化的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-03-03
本篇文章主要介紹了golang package time的用法具體詳解，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-05-05
本文主要介紹了Go語言中日期包的具體使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-05-05
go語言使用Casbin實現(xiàn)角色的權(quán)限控制
Casbin是用于Golang項目的功能強大且高效的開源訪問控制庫。本文主要介紹了go語言使用Casbin實現(xiàn)角色的權(quán)限控制，感興趣的可以了解下2021-06-06
slice（切片）是go中常見和強大的類型，這篇文章不是slice使用簡介，從源碼角度來分析slice的實現(xiàn)，slice的一些迷惑的使用方式，感興趣的朋友跟隨小編一起看看吧2023-06-06
掌握GoLang Fiber路由和中間件技術(shù)進(jìn)行高效Web開發(fā)
這篇文章主要為大家介紹了GoLang Fiber路由和中間件進(jìn)行高效Web開發(fā),本文將深入探討 Fiber 中的路由細(xì)節(jié),學(xué)習(xí)如何創(chuàng)建和處理路由,深入了解使用路由參數(shù)的動態(tài)路由,并掌握在 Fiber 應(yīng)用程序中實現(xiàn)中間件的藝術(shù)2024-01-01
Go語言標(biāo)準(zhǔn)庫sync.Once使用場景及性能優(yōu)化詳解
這篇文章主要為大家介紹了Go語言標(biāo)準(zhǔn)庫sync.Once使用場景及性能優(yōu)化詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-12-12
AES( advanced encryption standard)使用相同密鑰進(jìn)行加密和解密，也就是對稱加密。本文將詳細(xì)講解Golang實現(xiàn)AES加密和解密的方法，感興趣的可以學(xué)習(xí)一下2022-05-05