利用 goroutine 和通道实现自上而下的树构建功能

有志者，事竟成！如果你在学习Golang，那么本文《利用 goroutine 和通道实现自上而下的树构建功能》，就很适合你！文章讲解的知识点主要包括，若是你对本文感兴趣，或者是想搞懂其中某个知识点，就请你继续往下看吧~

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

现在我正在尝试实现并发树构建功能，算法非常简单 - 从上到下为每个节点添加 2 个子节点，然后为每个子节点执行相同的操作深度限制次。以下是非并发代码：

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^(深度-1)-1 个 goroutine，因此您可以在 main 中等待它们完成：

func main() {
 ...
  wg:=sync.waitgroup{}
  wg.add((1<<(depth-1))-1)
  addchildrentonode(&mainnode, 4, 0)
  wg.wait()
  ...

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

我想我终于知道如何实现它了。 @burak-serdar 的回答很有帮助。实际上，我们可以将整个 addchildrentonode 添加到等待组中，然后使用 lambda 仅运行 goroutine 中的下一层，而不是将整个 addchildrentonode 推送到 goroutine 池中。而且因为我们在这一层之前添加到等待组中，所以保证不会溢出“完成”值，因此当所有子级都填充时我们总是会退出。这是代码：

package main

import (
    "encoding/json"
    "fmt"
    "math/rand"
    "sync"
    "time"
)

type Node struct {
    Name     string
    Children []Node
}

func main() {
    rand.Seed(time.Now().UnixNano())

    mainNode := Node{"p", nil}
    var wg sync.WaitGroup

    AddChildrenToNode(&mainNode, 4, 0, &wg)
    wg.Wait()

    b, _ := json.MarshalIndent(mainNode, "", "  ")
    fmt.Println(string(b)) // print as json
}

func AddChildrenToNode(node *Node, depthLimit int, curDepth int, wg *sync.WaitGroup) {
    curDepth++
    if curDepth >= depthLimit {
        return // reached depth limit
    }

    // Dynamic children count
    cN := rand.Intn(5)
    for i := 0; i <= cN; i++ {
        node.Children = append(node.Children, Node{node.Name + "-l", nil})
    }

    //node.Children = []Node{}

    time.Sleep(500 * time.Millisecond) // imitating hard work c:

    for idx, _ := range node.Children {
        fmt.Println(".")
        wg.Add(1) // it will always lag behind the next done so the flow wont be broken
        go func(idx int) {
            AddChildrenToNode(&node.Children[idx], depthLimit, curDepth, wg) // run this for every created child, recursively
            wg.Done()
        }(idx)
    }
}

终于介绍完啦！小伙伴们，这篇关于《利用 goroutine 和通道实现自上而下的树构建功能》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布Golang相关知识，快来关注吧！