英文:
Using multiple Goroutines on Go Tour Equivalent Binary Trees
问题
在尝试解决Go Tour中的等价二叉树问题中的树遍历部分时，显而易见的解决方案是使用递归。其他解决方案，比如使用闭包，可以在通用问题的答案中找到。
我最初的想法是为每一步遍历使用一个Goroutine。这难道不是更好的、更符合Go风格（Go中的Pythonic等价物是什么？）的解决方案吗？问题是，我无法弄清楚如何在树遍历完成后要么A)关闭通道，要么B)以其他方式发出信号。一个早期的示例使用了两个通道，一个用于数据，一个用于退出信号。传递第二个通道与问题定义不符，并且遍历完成的根本问题仍然存在。是否有一种优雅的解决方案，每个遍历步骤都使用一个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)
}
//完成了这个节点，我如何知道何时所有节点都完成了？
}
英文:
When attempting to solve tree walk portion of the Equivalent Binary Trees problem in the Go Tour, the obvious solution is to use recursion. Other solutions, such as a closure, are provided in answers to the general question on how to solve the problem.
My original thought was to use a Goroutine for each step of the walk. Isn't this a better, more Go-onic (what's the Go equivalent of Pythonic?) solution? The problem is I couldn't figure out how to either A) close the channel after the tree has been walked, or B) signal in some other way that the tree walk completed. An earlier example uses 2 channels, one for data and one for a quit signal. Passing a second channel doesn't fit with the problem definition, and the root issue of when the walk is finished is still present. Is there an elegant solution with a Goroutine for each walk step, or is recursion the best solution?
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?
}
1: http://tour.golang.org/#72 "Equivalent Binary Trees"
2: https://code.google.com/p/go-tour/source/browse/solutions/binarytrees.go
3: https://stackoverflow.com/questions/12224042/go-tour-exercise-equivalent-binary-trees
4: http://tour.golang.org/#69
答案1
得分: 1
使用goroutine来处理每一步的遍历是行不通的。除了不知道何时关闭通道（我不知道解决方法），你也无法保证得到你想要的顺序。例如，下面的代码：
go fmt.Println(1)
go fmt.Println(2)
go fmt.Println(3)
可能会打印出123、132、213、231、312或321中的任意一种，这取决于调度器选择如何运行这些goroutine。这意味着你的Walk实现将不再按正确的顺序给出值。
只有在确实有并发操作的情况下，goroutine才是正确的答案；鉴于通道的输出必须严格有序，这个问题中没有可以利用的并发操作。
英文:
Using a goroutine for each step of the walk will not work. Entirely apart from not knowing when you can close the channel (which I don't know of a good way to solve), you are not guaranteed to get the ordering you want. For example, the following code:
go fmt.Println(1)
go fmt.Println(2)
go fmt.Println(3)
Could print any of 123, 132, 213, 231, 312, or 321 depending on how the scheduler chooses to run those goroutines. This means that your Walk implementation is no longer going to give you the values in the correct order.
Goroutines are only the right answer when there is actually something you want to do concurrently; given that the output to the channel has to be strictly ordered there is no concurrency to exploit in this problem.
答案2
得分: 0
你可以使用sync.WaitGroup。
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()
// 现在它们都完成了，在这里做一些事情
}
以上是要翻译的内容。
英文:
You can use sync.WaitGroup
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
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论