multithreading - 在golang中并行递归扫描树

Question

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

因为我必须到达叶子节点才能从并行性中获益，所以我需要在树的更高层并行化执行。这虽然可能会导致数百万个 goroutines。用信号量限制它似乎不是“开始”的方式——没有这样的同步原语。我担心的另一个问题是，事实上，一个 channel 有多贵，我是否应该改用 WaitGroup 。

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

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