Goroutines 中的递归树构建

Question

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

tree 部分可能无关紧要，但如果我 return 函数的值不同，我可以用不同的方式构建它。

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

Answer 1

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

这里的 tl;dr 是您必须 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/Whosebug/66727888/main.go:22 +0x66

goroutine 6 [chan receive (nil chan)]:
main.summer(0x0, 0x0)
    /Users/danfarrell/git/Whosebug/66727888/main.go:10 +0x59
created by main.main
    /Users/danfarrell/git/Whosebug/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

Answer 2

感谢这里的帮助，我走上了正确的轨道。我还从另一个线程中获取了提示并添加了一个 depth 变量，并将 true 发送到 done 以保持程序运行。

func recurseTreeFetching(fetcher Fetcher, tree treeprint.Tree, issueID string, done chan bool, depth int) {
    issues := fetcher.fetchIssues(issueID)
    if len(issues) == 0 {
        return
    }
    depth--
    if depth == 0 {
        done <- true
        return
    }

    for i := 0; i < len(issues); i++ {
        currIssueID := issues[i].Key
        currBranch := tree.AddBranch(currIssueID)
        go recurseTreeFetching(fetcher, currBranch, currIssueID, done, depth)
    }
}

Answer 3

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

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

下面代码思路如下：

维护正在执行的函数调用的数量，这些相当于children的数量（包括初始的“tree-top”）。
函数执行完成后，从数字中减去它。
一旦我们达到零，我们就用完了函数调用并可以打印树

潜在问题：如果一个分支比另一个分支花费的时间长得多，我相信代码可以在慢分支完成之前将 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

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

Goroutines 中的递归树构建

Recursive tree building in Goroutines

recursion

go

goroutine