go - 利用goroutines和channel进行从上到下的树构建功能

Question

我是golang和 channel /goroutines的新手，但我了解概念和简单用法。

现在，我正在尝试实现并发树构建功能，该算法非常简单-从上至下为每个节点添加2个 child ，然后为每个 child 执行相同的操作 depthLimit 次。这是非一致代码的代码:

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。问题是我们实际上不知道何时“ build ”完成并发出阻塞/解除阻塞主体的信号。我想念什么吗？我也尝试过使用sync.WaitingGroup。

Answer 1

可以将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 goroutine，因此您可以在main中等待它们完成:

func main() {
 ...
  wg:=sync.WaitGroup{}
  wg.Add((1<<(depth-1))-1)
  AddChildrenToNode(&mainNode, 4, 0)
  wg.Wait()
  ...

还有其他方法可以完成，例如为左右节点添加一个goroutine。