Go素数筛选分析

时间:2022-10-19 07:06:26

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))持续读取传入的chch2之前已被取出,从3依次往后读取),同时返回一个新的chan out(当通过过滤器的iout写入时,此时out仅有写入而没有读取操作,PF(ch, 2)将阻塞在第1次写chan out操作)。与此同时main()ch = PrimeFilter(ch, 2)out赋值给ch,此操作给ch赋了新变量。到这里,重点来了:由于在随后的时间里,协程GenPF(ch, 2)中仍需要不停写入和读取ch,这里将out赋值给ch的操作是否会更改GenPF(ch, 2)两协程中ch的值了?

直接给出答案(后面会给出代码测试),此时ch赋新值不影响GenPF(ch, 2)两协程,仅影响main() for循环体随后对chan的操作。(本人认为gochannel参数传递采用了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,后创建两个协程writeread分别对ch1不间断写入与读取,持续一段时间后,main()新创建ch2,并赋值给ch1,查看协程writeread是否受到影响。

...
write 0xc000048120
read 5 0xc000048120
main() 1 0xc000048120
main() 2 0xc000112000
write 0xc000048120
read 5 0xc000048120
...

程序输出如上,可以看到ch1地址为0xc000048120ch2地址为0xc000112000main()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.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语言没有直接把获取goid的接口暴露出来,这里采用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]----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
......

输出结果如上,main协程id=1GenerateNatural协程id=2PrimeFilter(ch, prime)协程id3开始递增。这里还是不太容易看明白,下面分类阐述输出结果。

首先,单独查看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个素数,将增加1PrimeFilter(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的重新赋值会不会影响其他协程不甚了解,导致理解混乱。
  • 经深入分析代码后理解了素数筛选的内部原理,可谓知其所以然,然如果让自己来设计,代码肯定会臃肿非常多,对于大佬能用如此简单的代码实现功能,万分钦佩!