Golang Daisy-chain分析

在学习 go 并发的过程中,意外看到了菊花链的代码,一开始基本上对于整体流程摸不着头脑,经过查阅资料和自己苦思,最终找到了两个关键点,捋清了整个执行过程

代码:

func TestFunc5(t *testing.T) {/* *  利用信道菊花链筛法求某一个整数范围的素数 *  筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列, *  1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。 *  依次类推,直到筛子为空时结束 */const max = 100  // 找出100以内的所有素数nums := xrange() // 初始化一个整数生成器number := <-nums // 从生成器中抓一个整数(2), 作为初始化整数for number <= max { // number作为筛子,当筛子超过max的时候结束筛选fmt.Println(number)         // 打印素数, 筛子即一个素数nums = filter(nums, number) //筛掉number的倍数number = <-nums // 更新筛子}}func filter(in chan int, number int) chan int {// 输入一个整数队列,筛出是number倍数的, 不是number的倍数的放入输出队列// in:  输入队列out := make(chan int)go func() {for {i := <-in // 从输入中取一个if i%number != 0 {out <- i // 放入输出信道}}}()return out}func xrange() chan int { // 从2开始自增的整数生成器var ch chan int = make(chan int)go func() { // 开出一个goroutinefor i := 2; ; i++ {ch <- i // 直到信道索要数据,才把i添加进信道}}()return ch}

代码是从网络上复制,然后放在本地测试文件中进行调试的,自己运行的话可以把 TestFunc 改成 main

对于菊花链的代码,从逻辑上来说并不复杂:

• 采用的是埃式筛,将 2-n 的整数按照从小到大的顺序排列,以 2 为开始的素数,3/2 不能整除是素数,5/2 且 5/3 不能整除是素数,以此类推,不断从小到大除以已经得出的素数,都不能整除,意味着它没有可因式分解的余地,也就是素数;代码也有改进的空间,即使用欧式筛,去除不必要的筛选(这个我还没研究,感兴趣的可以自己看看);

对于菊花链,对我个人而言,最关键的两个点在于:

1. filter 中所有的 goroutine 都是一直存在的;
2. filter 中不断建立 out,而 out 又通过 return 返回给 nums,nums 再通过 filter 传参给 in;最终效果也就是每个 goroutine 中都建立了一个新的 channel,而这个 channel 都会依次传递给下一个 goroutine,也就是第一个的 out 第二个 in 接收,第二个的第三个接收等等,等到所有的 goroutine 依次执行完后,最后一个 goroutine 才会获取到真正想要的那个 out,然后返回给 nums;

下面即是我捋出来的整个执行过程:

1. 通过 xrange 初始化一个 channel nums,接下来依次接收 从 2 开始不断自增 1 的整数,将作为被筛选的数;
2. number 初始化中 nums 中获取 2;
3. 开始循环筛选 2-max 中的素数,并首先输出初始素数 2;
4. nums = filter(nums, number) 将 xrange channel 和 2 传递给 filter;
5. filter 中创建一个 out channel,生成一个 goroutine;
6. goroutine 中,i 从 xrange channel 也就是 in 中获取到 2 的自增一 3;
7. number1 = 2,3%2 不能整除,素数,放入 out,return out;
8. nums = out,然后 number = <- nums 更新 number 为 3;
9. 循环输出,继续调用 filter,这时候传入 nums 也就是 out1 和 number 3;
10. filter 新建 out2,生成 goroutine2,从 out1(in)中读取,没有数值,堵塞;
11. goroutine1 out1 值被消费,继续运行,从 xrange(in)中读取 4,number1 = 2,4%2 整除 pass,5%2 不能整除,输出到 out1,阻塞;
12. goroutine2 从 out1(in)中顺利读取到值 5,继续运行,number2 = 3,5%3 不能整除,素数,输出到 out2,return;
13. ………………
14. 依次类推,从 goroutine1 开始,不断固定的筛掉 2 的倍数、3 的倍数等等,新的 in 不断阻塞从头筛选获取;在这个过程中,out 本身形成了一个链条,goroutine 的排序运行让整个链条顺利运行;
15. 最终不断从 xrange 中获取到超于一百的素数,return 之后判定结束运行。

值得注意的是:in2 获取了 out1,让 out1 不再阻塞,能够继续运行,但是最终还是会阻塞在输出处 out1,直到最新的 out return,并再次调用 filter。也就是说它们的执行顺序并不一直是我上面说的每次都按照顺序执行,只是最终呈现的结果是顺序的,并且逻辑上没有问题

两个关键点卡住了我很长时间,第一点很基础但一时忽略了,而第二点尤为重要,让我对整个执行过程总是隔着一层雾。还是需要更多的学习与实践,记录下分析结果,与君共勉。