go - 利用 goroutine 和通道实现自上而下的树构建功能
问题描述
我是 golang 和通道/goroutines 的新手,但我了解概念和简单用法。
现在我正在尝试实现并发树构建功能,算法非常简单 - 从上到下为每个节点添加 2 个子节点,然后为每个子节点执行相同的操作depthLimit times。这是非并发的代码:
package main
import (
"encoding/json"
"fmt"
"time"
)
type Node struct {
Name string
Children []Node
}
func main() {
mainNode := Node{"p", nil}
AddChildrenToNode(&mainNode, 4, 0)
b, _ := json.MarshalIndent(mainNode, "", " ")
fmt.Println(string(b)) // print as json
}
func AddChildrenToNode(node *Node, depthLimit int, curDepth int) {
curDepth++
if curDepth >= depthLimit {
return // reached depth limit
}
time.Sleep(500 * time.Millisecond) // imitating hard work c:
fmt.Print(".") // status indicator
// add children
node.Children = []Node{
Node{node.Name + "-l", nil},
Node{node.Name + "-r", nil},
}
for idx, _ := range node.Children {
AddChildrenToNode(&node.Children[idx], depthLimit, curDepth) // run this for every created child, recursively
}
}
但是现在我面临为 goroutine 的使用而重写它的困难。问题是我们实际上无法知道“构建”何时完成并发出阻塞/解除阻塞 main 的信号。我错过了什么吗?我也尝试过玩sync.WaitingGroup。
解决方案
将 goroutine 引入该算法的一种方法是使用单独的 goroutine 来添加子节点,假设在完成“艰苦工作”部分之前您无法真正添加这些子节点。
func AddChildrenToNode(node *Node, wg *sync.WaitGroup,depthLimit int, curDepth int) {
// work
go func() {
defer wg.Done()
node.Children = []Node{
Node{node.Name + "-l", nil},
Node{node.Name + "-r", nil},
}
for idx, _ := range node.Children {
AddChildrenToNode(&node.Children[idx], depthLimit, curDepth) // run this for every created child, recursively
}
}()
}
使用此方案,您最终会创建 2^(depth-1)-1 goroutines,因此您可以在 main 中等待它们完成:
func main() {
...
wg:=sync.WaitGroup{}
wg.Add((1<<(depth-1))-1)
AddChildrenToNode(&mainNode, 4, 0)
wg.Wait()
...
还有其他方法可以做到这一点,比如为左右节点添加一个 goroutine。
推荐阅读
- javascript - 如何在情节中为颜色条设置不均匀的刻度值
- python - pandas - 筛选在 groupby 中至少有一列包含非空值的组
- julia - 如何对 Julia 进行多重插补?
- forms - Symfony 4 表单处理
- three.js - 物体可以隐藏在其他透明物体后面吗?
- python - 读取文件并匹配多行
- python-3.x - Python 计算前导和尾随空格
- docker - docker如何连接到外部DNS
- performance - ff4j 和 togglz 之间的性能比较
- java - Java MySQLSyntaxErrorException?为什么我的 SELECT 语句不正确?