在golang中并行递归扫描树

Question

我有一棵二叉树，它访问节点的速度相对较快，但叶子除外——它们可能慢 100-1000 倍。我有一个递归算法，我想在 go 中实现（我是新手）。

因为我必须到达叶子节点才能从并行性中受益，所以我需要在树中将执行并行化得更高。不过，这可能会导致数百万个 goroutines。用信号量限制这一点似乎不是“可行”的方式——没有这样的同步原语。我担心的另一个问题是，实际上，一个频道有多贵，我是否应该使用等待组。

我的树是抽象的，算法在它上面运行，按级别和索引识别项目。

// l3               0

//               /    \

// l2          0        1

//           /  \     /   \

// l1       0    1   2     3

//         / \  / \ / \   / \

// l0     0  1 2  3 4 5  6  7

例如，我可以使用这样的函数来计算向量中所有项目的总和：

func Sum(level, index int, items []int) int {

    if level == 0 {return items[index]}

    return Sum(level-1, index*2, items) + Sum(level-1, index*2+1, items)

}

我的方法应该是什么？有人可以指出我在 Go 中实现的递归树多线程算法吗？

Answer 1

听起来你需要一个工作池。这是我刚刚写的一个例子：https: //play.golang.org/p/NRM0yyQi8Xpackage mainimport (&nbsp; &nbsp; "fmt"&nbsp; &nbsp; "sync"&nbsp; &nbsp; "time")type Leaf struct {&nbsp; &nbsp; // Whatever}func worker(i int, wg *sync.WaitGroup, in <-chan Leaf) {&nbsp; &nbsp; for leaf := range in {&nbsp; &nbsp; &nbsp; &nbsp; time.Sleep(time.Millisecond * 500)&nbsp; &nbsp; &nbsp; &nbsp; fmt.Printf("worker %d finished work: %#v\n", i, leaf)&nbsp; &nbsp; }&nbsp; &nbsp; fmt.Printf("worker %d exiting\n", i)&nbsp; &nbsp; wg.Done()}func main() {&nbsp; &nbsp; var jobQueue = make(chan Leaf)&nbsp; &nbsp; var numWorkers = 10&nbsp; &nbsp; // the waitgroup will allow us to wait for all the goroutines to finish at the end&nbsp; &nbsp; var wg = new(sync.WaitGroup)&nbsp; &nbsp; for i := 0; i < numWorkers; i++ {&nbsp; &nbsp; &nbsp; &nbsp; wg.Add(1)&nbsp; &nbsp; &nbsp; &nbsp; go worker(i, wg, jobQueue)&nbsp; &nbsp; }&nbsp; &nbsp; // enqueue work (this goes inside your tree traversal.)&nbsp; &nbsp; for i := 0; i < 100; i++ {&nbsp; &nbsp; &nbsp; &nbsp; jobQueue <- Leaf{}&nbsp; &nbsp; }&nbsp; &nbsp; // closing jobQueue will cause all goroutines to exit the loop on the channel.&nbsp; &nbsp; close(jobQueue)&nbsp; &nbsp; // Wait for all the goroutines to finish&nbsp; &nbsp; wg.Wait()}

Answer 2

我强烈建议从上到下阅读这篇优秀的博客文章：https://blog.golang.org/pipelines它不仅涵盖了您所需要的示例（即并行文件树遍历计算 MD5 文件校验和），还涵盖了更多内容：扇入/扇出通道技术并行性通过完成通道取消管道通过错误通道进行流水线错误链接有界并行最后一个主题，有界并行，用于确保“行走”的大节点目录树不会创建过多的 go-routines：bounded.go