构建递归树的Goroutines

本篇文章主要是结合我之前面试的各种经历和实战开发中遇到的问题解决经验整理的，希望这篇《构建递归树的Goroutines》对你有很大帮助！欢迎收藏，分享给更多的需要的朋友学习~

我想使用 github.com/xlab/treeprint 包构建并显示链接问题树。我有一个工作版本，但它不使用 go-routines，并且似乎是一个不错的候选者。

tree 部分可能不相关，但如果我从函数返回不同的值，我可以用不同的方式构建它。

func main {
    tree := treeprint.new()
    recursetreefetching(fetcher, tree, *issueid)
    fmt.println(tree.string())
}

func recursetreefetching(fetcher fetcher, tree treeprint.tree, issueid string) {
    issues := fetcher.fetchissues(issueid)
    if len(issues) == 0 {
        return
    }
    for i := 0; i < len(issues); i++ {
        currissueid := issues[i].key
        currbranch := tree.addbranch(currissueid)
        recursetreefetching(fetcher, currbranch, currissueid)
    }
}

这可行，但速度相当慢。我看过这样的答案：/recursive-goroutines-what-is-the-neest-way-to-tell-go-to-stop-reading-from-ch，但我正在努力让它发挥作用.

我不限制深度，也不检查已添加的节点。

我尝试过“增加一些并发性”。但函数死锁。有任何指导或修复吗？

func main {
    tree := treeprint.New()
    var ch chan int
    go recurseTreeFetching(fetcher, tree, *issueID, ch)
    tocollect := 1
    for n := 0; n < tocollect; n++ {
        tocollect += <-ch
    }
    fmt.Println(tree.String())

}

func recurseTreeFetching(fetcher Fetcher, tree treeprint.Tree, issueID string, ch chan int) {
    issues := fetcher.fetchIssues(issueID)
    if len(issues) == 0 {
        return
    }
    ch <- len(issues)
    for i := 0; i < len(issues); i++ {
        currIssueID := issues[i].Key
        currBranch := tree.AddBranch(currIssueID)
        go recurseTreeFetching(fetcher, currBranch, currIssueID, ch)
    }
}

解决方案

添加另一个答案，因为它使用不同的方法。

我的第一个解决方案的问题是，如果我们永远不会到达 depth 变量，我们永远不会得到 done <- true，因此该函数永远不会“结束”。如果这不叫死锁那叫什么？

下面代码的思路如下：

• 维护正在执行的函数调用数量，这些相当于子级的数量（包括初始的“树顶”）。
• 函数执行完成后，从数字中减去该值。
• 一旦我们达到零，我们就已经用尽了函数调用并且可以打印树

潜在问题： 如果一个分支花费的时间明显长于另一个分支，我相信代码可以在慢速分支完成之前将 children 值减去 0 。

func recursetreefetching(fetcher fetcher, tree treeprint.tree, issueid string, ch chan int, depth int) {
    issues := fetcher.fetchissues(issueid)
    if len(issues) == 0 {
        // delete this child
        ch <- -1
        return
    }
    depth--
    if depth == 0 {
        // delete this child
        ch <- -1
        return
    }
    // add the number of child issues, minus the current one
    ch <- len(issues) - 1

    for i := 0; i < len(issues); i++ {
        currissueid := issues[i].key
        currbranch := tree.addbranch(currissueid)
        go recursetreefetching(fetcher, currbranch, currissueid, ch, depth)
    }
}

客户端代码：

go recursetreefetching(fetcher, tree, *issueid, ch, *depth)
    childs := 1
    for childs > 0 {
        childs += <-ch
    }

    fmt.println(tree.string())

这是一个我认为可以演示该错误的测试，但它显示正确，所以也许这可行。

type fakeunevenfetcher struct {
}

func (f fakeunevenfetcher) fetchissues(issueid string) []issue {
    var array []issue
    // initial return
    if issueid == "a" {
        b := issue{key: "b"}
        array = append(array, b)
        c := issue{key: "c"}
        array = append(array, c)
    }
    // branch b quickly returns three results
    if issueid == "b" {
        d := issue{key: "d"}
        array = append(array, d)
        e := issue{key: "e"}
        array = append(array, e)

    }
    // branch c returns two returns after 3 seconds
    if issueid == "c" {
        time.sleep(3 * time.second)
        f := issue{key: "f"}
        array = append(array, f)
        g := issue{key: "g"}
        array = append(array, g)
        h := issue{key: "h"}
        array = append(array, h)
    }

    return array
}

func testunevenfetch(t *testing.t) {
    fetcher := fakeunevenfetcher{}
    tree := treeprint.new()
    var ch = make(chan int)

    go recursetreefetching(fetcher, tree, "a", ch, 3)
    childs := 1
    for childs > 0 {
        childs += <-ch
    }

    fmt.println(tree.string())
}

打印：

.
├── b
│   ├── d
│   └── e
└── c
    ├── f
    ├── g
    └── h

这是我的预期结果，但不是我预期的失败。

我想我已经能够重现您的错误，尽管这只是基于您的代码的猜测（因为您没有'不要提供您的实际错误消息）。

这里的重点是，您必须 make(chan int) 您的频道。错误消息提到“死锁”，但真正的问题是通道仍然是 nil。

package main
import(
  "log"
)


func summer(src <-chan int, result chan<- int64) {
  var sum int64
  var count int
  for i := range src {
    sum += int64(i)
    count++
  }
  log.printf("summer: summed %d ints: %d", count, sum)
  result<-sum
}

func main() {
  var src chan int
  var dest chan int64
  go summer(src,dest)
  for i:=0; i<1000;i++{
    src<-i
  }
  close(src)
  <-dest
}

$ go run main.go
fatal error: all goroutines are asleep - deadlock!

goroutine 1 [chan send (nil chan)]:
main.main()
    /users/danfarrell/git/stackoverflow/66727888/main.go:22 +0x66

goroutine 6 [chan receive (nil chan)]:
main.summer(0x0, 0x0)
    /users/danfarrell/git/stackoverflow/66727888/main.go:10 +0x59
created by main.main
    /users/danfarrell/git/stackoverflow/66727888/main.go:20 +0x41
exit status 2

但是如果我将 make(...) 添加到通道中：

package main
import(
  "log"
)


func summer(src <-chan int, result chan<- int64) {
  var sum int64
  var count int
  for i := range src {
    sum += int64(i)
    count++
  }
  log.printf("summer: summed %d ints: %d", count, sum)
  result<-sum
}

func main() {
  var src = make(chan int)
  var dest = make(chan int64)
  go summer(src,dest)
  for i:=0; i<1000;i++{
    src<-i
  }
  close(src)
  <-dest
}

然后相同的代码可以工作：

$ go run main.go
2021/03/20 20:31:01 summer: summed 1000 ints: 499500

理论要掌握，实操不能落！以上关于《构建递归树的Goroutines》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！