在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/NRM0yyQi8X

package main

import (

    "fmt"

    "sync"

    "time"

)

type Leaf struct {

    // Whatever

}

func worker(i int, wg *sync.WaitGroup, in <-chan Leaf) {

    for leaf := range in {

        time.Sleep(time.Millisecond * 500)

        fmt.Printf("worker %d finished work: %#v\n", i, leaf)

    }

    fmt.Printf("worker %d exiting\n", i)

    wg.Done()

}

func main() {

    var jobQueue = make(chan Leaf)

    var numWorkers = 10

    // the waitgroup will allow us to wait for all the goroutines to finish at the end

    var wg = new(sync.WaitGroup)

    for i := 0; i < numWorkers; i++ {

        wg.Add(1)

        go worker(i, wg, jobQueue)

    }

    // enqueue work (this goes inside your tree traversal.)

    for i := 0; i < 100; i++ {

        jobQueue <- Leaf{}

    }

    // closing jobQueue will cause all goroutines to exit the loop on the channel.

    close(jobQueue)

    // Wait for all the goroutines to finish

    wg.Wait()

}

Answer 2

我强烈建议从上到下阅读这篇优秀的博客文章：

https://blog.golang.org/pipelines

它不仅涵盖了您所需要的示例（即并行文件树遍历计算 MD5 文件校验和），还涵盖了更多内容：

• 扇入/扇出通道技术

• 并行性

• 通过完成通道取消管道

• 通过错误通道进行流水线错误链接

• 有界并行

最后一个主题，有界并行，用于确保“行走”的大节点目录树不会创建过多的 go-routines：bounded.go