Go素数筛选分析详解

对于一个Golang开发者来说，牢固扎实的基础是十分重要的，golang学习网就来带大家一点点的掌握基础知识点。今天本篇文章带大家了解《Go素数筛选分析详解》，主要介绍了素数、筛选，希望对大家的知识积累有所帮助，快点收藏起来吧，否则需要时就找不到了！

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 
<p><code>main()</code>函数先是调用 <code>GenerateNatural()</code> 生成最原始的从 <code>2</code> 开始的自然数序列。然后开始一个 <code>100</code> 次迭代的循环，希望生成 <code>100</code> 个素数。在每次循环迭代开始的时候，管道中的第一个数必定是素数，我们先读取并打印这个素数。然后基于管道中剩余的数列，并以当前取出的素数为筛子过滤后面的素数。不同的素数筛子对应的管道是串联在一起的。</p>
<p>运行代码，程序正确输出如下：</p>
<blockquote><p>1: 2<br>2: 3<br>3: 5<br>......<br>......<br>98: 521<br>99: 523<br>100: 541</p></blockquote>
<h2>2. 代码分析</h2>
<p>之前在课本中学习到：<code>chan底层结构 是一个指针，所以我们能在函数间直接传递 channel，而不用传递 channel 的指针</code>。</p>
<p>上述代码<code>fun GenerateNatural()</code>中创建了管道<code>ch := make(chan int)</code>，并创建一个协程（为了便于描述，该协程称为<code>Gen</code>）持续向<code>ch</code>中写入渐增自然数。</p>
<p>当<code>i=0</code>时，<code>main()</code>中<code>prime := 读取该<code>ch</code>（此时<code>prime=2</code>，输出素数<code>2</code>），接着将<code>ch</code>传入<code>PrimeFilter(ch, prime)</code>中。<code>PrimeFilter(ch, prime)</code>创建新协程（称为<code>PF(ch, 2)</code>）持续读取传入的<code>ch</code>（<code>ch</code>中<code>2</code>之前已被取出，从<code>3</code>依次往后读取），同时返回一个新的<code>chan out</code>（当通过过滤器的<code>i</code>向<code>out</code>写入时，此时<code>out</code>仅有写入而没有读取操作，<code>PF(ch, 2)</code>将阻塞在第<code>1</code>次写<code>chan out</code>操作）。与此同时<code>main()</code>中<code>ch = PrimeFilter(ch, 2)</code>将<code>out</code>赋值给<code>ch</code>，此操作给<code>ch</code>赋了新变量。到这里，重点来了：由于在随后的时间里，协程<code>Gen</code>、<code>PF(ch, 2)</code>中仍需要不停写入和读取<code>ch</code>，这里将<code>out</code>赋值给<code>ch</code>的操作是否会更改<code>Gen</code>、<code>PF(ch, 2)</code>两协程中<code>ch</code>的值了？</code></p>
<p>直接给出答案（后面会给出代码测试），此时<code>ch</code>赋新值不影响<code>Gen</code>、<code>PF(ch, 2)</code>两协程，仅影响<code>main() for</code>循环体随后对<code>chan</code>的操作。（本人认为<code>go</code>中<code>channel</code>参数传递采用了<code>channel</code>指针的拷贝，后续给<code>channel</code>赋新值相当于将该<code>channel</code>重新指向了另外一个地址，该<code>channel</code>与之前协程中使用的<code>channel</code>分别指向不同地址，是完全不同的变量）。为了便于后面分析，这里将<code>ch = PrimeFilter(ch, 2)</code>赋值后的<code>ch</code>称为<code>ch_2</code>。</p>
<p>当<code>i=1</code>时，<code>main() for</code>循环读取前一次产生新的<code>ch_2</code>赋值给<code>prime</code>（此时<code>prime=3</code>，输出素数<code>3</code>），接着将<code>ch_2</code>传入<code>PrimeFilter(ch, prime)</code>并创建新协程（称为<code>PF(ch, 3)</code>），而后<code>ch = PrimeFilter(ch, 3)</code>将新产生的<code>out</code>赋值给<code>ch</code>，称为<code>ch_3</code>。与此同时协程<code>Gen</code>持续向<code>ch</code>中写入直至阻塞，携程<code>PF(ch, 2)</code>持续读取<code>ch</code>值并写入<code>ch_2</code>直至阻塞，新协程<code>PF(ch, 3)</code>持续读取<code>ch_2</code>值并输出至<code>chan out（即ch_3）</code>（此时<code>ch_3</code>仅有写入而没有读取操作，<code>PF(ch, 3)</code>将阻塞在第<code>1</code>次写<code>ch_3</code>操作）。</p>
<p>当<code>i</code>继续增加时，后面的结果以此类推。</p>
<p>总结一下：<code>main()</code>函数中，每循环<code>1</code>次，会增加一个协程<code>PF(ch, prime)</code>，且协程<code>Gen</code>与新增加的协程之间是串联的关系（即前一个协程的输出，作为下一个协程的输入，二者通过<code>channel</code>交互），协程<code>main</code>每次循环读取最后一个<code>channel</code>的第<code>1</code>个值，获取<code>prime</code>素数。基本原理如下图所示。</p>
<p style="text-align:center"><img alt="" src="/uploads/20221231/167247992263b004b2401cc.jpg"></p>
<h2>3. 代码验证</h2>
<p>(1) channel参数传递验证</p>
<pre class="brush:go;">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", 
<p>测试代码比较简单，在<code>main()</code>中创建<code>chan ch1</code>，后创建两个协程<code>write</code>、<code>read</code>分别对<code>ch1</code>不间断写入与读取，持续一段时间后，<code>main()</code>新创建<code>ch2</code>，并赋值给<code>ch1</code>，查看协程<code>write</code>、<code>read</code>是否受到影响。</p>
<pre class="brush:plain;">...
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 
<p>1）打印协程<code>id</code></p>
<p>由于<code>Go</code>语言没有直接把获取<code>go</code>程<code>id</code>的接口暴露出来，这里采用<code>atomic.AddUint32</code>原子操作，每次新建<code>1</code>个协程时，将<code>atomic.AddUint32(&total, 1)</code>的值保存下来，作为该协程的唯一<code>id</code>。</p>
<p>2）输出结果分析</p>
<blockquote><p>[routineId: 0002]----generate i=2, ch=0xc000018180<br>[routineId: 0001]----main i=1; prime=2, ch=0xc000018180, total=2<br>[routineId: 0003]----read i=3, in=0xc000018180, out=0xc000090000<br>[routineId: 0002]----generate i=3, ch=0xc000018180<br>[routineId: 0001]----main i=2; prime=3, ch=0xc000090000, total=3<br>[routineId: 0002]----generate i=4, ch=0xc000018180<br>[routineId: 0002]----generate i=5, ch=0xc000018180<br>[routineId: 0003]----read i=5, in=0xc000018180, out=0xc000090000<br>[routineId: 0002]----generate i=6, ch=0xc000018180<br>[routineId: 0002]----generate i=7, ch=0xc000018180<br>......</p></blockquote>
<p>输出结果如上，<code>main</code>协程<code>id=1</code>，<code>GenerateNatural</code>协程<code>id=2</code>，<code>PrimeFilter(ch, prime)</code>协程<code>id</code>从<code>3</code>开始递增。这里还是不太容易看明白，下面分类阐述输出结果。</p>
<p>首先，单独查看<code>GenerateNatural</code>协程输出，如下。可以看出，此协程就是在写入阻塞交替间往<code>ch=0xc000018180</code>中写入数据。</p>
<pre class="brush:plain;">[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素数筛选分析详解》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多Golang知识！