Использование подпрограмм и каналов для функции построения деревьев сверху вниз - PullRequest
Новая
       8

Использование подпрограмм и каналов для функции построения деревьев сверху вниз

0 голосов
/ 08 февраля 2020

Я новичок с golang и каналами / программами, но я понимаю концепцию и простое использование.

Теперь я пытаюсь реализовать параллельную функцию построения дерева, алгоритм довольно прост - от сверху вниз для каждого узла я добавляю 2 дочерних элементов, а затем для каждого дочернего элемента выполняю одну и ту же операцию deepLimit times . Вот код для неконкурентного: 

package main

import (
    "encoding/json"
    "fmt"
    "time"
)

type Node struct {
    Name     string
    Children []Node
}

func main() {
    mainNode := Node{"p", nil}
    AddChildrenToNode(&mainNode, 4, 0)

    b, _ := json.MarshalIndent(mainNode, "", "  ")
    fmt.Println(string(b)) // print as json
}

func AddChildrenToNode(node *Node, depthLimit int, curDepth int) {
    curDepth++
    if curDepth >= depthLimit {
        return // reached depth limit
    }

    time.Sleep(500 * time.Millisecond) // imitating hard work c:
    fmt.Print(".")                     // status indicator
    // add children
    node.Children = []Node{
        Node{node.Name + "-l", nil},
        Node{node.Name + "-r", nil},
    }
    for idx, _ := range node.Children {
        AddChildrenToNode(&node.Children[idx], depthLimit, curDepth) // run this for every created child, recursively
    }
}

Но теперь я сталкиваюсь с трудностями, переписывая его для использования goroutine. Проблема в том, что мы на самом деле не можем знать, когда «строительство» закончено, и дать сигнал на блокировку / разблокировку основного. Я что-то пропустил? Я также пытался играть с syn c .WaitingGroup .

Ответы [ 2 ]

2 голосов
/ 09 февраля 2020

Один из способов, которым вы можете ввести goroutines в этот алгоритм, - это использовать отдельную goroutine для добавления дочерних узлов, предполагая, что вы не можете добавить их до того, как закончите sh раздел «тяжелая работа». 

func AddChildrenToNode(node *Node, wg *sync.WaitGroup,depthLimit int, curDepth int) {
  // work
  go func() {
    defer wg.Done()
    node.Children = []Node{
        Node{node.Name + "-l", nil},
        Node{node.Name + "-r", nil},
    }
    for idx, _ := range node.Children {
        AddChildrenToNode(&node.Children[idx], depthLimit, curDepth) // run this for every created child, recursively
    }
  }()
}

С этой схемой вы в конечном итоге создаете 2 ^ (глубина-1) -1 процедур, так что вы можете ждать в main для их завершения: 

func main() {
 ...
  wg:=sync.WaitGroup{}
  wg.Add((1<<(depth-1))-1)
  AddChildrenToNode(&mainNode, 4, 0)
  wg.Wait()
  ...

Есть это можно сделать другими способами, например, добавив горутин для левых и правых узлов.

0 голосов
/ 09 февраля 2020

Наверное, я наконец понял, как это реализовать. Ответ @ burak-serdar очень помог. На самом деле, вместо того, чтобы помещать весь AddChildrenToNode в пул групп, мы можем добавить в нашу группу ожидания и затем использовать лямбду, чтобы запускать только следующий слой в горутине. И поскольку мы добавляем в нашу группу ожидания перед этим слоем - гарантированно не будет переполнено значение «dones», поэтому мы всегда будем выходить, когда заполнены все дочерние элементы. Вот код: 

package main

import (
    "encoding/json"
    "fmt"
    "math/rand"
    "sync"
    "time"
)

type Node struct {
    Name     string
    Children []Node
}

func main() {
    rand.Seed(time.Now().UnixNano())

    mainNode := Node{"p", nil}
    var wg sync.WaitGroup

    AddChildrenToNode(&mainNode, 4, 0, &wg)
    wg.Wait()

    b, _ := json.MarshalIndent(mainNode, "", "  ")
    fmt.Println(string(b)) // print as json
}

func AddChildrenToNode(node *Node, depthLimit int, curDepth int, wg *sync.WaitGroup) {
    curDepth++
    if curDepth >= depthLimit {
        return // reached depth limit
    }

    // Dynamic children count
    cN := rand.Intn(5)
    for i := 0; i <= cN; i++ {
        node.Children = append(node.Children, Node{node.Name + "-l", nil})
    }

    //node.Children = []Node{}

    time.Sleep(500 * time.Millisecond) // imitating hard work c:

    for idx, _ := range node.Children {
        fmt.Println(".")
        wg.Add(1) // it will always lag behind the next done so the flow wont be broken
        go func(idx int) {
            AddChildrenToNode(&node.Children[idx], depthLimit, curDepth, wg) // run this for every created child, recursively
            wg.Done()
        }(idx)
    }
}
...