素数生成器
文章目录
一个不太优雅的素数生成器,主要用来观察“Go-routine + 管道”的开发方式
前言
在阅读《Go高级编程》的时候,里面有个用 Newsqueak 编写的生成素数的例子,感觉这个例子很有意思,我就把它用Go重写了一下,特来此记录一下。
代码
下面的程序实现了一个“素数生成器”,它将会输出前N
个素数:
|
|
分析
整个素数生成器可以用下面这张流程图来表示。
上图中各个 Goroutine 的说明如下
- Counter 用来生成从2到N的数字
FilterPrimer(prime, listen, send)
从listen
__输入管道__中读取数字,将素数prime
的倍数过滤掉,然后将结果输出到send
__输出管道__中sieve
负责从读取素数,并根据产生的素数新建FilterPrime
进行后续的过滤
整个程序的流程如下:
- Counter 产生第一个素数2,
sieve
Goroutine 将2输出到prime
管道中,并以此建立 GoroutineFilterPrime(2)
,Counter
的输出管道会成为FilterPrime(2)
的输入管道 FilterPrime(2)
从输入管道中读取数字并过滤输出,它输出的第一个数字是素数3。sieve
Goroutine 将3输出到prime
管道中,并以此建立 GoroutineFilterPrime(3)
,FilterPrime(2)
的输出管道会作为FilterPrime(3)
的输入管道FilterPrime(3)
从输入管道读取数字并过滤输出,它输出的第一个数字是素数5(4已经被FilterPrime(2)
过滤掉了)。sieve
Goroutine 将5输出到prime
管道中,并以此建立 GoroutineFilterPrime(5)
,FilterPrime(3)
的输出管道会作为FilterPrime(5)
的输入管道- 依次类推。。。
- 最终可以从管道
prime
中读取出素数,prime
管道每次读取,数字都会从Counter
产生,然后经过一层层过滤,最终将素数输出出来,并根据这个输出的素数,建立下一个FilterPrime
Goroutine。
从上面的分析中我们可以看出,如果我们想要获取前N个素数,那么就需要建立N+2个 Goroutine 和N+1个 Channel 。故其空间复杂度为O(2N)。同时,整个程序的流程就是Counter
产生数字,然后经历一个一个的FilterPrime
,最终将素数过滤出来,整个循环只进行一次,所以时间复杂度为O(M),其中M表示第N个素数的值。