遍历子进程的家谱：使用 Go 实现

本篇文章向大家介绍《遍历子进程的家谱：使用 Go 实现》，主要包括，具有一定的参考价值，需要的朋友可以参考一下。

我有一个很大的人口谱系（map[int][]int），其中关键是值切片中的动物和父母（两个）。没有父母的动物的父母将为负整数。

其次，我有一个动物列表，我想构建它们的特定谱系并写入文件。我列表中的所有动物谱系都应写入同一个文件。

pedigree := map[int][]int{
    1:  []int{2, 3},
    2:  []int{-1, 5},
    3:  []int{6, 7},
    4:  []int{8, 9},
    5:  []int{-1, -2},
    6:  []int{8, -2},
    7:  []int{-1, -2},
    8:  []int{-1, -2},
    9:  []int{10, -2},
    10: []int{-1, 4}
}

list := []int{1, 4}

以及我对 io.writer 编写的文件的期望：

1   2   3
  2  -1   5
  3   6   7
  5  -1  -2
  6   8  -2
  7  -1  -2
  8  -1  -2
  4   8   9
  9  10  -2
 10  -1   4

因此，我需要一个递归函数来从基础动物开始遍历谱系，然后继续遍历所有路径，直到到达具有负数的父母。

更重要的是我列表中的动物被认为是在谱系中引起循环的动物（动物 4 成为其自身的伟大父母）。

我已经尝试过使用以下代码：

type tree struct {
    sire   *tree
    dam    *tree
    animal int
    base   int
    path   []int
}

func newTree(a, s, d, b int) tree {
    return tree{
        animal: a,
        sire:   &tree{animal: s, base: b},
        dam:    &tree{animal: d, base: b},
        base:   b,
    }
}

for _, animal := range list {
    myTree = newTree(animal, pedigree[animal][0], pedigree[animal][1], 0)
    walk(myTree, written, fw) // written is a map of integers and fw is io.Writer
}

func walk(t tree, written map[int]int, writer io.Writer) tree {
    style := "%12d%12d%12d\n"
    if t.animal == t.base {
        return t
    }
    if t.base == 0 {  // for the first iteration
        t.base = t.animal
    }
    if _, ok := written[t.animal]; !ok {
        sire := t.sire.animal
        dam := t.dam.animal
        if sire == 0 {
            sire = t.base
        }
        if dam == 0 {
            dam = t.base
        }
        written[t.animal] = 0
        io.WriteString(writer, fmt.Sprintf(style, t.animal, sire, dam))
    }
    // Shift forward.
    if t.sire.animal > 0 {
        myTree := newTree(t.sire.animal, pedigree[t.sire.animal][0], pedigree[t.dam.animal][1], t.base)
        walk(myTree, written, writer)
    }
    if t.dam.animal > 0 {
        myTree := newTree(t.dam.animal, pedigree[t.dam.animal][0], pedigree[t.dam.animal][1], t.base)
        walk(myTree, written, writer)
    }
    return t
}

我的谱系由大约 1300 万只动物组成，但我无法让函数在正确的点停止并在完成一些动物后出现 stack overflow 恐慌。我相信我的一些问题是：

• 参与循环的动物是基础动物，因此我应该检查 animal == base (1->2->3->1)
• 参与循环的动物不是基础动物 (1->2->3->4->5->6->3)

任何帮助将不胜感激。

解决方案

由于您的谱系图中可能存在循环，因此您可能会陷入这样的循环。这意味着您必须检测循环并停止在那里构建。您可以通过稍微更改树来做到这一点。

首先，您按值传递 tree 对象，但附加指向它的指针。改为传递指向树的指针：

func walk(t *tree, written map[int]int, writer io.writer) *tree {
}

更好的方法可能是：

func (t *tree) walk(written map[int]int, writer io.writer) {...}

您还应该将 *parent 添加到树中，以便可以检测循环：

type tree struct {
    parent *tree
    sire   *tree
    dam    *tree
    animal int
    base   int
    path   []int
}

每次创建新关卡时，请适当设置父关卡：

mytree := newtree(t.sire.animal, pedigree[t.sire.animal][0], pedigree[t.dam.animal][1], t.base)
mytree.parent=t
mytree.walk(written, writer)

然后添加一个函数来测试是否进入循环：

func (t *tree) loop(animal int) bool {
   for t!=nil {
       if t.animal==animal {
          return true
       }
       t=t.parent
   }
   return false
}

并检查您是否进入循环：

if !myTree.loop(myTree.animal) {
   myTree.walk(written, writer)
}

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于Golang的相关知识，也可关注golang学习网公众号。