循環してしまう木構造をGoroutineで処理したい。
いま木構造でそれぞれのノードでGoroutineを作成し、ある処理を行い更に下位のノードのGoroutineをそのGoroutineで起動するようなプログラムを作成しています。そこで問題は、あるノードの下に、これまでに別のGoroutineで辿ったノードが出てきてしまう場合です。同じノードのしたには100%同じ木構造が構築される状況なので、そのすでに辿ったノードの下にはすでに別のGoroutineにより辿ったノードがあるので、無駄な処理になってしまいます。
そこで、すでに調べたノードを記憶して後からそのノード以下を辿らないようにしたいです。この場合スライスを用いて、すでに辿ったノードの識別子を登録し、それぞれのGoroutineで参照し、一致しなければ下位ノードのGoroutineを起動するようにしましたがこれがうまくできません。この場合はどのような方法が考えられますか。
以下に検証に用いたサンプルプログラムを示します。
package main
import "math/rand"
import "time"
import "fmt"
var alpha =[]string{"A","B","C","D","E","F","G","H","I","J","K","L","M"}
func main() {
c := make(chan string)
s := make([]string, 0, len(alpha))
for i:=0; i<3; i++{
go routine(s, c)
}
for{
res := <-c
s = append(s, res)
if len(s) == len(alpha){
break
}
}
for _, v := range s{
fmt.Println(v)
}
}
func routine(s []string, ch chan string){
c := random()
for _,v := range s{
if v == c{
return
}
}
ch <- c
for i:=0;i<3;i++{
go routine(s,ch)
}
}
func random()string{
rand.Seed(time.Now().UnixNano())
return alpha[rand.Intn(len(alpha))]
}
結果
C
H
M
I
L
D
L
F
I
I
K
K
H
ここでは対象のデータは木構造になっていないです。
このようにすでに出てきたものもスライスに保存されてしまいます。さらに実際に作成しようとしているコードでは、木構造全体のノード数(ここではABC...)が未知数なので、Sliceを用いた方法はできないと考えられます(capなしのappendは新しいアドレスを確保するため)。
この場合どのようにして、すでに辿ったノードを判断すればいいのでしょうか。