英文:
How can I spawn go routines that depend on their predecessors?
问题
举个例子,假设我想填充这个矩阵:
| 0 | 0 | 0 | 0 |
| 0 | 1 | 2 | 3 |
| 0 | 2 | 3 | 4 |
| 0 | 3 | 4 | 5 |
具体来说,我想要填充的规则是,每个单元格的值都比它的上方、左方和左上方邻居的值中的最大值大1。
因为每个单元格只有三个依赖项(它的上方、左方和左上方邻居),我可以填充位于 m[1][1]
(即数字 1
)的单元格,一旦它被填充,我就可以填充标记为 2
的单元格,因为它们的所有依赖项都已经被填充。
| 0 | 0 | 0 | 0 | | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | ---\ | 0 | 1 | 2 | 0 |
| 0 | 0 | 0 | 0 | ---/ | 0 | 2 | 0 | 0 |
| 0 | 0 | 0 | 0 | | 0 | 0 | 0 | 0 |
如何启动1个go例程,然后2个,然后3个,然后4个...,以填充这个矩阵的每个对角线?更具体地说,如何在开始依赖单元格之前等待邻居完成?
[编辑]:感谢你的评论,@Zippoxer!为了澄清,我想知道在Go语言中运行一个依赖于另一个例程完成的例程的语法是什么。因为当一个例程完成时,可以启动多个新的例程,所以不能简单地调用函数而没有并发!
英文:
Say for example that I want to populate this matrix:
| 0 | 0 | 0 | 0 |
| 0 | 1 | 2 | 3 |
| 0 | 2 | 3 | 4 |
| 0 | 3 | 4 | 5 |
Specifically, I want to populate it so that each cell follows the rule,
In english, a cell's value is one greater than the maximum of its top
, left
, and topleft
neighbors' values.
Because each cell only has three dependencies (its top
, left
, and topleft
neighbors), I can populate the cell at m[1][1]
(the 1
), and once that's populated, I can populate the cells marked 2
as all of their dependencies are already populated.
| 0 | 0 | 0 | 0 | | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | ---\ | 0 | 1 | 2 | 0 |
| 0 | 0 | 0 | 0 | ---/ | 0 | 2 | 0 | 0 |
| 0 | 0 | 0 | 0 | | 0 | 0 | 0 | 0 |
How can I spin up 1 go routine, then 2, then 3, then 4..., to populate each diagonal of this matrix? Perhaps more specifically, how can I wait on the neighbors to finish before beginning the dependent cell?
[EDIT]: Thanks for the comment, @Zippoxer! To clarify, I'm asking what the syntax is in Go to run a go-routine that depends on another finishing first. Because multiple new go-routines can start when just one go-routine finishes, it's not as simple as just calling things without concurrency!
答案1
得分: 2
希望这只是一个人为的例子,因为这绝对不是最快的解决方案,但也许这正是你想要的。
每个单元格在自己的goroutine中运行,并拥有自己的通道,大致表示其依赖关系。一旦一个单元格从其通道中读取了三个值,它就知道其依赖关系已经全部解决。当一个单元格完成时,它会将某个值传递给所有依赖项的通道。
import "sync"
type empty struct{}
func contrivedMathThing(i, j int) [][]int {
var wg sync.WaitGroup
wg.Add(i * j)
// 为goroutine等待的通道和每个单元格的结果创建二维切片。
// 创建二维切片有点麻烦,但我认为这样做可以更清楚地说明问题。
chans := make([][]chan empty, i)
results := make([][]int, i)
for a := 0; a < i; a++ {
chans[a] = make([]chan empty, j)
results[a] = make([]int, j)
for b := 0; b < j; b++ {
chans[a][b] = make(chan empty, 3)
}
}
for a := 0; a < i; a++ {
for b := 0; b < j; b++ {
go func(a, b int, waitc <-chan empty) {
defer wg.Done()
// 等待所有依赖项完成
<-waitc
<-waitc
<-waitc
// 计算结果
// 懒得写...
// 将结果保存到结果数组中
results[a][b] = result
// 通知所有依赖项,其中一个依赖项已解决
if a < i-1 {
chans[a+1][b] <- empty{}
}
if b < j-1 {
chans[a][b+1] <- empty{}
}
if a < i-1 && b < j-1 {
chans[a+1][b+1] <- empty{}
}
}(a, b, chans[a][b])
}
}
// 第一行和第一列中的所有单元格都需要开始时满足两个依赖项。
for a := 1; a < i; a++ {
chans[a][0] <- empty{}
chans[a][0] <- empty{}
}
for b := 1; b < j; b++ {
chans[0][b] <- empty{}
chans[0][b] <- empty{}
}
// 解除[0][0]位置的单元格的阻塞,以便开始计算
close(chans[0][0])
wg.Wait()
return results
}
以上是给定的代码的翻译。
英文:
Hopefully this is a contrived example, because this is definitely not the fastest solution, but maybe it's what you want.
Each cell runs in its own goroutine and has its own channel, roughly representing its dependencies. A cell knows its dependencies have all resolved once it's read three values from its channel. When a cell completes, it passes some value to the channels of all of its dependents.
import "sync"
type empty struct{}
func contrivedMathThing(i, j int) ([][]int) {
var wg sync.WaitGroup
wg.Add(i * j)
// Make two-dimensional slices for the channels that the goroutines will
// wait on, and for the results of each cell. Two dimensional slices are
// more annoying to make, but I think make the example a bit more clear.
chans := make([][]chan empty, i)
results := make([][]int, i)
for a := 0; a < i; a++ {
chans[a] = make([]chan empty, j)
results[a] = make([]int, j)
for b := 0; b < j; b++ {
chans[a][b] = make(chan empty, 3)
}
}
for a := 0; a < i; a++ {
for b := 0; b < j; b++ {
go func(a, b int, waitc <-chan empty) {
defer wg.Done()
// Wait for all dependencies to complete
<-waitc
<-waitc
<-waitc
// Compute the result
// Too lazy to write...
// Save the result to the results array
results[a][b] = result
// Signal all dependents that one of their dependencies has
// resolved
if a < i - 1 {
chans[a + 1][b] <- empty{}
}
if b < j - 1 {
chans[a][b + 1] <- empty{}
}
if a < i - 1 && b < j - 1 {
chans[a + 1][b + 1] <- empty{}
}
}(a, b, chans[a][b])
}
}
// All cells in the first row and first column need to start out with two
// of their dependencies satisfied.
for a := 1; a < i; a++ {
chans[a][0] <- empty{}
chans[a][0] <- empty{}
}
for b := 1; b < j; b++ {
chans[0][b] <- empty{}
chans[0][b] <- empty{}
}
// Unblock the cell at [0][0] so this show can get started
close(chans[0][0])
wg.Wait()
return results
}
答案2
得分: 1
使用通道。
一个goroutine等待另一个goroutine:
done := make(chan bool)
go func() {
// 工作...
done <- true // 发送信号表示我们完成了。
}()
go func() {
<-done // 等待前一个goroutine发出信号。
// 工作...
}()
英文:
Use channels.
A goroutine waiting on another goroutine:
done := make(chan bool)
go func() {
// Work...
done <- true // Signal we're done.
}()
go func() {
<- done // Wait for the previous goroutine to signal.
// Work...
}()
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论