从素数筛算法看 Golang 并发模式

Golang
2022年2月11日 11:56

常规方式求解素数

如何判断一个数字是否为素数？最简单的迭代解法：

func isPrime(n int) bool {
    for i := 2; i*i <= n; i++ {
        if n % i == 0 {
            return false
        }
    }
    return true
}

如果要生成 100 个素数，这个算法就太低效

素数筛法

素数筛法基于这样的思想：从最小的素数 2 开始，依次剔除 2 的倍数，再依次剔除 3 的倍数，依次剔除 5 的倍数...每次都是以素数的倍数来剔除元素

素数筛流程：
prime-filter-flow

根据这样的思想，可以编写算法：

// 筛选 [0, n] 之间所有的素数
func PrimeFilte(n int) []int {
    pmark := make([]int, n+1)    // 多申请一个，让下标能对应到素数
    pmark[0], pmark[1] = 0, 0
    for i := 2; i <= n; i++ {
        pmark[i] = 1
    }
    for i := 2; i <= n; i++ {
        if pmark[i] == 1 {    // 改进之处，用素数来筛选
            for j := 2 * i; j <= n; j += i {    
                pmark[j] = 0
            }
    }
    var ret []int
    for i := 2; i <= n; i++ {
        if pmark[i] == 1 {
            ret = append(ret, i)
        }
    }
    return ret
}

并发素数筛

在《Go 语言高级编程》一书中，作者提到了并发素数筛，这个算法能比较好的体现 Golang 的并发思想，Golang 借鉴了 CSP 模型的两个概念：并发执行体和通道，即 goroutine 和 channel，实现了一个比较高效的并发素数筛，原版在函数体内部生成 chan，没有体现出串联效果，这里给出一个修改版（不考虑安全退出的处理，只展现核心逻辑）：

package main

// 生成器，不断产生大于 2 的自然数
func Generate(ch chan<- int) {
    for i := 2; ; i++ {
        ch <- i
    }
}

// 过滤器，将过滤不掉的数据发往下一个过滤器
func Filter(in <-chan int, out chan<- int, prime int) {
    for {
        i := <-in
        if i % prime != 0 {    // 当前过滤器未过滤掉，则发往下一个过滤器
            out <- i
        }
    }
}

func main() {
    var ret []int
    ch := make(chan int)
    go Generate(ch)    // 启动生成器，不断往 0 级 chan 投送自然数
    for i := 0; i <= 100; i++ {
        prime := <-ch
        ret = append(ret, prime)
        out := make(chan int)    // 新生成一个通道
        go Filter(ch, out, prime)
        ch = out
    }
}

这段代码实际形成了下面的模型，类似于 Unix 中的管道：
prime-filter-structure

这样就很好理解了。

有几个关键点值得注意：

  • 所有 channel 为无缓冲通道，在 goroutine 间做同步通信
  • 初始 channel 由生成器创建，用于不断传送新的自然数
  • Filter 将 channel 和 goroutine 前后串联了起来
  • 每次循环都生成一个新的 goroutine，这个 goroutine 以新生成的 prime 为过滤条件
  • 被某一级过滤器过滤掉的自然数，将不会发送到下一级 channel
  • 每一个 goroutine 都是无限循环，除非主 goroutine 退出，否则不会停止工作
  • channel 中的数据被下一级 goroutine 取出后，立即被上一级 goroutine 传入数据

这个算法比较好的体现了 Golang 的并发编程哲学：不要通过共享内存来通信，而应该通过通信来共享内存。

参考资料：

  1. 《Go语言高级编程》—— 柴树杉 / 曹春晖

Golang