golang並行遞歸掃描樹

我有一個二叉樹，訪問一個節點相對較快，除了葉子 - 它們可能會慢100-1000倍。我有一個遞歸算法，我想在去執行（我是新來的）。golang並行遞歸掃描樹

因爲我必須去樹葉才能從並行性中獲益，所以我需要在樹中更高的並行執行。這雖然可能會導致數百萬套房屋。限制信號量似乎不是'去'的方式 - 沒有這樣的同步原語。我的另一個問題是，實際上，一個頻道的價格有多昂貴，我應該用等候組來代替。

我的樹是抽象的，算法在其上運行，通過級別和索引來識別項目。

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

應該是什麼我的做法？有人可以指向我實現的遞歸樹多線程算法嗎？

來源

2016-06-17 gsf

這將有助於回答這個問題，如果你表現出你的樹的定義。我不確定你的意思是葉片變慢。 – Logiraptor

@Logiraptor它不是我的情況，但圖像文件系統和你在文件上進行操作 - 比如說計算哈希。瀏覽目錄在葉子上工作比較便宜。否則我的樹很抽象 - 我不保存它。我只是使用級別，索引來標識項目。 – gsf

您能否接受我的回答或評論爲什麼它不能解決您的問題？ :) – Logiraptor

這聽起來像你需要一個工作人員池。這裏有一個例子，我只是寫：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() 
}

來源

2016-06-18 00:08:51 Logiraptor

我強烈建議閱讀這個優秀的博客文章從上到下：

https://blog.golang.org/pipelines

它不僅涵蓋的正是一個例子是什麼你需要（即parallelized file-tree walk calculating MD5 file checksums），但太多更多：

扇入/扇出信道技術

並行
經由
管道取消完成通道
經由 錯誤鏈接
管道錯誤通道

界並行

最後一個主題，有界並行，用來確保「走」大節點目錄樹不產生過多的去例程：bounded.go

來源

2017-11-07 21:59:24 colminator

golang並行遞歸掃描樹

回答

相關問題