Go语言

Go语言中存在着一种名为通道(channel)的类型，是一种用来在goroutine之间传递数据的通信机制。

求取素数

这里我们打算求1~N之间的素数，算法是判断每个数是不是素数（而不用筛法）。但是当N（比如10000）较大时，这样会很慢，那我们可以开启多个协程，同时进行计算。

判断素数

经典算法从2模到p的平方根。

1
2
3
4
5
6
7
8
9
10
11
func isPrime(p int) bool {
	if p == 1 {
		return false
	}
	for i := 2; i < int(math.Sqrt(float64(p))); i++ {
		if p%2 == 0 {
			return false
		}
	}
	return true
}

如何开启多个协程

我们想开启多个协程来判断素数，那么其中一种方法就是把1~10000分成几份，然后把这几份数据分给每个协程进行计算。但这么做显然有个缺点，我们不知道到底该怎么分才能使每个协程的计算量大致相同。通过计算时间复杂度再去分配或许是可行的，但不够优雅。我们希望的是一堆数字就摆放在那里，然后每个协程每次都可以从那里取走一个数字进行判断，直到把所有的数字都判断完成。

我们可以使用一个通道来存储这些数据，用循环把每个数字放进去，而且还可以为这个函数单独开一个协程，实现一边往里存放数据，一边从里面拿去数据进行判断。在下文函数的形参中，intChan用来存放1~10000的数据primeChan用来存放素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func putNum(intChan chan int) {
	for i := 2; i < 10000; i++ {
		intChan <- i
	}
}

func primeNum(intChan chan int, primeChan chan int) {
	for num := range intChan {
		if isPrime(num) == true {
			primeChan <- num
		}
	}
}

func printPrime(primeChan chan int) {
	for v = range primeChan {
		fmt.Printf("v: %v\n", v)
	}
	wg.Done()
}

关闭通道的时机

到了这一步还不够，因为我们使用的是for range的方式访问的通道中的数据，所以最后还要把通道关闭。至于关闭的时机，数据存入完毕以后就可以关闭通道，关闭通道后依然可以从通道中读取数据，但不能再存入数据。对于intChan来说，我们可以直接在函数中存入数据以后关闭通道。但对于primeChan，我们不能直接在函数里关闭通道，因为这个函数被开了很多个协程，如果其中一个完成的工作，而其他的还没算完，那么会导致通道提前关闭，少存入最后几个素数。

这里提供一种解决思路，设定一个全局变量count=16(协程数)，每当一个primeNum协程结束时，count–，减到0时，就关闭通道，并跳出循环。下面代码用了一个死循环来监测count的状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func closeChan(primeChan chan int) {
	for {
		if count == 0 {
			close(primeChan)
			break
		}
	}
}

func primeNum(intChan chan int, primeChan chan int) {
	for num := range intChan {
		if isPrime(num) == true {
			primeChan <- num
		}
	}
    // 能执行到这一步说明intChan中已经没有数据了。
	count--
}

不过，到这一步还是不够，还是因为我们开启了多个协程，在执行primeNum中的count–时，有可能出现竞争。比如count=16时，有两个协程同时要执行count–，其中一个拿到count=16的数据，进行count–以后变成了count=15,而另一个协程同样是拿到count=16的数据，count–以后还是15。这样，本该为count=14的结果变成了count=15，那么count就不可能再减到0，循环就会真的变成死循环。

这时，我们需要给count–这一段加上一个互斥锁，以确保当有一个协程在执行count–操作时，不会有别的协程来竞争。

1
2
3
4
5
6
7
8
9
10
11
func primeNum(intChan chan int, primeChan chan int) {
	for num := range intChan {
		if isPrime(num) == true {
			primeChan <- num
		}
	}
	mutex.Lock()
	count--
	fmt.Printf("count: %v\n", count)
	mutex.Unlock()
}

以下是完整代码，我们还可以记录一下时间戳来计算耗时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package main

import (
	"fmt"
	"math"
	"sync"
	"time"
)

func isPrime(p int) bool {
	if p == 1 {
		return false
	}
	for i := 2; i < int(math.Sqrt(float64(p))); i++ {
		if p%2 == 0 {
			return false
		}
	}
	return true
}

var wg sync.WaitGroup
var count int = 16
var mutex sync.Mutex

func putNum(intChan chan int) {
	for i := 2; i < 100000; i++ {
		intChan <- i
	}
	close(intChan)
	wg.Done()
}

func primeNum(intChan chan int, primeChan chan int) {
	for num := range intChan {
		if isPrime(num) == true {
			primeChan <- num
		}
	}
	mutex.Lock()
	count--
	mutex.Unlock()
	wg.Done()
}

func printPrime(primeChan chan int) {
	for _ = range primeChan {  //这里使用_是因为数据太多就不打印了。
		// fmt.Printf("v: %v\n", v)
	}
	wg.Done()
}

func closeChan(primeChan chan int) {
	for {
		if count == 0 {
			close(primeChan)
			break
		}
	}
	wg.Done()
}

func main() {
	start := time.Now().UnixMilli()
	intChan := make(chan int, 10000)
	primeChan := make(chan int, 10000)
	wg.Add(1)
	go putNum(intChan)
	for i := 0; i < 16; i++ {
		wg.Add(1)
		go primeNum(intChan, primeChan)
	}
	wg.Add(1)
	go closeChan(primeChan)
	wg.Add(1)
	go printPrime(primeChan)
	wg.Wait()
	end := time.Now().UnixMilli()

	fmt.Printf("start: %v\n", start)
	fmt.Printf("end: %v\n", end)

	fmt.Printf("\"time\": %v\n", end-start)
}