I have a binary tree that accessing a node is relatively fast, with the exception of the leaves - they might be 100-1000 times slower. I have a recursive algorithm that I would like to implement in go (I am new to it).
Because I have to get to the leaves to get benefits from the parallelism I need to parallelize the execution higher in the tree. This though might result in millions of goroutines. Limiting this with semaphore does not seem the 'go' way- there is no such sync primitive. Another concern I have is how expensive is, in fact, a channel, should I use wait group instead.
My tree is abstract and the algorithm runs over it identifying the items by level and index.
// l3 0
// / \
// l2 0 1
// / \ / \
// l1 0 1 2 3
// / \ / \ / \ / \
// l0 0 1 2 3 4 5 6 7
For example, I can use such to compute sum of all items in a vector with the function:
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)
}
What should be my approach? Can someone point me to a recursive tree multithreaded algorithm implemented in go?