利用管道和协程求素数

￡神魔★判官ぃ 2021-07-24 13:23 516阅读 0赞

# 一 需求 #

统计 1-300000 的数字中，哪些是素数？要求使用 goroutine 和 channel 完成。

# 二 分析 #

传统的方法，就是使用一个循环，循环的判断各个数是不是素数。

使用并发/并行的方式，将统计素数的任务分配给多个(4个)goroutine 去完成，完成任务时间短。

# 三 图解 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

# 四 代码 #

package main
    
    import (
       "fmt"
       "time"
    )
    
    // 向 intChan放入 1-300000 个数
    func putNum(intChan chan int) {
       for i := 1; i <= 300000; i++ {
          intChan <- i
       }
       // 关闭intChan
       close(intChan)
    }
    
    // 从 intChan 取出数据，并判断是否为素数,如果是，就放入到primeChan
    func primeNum(intChan chan int, primeChan chan int, exitChan chan bool) {
       var flag bool
       for {
          // time.Sleep(time.Millisecond * 10)
          num, ok := <-intChan
          if !ok {
             break
          }
          flag = true // 假设是素数
          // 判断 num 是不是素数
          for i := 2; i < num; i++ {
             if num%i == 0 { // 说明该 num 不是素数
                flag = false
                break
             }
          }
    
          if flag {
             // 将这个数就放入到 primeChan
             primeChan <- num
          }
       }
    
       fmt.Println("有一个 primeNum 协程因为取不到数据，退出")
       // 这里我们还不能关闭 primeChan
       // 向 exitChan 写入true
       exitChan <- true
    }
    
    
    func main() {
       intChan := make(chan int, 1000)
       primeChan := make(chan int, 150000) // 放入结果
       // 标识退出的管道
       exitChan := make(chan bool, 4) // 4个
       start := time.Now().Unix()
       // 开启一个协程，向 intChan放入 1-300000 个数
       go putNum(intChan)
       // 开启 4 个协程，从 intChan 取出数据，并判断是否为素数,如果是，就放入到 primeChan
       for i := 0; i < 4; i++ {
          go primeNum(intChan, primeChan, exitChan)
       }
    
       go func() {
          for i := 0; i < 4; i++ {
             <-exitChan
          }
          end := time.Now().Unix()
          fmt.Println("使用协程耗时=", end-start)
          // 当从 exitChan 取出了4个结果，就可以放心的关闭 prprimeChan
          close(primeChan)
       }()
    
       // 遍历 primeChan ,把结果取出
       for {
          _, ok := <-primeChan
          if !ok {
             break
          }
          // 将结果输出
          // fmt.Printf("素数=%d\n", res)
       }
       fmt.Println("main线程退出")
    }

# 五 测试 #

> 有一个 primeNum 协程因为取不到数据，退出
> 
> 有一个 primeNum 协程因为取不到数据，退出
> 
> 有一个 primeNum 协程因为取不到数据，退出
> 
> 有一个 primeNum 协程因为取不到数据，退出
> 
> 使用协程耗时= 5
> 
> main线程退出

# 六 传统方法代码 #

package main
    
    import (
       "fmt"
       "time"
    )
    
    func main() {
       start := time.Now().Unix()
       for num := 1; num <= 300000; num++ {
          flag := true //假设是素数
          // 判断num是不是素数
          for i := 2; i < num; i++ {
             if num%i == 0 { // 说明该 num 不是素数
                flag = false
                break
             }
          }
          if flag {
          }
       }
       end := time.Now().Unix()
       fmt.Println("普通的方法耗时=", end-start)
    }

# 七 传统方法测试 #

> 普通的方法耗时= 16

# 八 结论 #

使用 go 协程后，执行的速度，比普通方法提高提升4倍左右。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/6dcaf034fd304a73944514a856d0b3ee.png