## 4.13\. 生成素数
这里我们要给出一个并行处理程序及之间的通信。这是一个非常大的课题,我们这里只是给出一些要点。
素数筛选是一个比较经典的问题(这里侧重于Eratosthenes素数筛选算法的并行特征)。它以全部的 自然后为筛选对象。首选从第一个素数2开始,后续数列中是已经素数倍数的数去掉。每次筛选可以得到 一个新的素数,然后将新的素数加入筛选器,继续筛选后面的自然数列(这里要参考算法的描述调整)。
这里是算法工作的原理图。每个框对应一个素数筛选器,并且将剩下的数列传给下一个素数筛进行筛选。
![](https://golang-china.googlecode.com/svn/trunk/Chinese/golang.org/img/sieve.gif)
为了产生整数序列,我们使用管道。管道可以用于连接两个并行的处理单。在Go语言中, 管道由运行时库管理,可以用"make"来创建新的管道。
这是"progs/sieve.go"程序的第一个函数:
```
09 // Send the sequence 2, 3, 4, ... to channel 'ch'.
10 func generate(ch chan int) {
11 for i := 2; ; i++ {
12 ch <- i // Send 'i' to channel 'ch'.
13 }
14 }
```
函数"generate"用于生成2, 3, 4, 5, ...自然数序列,然后依次发送到管道。 这里用到了二元操作符"<-", 它用于向管道发送数据。当管道没有接受者的时候 会阻塞,直到有接收者从管道接受数据为止。
过滤器函数有三个参数:输入输出管道和用于过滤的素数。当输入管道读出来的数不能被 过滤素数整除时,则将当前整数发送到输出管道。这里用到了"<-"操作符,它用于从 管道读取数据。
```
16 // Copy the values from channel 'in' to channel 'out',
17 // removing those divisible by 'prime'.
18 func filter(in, out chan int, prime int) {
19 for {
20 i := <-in // Receive value of new variable 'i' from 'in'.
21 if i % prime != 0 {
22 out <- i // Send 'i' to channel 'out'.
23 }
24 }
25 }
```
整数生成器generator函数和过滤器filters是并行执行的。Go语言有自己的并发 程序设计模型,这个和传统的进程/线程/轻量线程类似。为了区别,我们把Go语言 中的并行程序称为goroutines。如果一个函数要以goroutines方式并行执行, 只要用"go"关键字作为函数调用的前缀即可。goroutines和它的启动线程并行执行, 但是共享一个地址空间。例如,以goroutines方式执行前面的sum函数:
```
go sum(hugeArray); // calculate sum in the background
```
如果想知道计算什么时候结束,可以让sum用管道把结果返回:
```
ch := make(chan int);
go sum(hugeArray, ch);
// ... do something else for a while
result := <-ch; // wait for, and retrieve, result
```
再回到我们的素数筛选程序。下面程序演示如何将不同的素数筛链接在一起:
```
28 func main() {
29 ch := make(chan int) // Create a new channel.
30 go generate(ch) // Start generate() as a goroutine.
31 for {
32 prime := <-ch
33 fmt.Println(prime)
34 ch1 := make(chan int)
35 go filter(ch, ch1, prime)
36 ch = ch1
37 }
38 }
```
29行先调用"generate"函数,用于产生最原始的自然数序列(从2开始)。然后 从输出管道读取的第一个数为新的素数,并以这个新的素数生成一个新的过滤器。 然后将新创建的过滤器添加到前一个过滤器后面,新过滤器的输出作为新的输出 管道。
sieve程序还可以写的更简洁一点。这里是"generate"的改进,代码在 "progs/sieve1.go"中:
```
10 func generate() chan int {
11 ch := make(chan int)
12 go func(){
13 for i := 2; ; i++ {
14 ch <- i
15 }
16 }()
17 return ch
18 }
```
新完善的generate函数在内部进行必须的初始化操作。它创建输出管道,然后 启动goroutine用于产生整数序列,最后返回输出管道。它类似于一个并发程序 的工厂函数,完成后返回一个用于链接的管道。
第12-16行用go关键字启动一个匿名函数。需要注意的是,generate函数的"ch" 变量对于匿名函数是可见,并且"ch"变量在generate函数返回后依然存在(因为 匿名的goroutine还在运行)。
这里我们采用过滤器"filter"来筛选后面的素数:
```
21 func filter(in chan int, prime int) chan int {
22 out := make(chan int)
23 go func() {
24 for {
25 if i := <-in; i % prime != 0 {
26 out <- i
27 }
28 }
29 }()
30 return out
31 }
```
函数"sieve"对应处理的一个主循环,它只是依次将数列交给后面的素数筛选器进行筛选。 如果遇到新的素数,再输出素数后以该素数创建信的筛选器。
```
33 func sieve() chan int {
34 out := make(chan int)
35 go func() {
36 ch := generate()
37 for {
38 prime := <-ch
39 out <- prime
40 ch = filter(ch, prime)
41 }
42 }()
43 return out
44 }
```
主函数入口启动素数生成服务器,然后打印从管道输出的素数:
```
46 func main() {
47 primes := sieve()
48 for {
49 fmt.Println(<-primes)
50 }
51 }
```
- 1. 关于本文
- 2. Go语言简介
- 3. 安装go环境
- 3.1. 简介
- 3.2. 安装C语言工具
- 3.3. 安装Mercurial
- 3.4. 获取代码
- 3.5. 安装Go
- 3.6. 编写程序
- 3.7. 进一步学习
- 3.8. 更新go到新版本
- 3.9. 社区资源
- 3.10. 环境变量
- 4. Go语言入门
- 4.1. 简介
- 4.2. Hello,世界
- 4.3. 分号(Semicolons)
- 4.4. 编译
- 4.5. Echo
- 4.6. 类型简介
- 4.7. 申请内存
- 4.8. 常量
- 4.9. I/O包
- 4.10. Rotting cats
- 4.11. Sorting
- 4.12. 打印输出
- 4.13. 生成素数
- 4.14. Multiplexing
- 5. Effective Go
- 5.1. 简介
- 5.2. 格式化
- 5.3. 注释
- 5.4. 命名
- 5.5. 分号
- 5.6. 控制流
- 5.7. 函数
- 5.8. 数据
- 5.9. 初始化
- 5.10. 方法
- 5.11. 接口和其他类型
- 5.12. 内置
- 5.13. 并发
- 5.14. 错误处理
- 5.15. Web服务器
- 6. 如何编写Go程序
- 6.1. 简介
- 6.2. 社区资源
- 6.3. 新建一个包
- 6.4. 测试
- 6.5. 一个带测试的演示包
- 7. Codelab: 编写Web程序
- 7.1. 简介
- 7.2. 开始
- 7.3. 数据结构
- 7.4. 使用http包
- 7.5. 基于http提供wiki页面
- 7.6. 编辑页面
- 7.7. template包
- 7.8. 处理不存在的页面
- 7.9. 储存页面
- 7.10. 错误处理
- 7.11. 模板缓存
- 7.12. 验证
- 7.13. 函数文本和闭包
- 7.14. 试试!
- 7.15. 其他任务
- 8. 针对C++程序员指南
- 8.1. 概念差异
- 8.2. 语法
- 8.3. 常量
- 8.4. Slices(切片)
- 8.5. 构造值对象
- 8.6. Interfaces(接口)
- 8.7. Goroutines
- 8.8. Channels(管道)
- 9. 内存模型
- 9.1. 简介
- 9.2. Happens Before
- 9.3. 同步(Synchronization)
- 9.4. 错误的同步方式
- 10. 附录
- 10.1. 命令行工具
- 10.2. 视频和讲座
- 10.3. Release History
- 10.4. Go Roadmap
- 10.5. 相关资源