在 Go Tour 等效二叉树上使用多个 Goroutine

Question

当尝试解决 Go Tour 中“等效二叉树”问题的树行走部分时，显而易见的解决方案是使用“递归”。关于如何解决问题的一般问题的答案中提供了其他解决方案，例如闭包。 我最初的想法是为步行的每一步使用 Goroutine。这不是一个更好、更 Go-onic（Pythonic 的 Go 等价物是什么？）的解决方案吗？问题是我不知道如何 A）在树行走后关闭通道，或 B）以其他方式发出树行走完成的信号。早期的示例使用 2 个通道，一个用于数据，一个用于退出信号。通过第二个通道不符合问题定义，并且步行何时完成的根本问题仍然存在。是否有一个优雅的解决方案，每个步行步骤都有一个 Goroutine，或者递归是最好的解决方案？

func Walk(t *tree.Tree, ch chan int) {
    if t != nil {
        go Walk(t.Left, ch)
        ch <- t.Value
        go Walk(t.Right, ch)
    }
    //Done with this node, how do I know when all are done?
}

对步行的每一步都使用 goroutine 是行不通的。完全除了不知道什么时候可以关闭通道（我不知道有什么好的解决方法）之外，你不能保证得到你想要的订单。例如下面的代码：

Answer 1

可以打印 123、132、213、231、312 或 321 中的任何一个，具体取决于调度程序选择如何运行这些 goroutine。这意味着您的

Walk

 实现将不再以正确的顺序为您提供值。

只有当你确实想要同时做某件事时，Goroutines 才是正确的答案；鉴于通道的输出必须严格排序，因此在此问题中无法利用并发性。

您可以使用

Answer 2

func internalWalk(t *tree.Tree, wg *sync.WaitGroup, ch chan int) {
    wg.Add(1)
    if t != nil {
        go Walk(t.Left, ch)
        ch <- t.Value
        go Walk(t.Right, ch)
    }
    wg.Done()
}
func Walk(t *tree.Tree, ch chan int) {
    var wg sync.WaitGroup
    internalWalk(t, &wg, ch)
    wg.Wait()
    //they are all done now, do something here
}

基于@OneOfOne的回答，我已经用

sync.WaitGroup

Answer 3

正如@Evan所说，这意味着结果是无序的，但我不清楚这些要求是否意味着您需要按特定顺序阅读它们。

package main

import "golang.org/x/tour/tree"
import "fmt"
import "sync"

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan <- int, wg *sync.WaitGroup){
    defer wg.Done()
    if t != nil {
        wg.Add(2)
        go Walk(t.Left, ch, wg)
        go Walk(t.Right, ch, wg)
        ch <- t.Value
    }
}

func Walking(t *tree.Tree, ch chan <- int){
    var wg sync.WaitGroup
    wg.Add(1)
    Walk(t, ch, &wg)
    defer close(ch)
    wg.Wait()
}

func readChannel(ch <- chan int){
    for i := range ch {
        fmt.Println(i)
    }
}

func main() {
    c := make(chan int)
    go Walking(tree.New(1), c)
    readChannel(c)
}

使用此方法时需要考虑以下一些事项：

在进入Walk()之前需要调用Add()。如果 Done() 在下一个 Add() 之前执行，工作组计数器将变为 0，并且 Wait() 将被“解锁”。

我们仍然需要关闭通道。执行此操作的时间是在 waitGroup 完成之后。