代码之家 › 专栏 › 技术社区 › m_callens

同时计算树叶数

goroutine channel recursion go

m_callens · 技术社区 · 7 年前

有一个函数我想使用并发模型来编写,以防输入太大,并行处理效率更高,但它永远不会结束。

假设有一个 struct 定义为:

type Tree struct {
    Name     string   `json:"name"`
    SubTrees []*Tree  `json:"subTrees,omitempty"`
    Leaves   []string `json:"leaves"`
}

我想写一个函数来计算 Leaves 在整个递归结构中。使用递归很容易做到这一点:

func (tree *Tree) CountLeaves() int {
    curr := len(tree.Leaves)
    for _, s := range tree.SubTrees {
        curr += s.CountLeaves()
    }
    return curr
}

这很好,但如果结构变得太大,这将是低效的,所以我想将其重构为并发的并使用通道。下面是我对重构的尝试:

func (tree *Tree) CountLeaves() int {
    var wg sync.WaitGroup
    ch := make(chan int)
    defer close(ch)
    go count(tree, true, ch, &wg)

    var total int
    wg.Add(1)
    go func(total *int) {
        for x := range ch {
            fmt.Println(x)
            *total += x
        }
        wg.Done()
    }(&total)
    wg.Wait()

    return total
}

func count(t *Tree, root bool, ch chan int, wg *sync.WaitGroup) {
    defer wg.Done()
    ch <- len(t.Leaves)
    if t.SubTrees != nil {
        wg.Add(len(t.SubTrees))
        for _, s := range t.SubTrees {
            go count(s, false, ch, wg)
        }
        wg.Wait()
    }

    if root {
        ch <- -1
    }
}

我现在可以通过我当前需要计算的频道收集所有数字 树叶 但是这个功能永远不会结束。终止值 -1 从根本上 Tree 结构从未通过通道被推送或接收过,我不知道为什么。

有什么想法吗?

1 回复 | 直到 7 年前

dave 7 年前

我很确定你的 WaitGroup 只是永远不够 wg.Done 电话:

go func(total *int) {
    for x := range ch {
        fmt.Println(x)
        *total += x
    }
    wg.Done()
}(&total)

因为你从不关门 ch , the 已完成 不会在这里打电话。我认为如果在循环中移动它:

go func(total *int) {
    for x := range ch {
        fmt.Println(x)
        *total += x
         wg.Done()
    }
}(&total)

这将解决问题。

编辑:

实际上,我认为还有一个问题:

defer wg.Done()
ch <- len(t.Leaves)
if t.SubTrees != nil {
    wg.Add(len(t.SubTrees))
    for _, s := range t.SubTrees {
        go count(s, false, ch, wg)
    }
    wg.Wait()
}

递延的 wg.Done() 在你回来之前不会接到电话,所以这个 wg.Wait() 也将永远等待。这可能是:

ch <- len(t.Leaves)
if t.SubTrees != nil {
    wg.Add(len(t.SubTrees))
    for _, s := range t.SubTrees {
        go count(s, false, ch, wg)
    }
    wg.Done()
    wg.Wait()
} else {
    wg.Done()
}