新手问一个 Golang Go语言中实现并发素数筛的问题

发布于 1周前 作者 h691938207 来自 Go语言
func Filter(in <-chan int, out chan<- int, prime int) {
	for {
		i := <-in
		if i%prime != 0 {
			out <- i
		}
	}
}

func Generate(ch chan<- int) { for i := 2; ; i++ { ch <- i } }

func main() { ch := make(chan int) go Generate(ch) // print the first 10 prime numbers for i := 0; i < 10; i++ { prime := <-ch println("next prime = ", prime) ch1 := make(chan int) go Filter(ch, ch1, prime) ch = ch1 } }


func Filter(in <-chan int, out chan<- int, prime int) {
	for {
		i := <-in
		if i%prime != 0 {
			out <- i
		}
	}
}

func main() { ch := make(chan int) go func() { for i := 2; ; i++ { ch <- i } }()

for i := 0; i &lt; 10; i++ {
	prime := &lt;-ch
	println("next prime = ", prime)
	ch1 := make(chan int)
	go Filter(ch, ch1, prime)
	ch = ch1
}

}

运行后发现上面的代码可以实现并发素数筛的功能, 但是下面的闭包写法就不行, 有没有大佬解释一下?


新手问一个 Golang Go语言中实现并发素数筛的问题

更多关于新手问一个 Golang Go语言中实现并发素数筛的问题的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html

10 回复

😅 func Filter(in int, out int, prime int) PLEASE!!!

更多关于新手问一个 Golang Go语言中实现并发素数筛的问题的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


go func(ch chan<- int) {
for i := 2; ; i++ {
ch <- i
}
}(ch)

ch = ch1
这行导致的

。。这写法

这样确实是可以的, 但是我想问的其实是原来错误的写法里, 闭包内部的这个 ch 的生命周期到底是什么样的😂

顺便说一下, 源代码来自 rob pike 的一次分享:

<iframe src="https://www.youtube.com/embed/sX8r6zATHGU" class="embedded_video" allowfullscreen="" type="text/html" id="ytplayer" frameborder="0"></iframe>
&t=821s

以及可以在 reddit 上的这个回答查看正确版本的详细数据流分析: https://www.reddit.com/r/golang/comments/434zry/help_understanding_this_prime_sieve_concurrent/

这应该单纯是个闭包问题:

1. ch 变量本质上是个 *hchan ( https://github.com/golang/go/blob/ed035af7b7d7c1cd2e6f852e22a9b04fc2a2cc65/src/runtime/chan.go#L34 ),是指向 make(chan int) 也就是 runtime.makechan 创建的 hchan 的指针。

2. 直接使用闭包引用 ch ,ch 发生了内存逃逸(因为是 go func ,我 -gcflags="-m" 看了下确实逃逸到了堆),你在闭包 go func 中使用 ch ,就是在操作 ch 指向的 hchan 。

3. main 函数后续 ch = ch1 , 也就是 ch 指向了原本 ch1 指向的 hchan ,导致 go func 操作的 hchan 也发生了变化,进而整体程序没有按照预期执行。

4. 而正确的实现 Generate(ch),以及 func(ch){…}(ch) ,是函数传参,是将 ch 变量值复制传入到了 Generate 或者 go func 里。

如果你去看汇编,这次 ch 就分配在栈里( main.ch+40(SP) ),在运行 go func 之前就把它的值复制到寄存器里供函数使用了 ( MOVQ main.ch+40(SP), CX )。因此后续 main 里 ch 针对 hchan 的指向发生变化不会影响 go func 内部,值复制保证 go func 内部指向的 hchan 不变。


感兴趣自己可以看下汇编研究下,我也只是大致看了下:go tool compile -S main.go > assembly.s

👍👍解释的很清楚

说起来这个 Rob Pike 的素数筛法应该思路就是当年 CSP 1978 这篇论文提到的素数算法,以前欧长坤老板做过 CSP 1978 论文解读的分享,里面就有素数筛法的例子,论文当然是自己的 CSP 语言,而他写了个 Go 版本:
https://github.com/changkun/pkg/blob/f787593b4467793f8ee0b07583ea9ffde5adf2be/csp/csp.go#L833

#8 https://swtch.com/~rsc/thread/ 补充下 Russ Cox 的文章 顺便提一嘴 xv6 有个实验就是实现这样的素数筛

在Go语言中实现并发素数筛(如埃拉托斯特尼筛法)是一个经典的并发编程练习。以下是一个简要的思路和实现方法:

  1. 基本思路

    • 使用一个布尔数组来标记每个数是否为素数。
    • 从2开始,将每个素数的倍数标记为非素数。
    • 通过并发来加速这个过程,可以分配不同的范围给不同的goroutine来处理。
  2. 实现步骤

    • 初始化一个足够大的布尔数组,默认所有数都为素数。
    • 创建一个channel用于同步,确保所有goroutine完成后才输出结果。
    • 划分范围,启动多个goroutine,每个goroutine负责一部分数字,将其中的非素数标记出来。
    • 使用互斥锁(sync.Mutex)来保护对布尔数组的并发访问,避免数据竞争。
    • 所有goroutine完成后,遍历布尔数组,输出所有标记为素数的数字。
  3. 注意事项

    • 并发粒度要适中,避免过多的上下文切换开销。
    • 合理使用互斥锁,尽量减少锁的竞争。
    • 考虑使用更高效的数据结构或算法,如位数组(bitmap)来存储素数状态,以减少内存占用。

通过上述方法,你可以在Go语言中实现一个高效的并发素数筛。这不仅是对Go语言并发特性的一个实践,也是对算法优化的一次尝试。希望这个回答对你有所帮助!

回到顶部