时间戳

首页 > 解决方案 > 等价二叉树练习，实现“并发”

go - 等价二叉树练习，实现“并发”

问题描述

我正在解决A Tour of Go中的练习，等效二叉树。这个练习需要实现一个Walk函数，该函数应该遍历一棵树并将所有值从树有序地发送到通道。

演习声明指出：

... 我们将使用 Go 的并发和通道来编写一个简单的解决方案。

阅读该行，我认为以Walk一种为每个左/右子树启动一个 goroutine 并使其Walk比非并发版本运行得更快（关于时间复杂度）的方式来实现是具有挑战性的。让我用代码更详细地解释一下。

这是我早期的代码Walk：

func Walk(t *tree.Tree, ch chan int) {
    defer close(ch)
    if t == nil { return }
    
    lch, rch := make(chan int), make(chan int)
    go Walk(t.Left, lch)
    for v := range lch { ch <- v }

    ch <- t.Value

    go Walk(t.Right, rch)
    for v := range rch { ch <- v }

    return
}

它肯定使用 goroutines，但实际上与没有 goroutines 的遍历没有什么不同，因为 ealry 会for v := range lch { ... }延迟go Walk(t.Right, rch)直到结束。

向上移动没有任何区别go Walk(t.Right, rch)：

func Walk(t *tree.Tree, ch chan int) {
    defer close(ch)
    if t == nil { return }
    
    lch, rch := make(chan int), make(chan int)
    go Walk(t.Left, lch)
    go Walk(t.Right, rch)

    for v := range lch { ch <- v }
    ch <- t.Value
    for v := range rch { ch <- v }
}

一棵带有彩色节点的树

go Walk(t.Left, lch)沿着整个左子树（以蓝色为根）行走，并立即接收lch从中发送的值。

go Walk(t.Right, rch)也尝试走，但被阻塞，因为ch <- t.Value右子树的最左边节点（红色）这样做并传播阻塞。这种状态一直持续到for v := range rch { ch <- v }达到。

我的问题：如何以Walkgoroutines（对应左或右）ch <- t.Value尽可能避免被阻塞的方式实现？

标签： goconcurrency

解决方案

右子树中的值需要一个缓冲区（例如缓冲通道），因为它们必须持续存在，直到那些 (<-lch和t.Value) 之前的值被消耗掉。

为大小未知的子树准备缓冲区有几个含义

  • 如果使用缓冲通道 ，make(chan int, N)则选择N至关重要。如果N恰好对于子树来说太小，则子树的 goroutine 会很快阻塞。如果它太大，内存就会被不必要地浪费。
  • 使用自动调整缓冲区大小实现自定义通道可能是一种解决方案，但它会带来额外的复杂性和开销。我不知道惩罚是否会抵消性能提升。这取决于自定义通道如何管理其内部缓冲区或如何管理这些缓冲区。

在我看来，对于这种“遍历一个随机的、未知的树，并发性被挤出”的问题，没有简单而通用的解决方案。

推荐阅读