当前位置： > > > > 同时计算树叶数量

同时计算树叶数量

来源：stackoverflow
2024-04-25 14:51:34
0浏览
收藏

在Golang实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天米云就整理分享《同时计算树叶数量》，聊聊，希望可以帮助到正在努力赚钱的你。

问题内容

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

假设有一个 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
    }
}

我当前能够通过当前计算 leaves 总数所需的通道收集所有数字，但该函数永远不会结束。来自根 tree 结构的终止值 -1 永远不会通过通道推送或接收，我不明白为什么。

有什么想法吗？

解决方案

我很确定您的 waitgroup 永远不会获得足够的 wg.done 调用：

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

由于您从未关闭 ch，因此 wg.done 永远不会在这里被调用。我认为如果你将它移动到循环内：

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()
}

本篇关于《同时计算树叶数量》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于Golang的相关知识，请关注米云公众号！