Go素数筛选分析详解

2022-12-03 14:51 开发作者： happyfuns

Go素数筛选分析

1. 素数筛选介绍

学习Go语言的过程中，遇到素数筛选的问题。这是一个经典的并发编程问题，是某大佬的代码，短短几行代码就实现了素数筛选。但是自己看完原理和代码后一脸懵逼（仅此几行能实现素数筛选），然后在网上查询相关资料，依旧似懂非懂。经过1天的分析调试，目前基本上掌握了的原理。在这里介绍一下学习理解的过程。

素数筛选基本原理如下图：

Go素数筛选分析详解

就原理来说还是比较简单的，首先生成从 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（当通过过python滤器的i向out写入时，此时out仅有写入而没有读取操作，PF(ch, 2)将阻塞在第1次写chan ophput操作）。与此同时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素数。基本原理如下图所示。

Go素数筛选分析详解

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.开发者_C培训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]----DloSzmain 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=0xc0002android0a000
......
[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素数筛选内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

继续阅读：Go素数筛选

Go素数筛选分析详解

目录