go - 在 Go 中递归选择子项的有效方法？

Question

我正在尝试找出从 Golang 中的父级递归选择所有相关子级的最佳方法(顺序无关紧要)，但我听说编译器并未针对递归和尾递归函数进行优化，所以它们的成本很高。

假设我在 map 中有以下记录结构:

Legend: ID:ParentID

               1:0
           _____|_______
          /     |       \
        2:1    3:1      4:1
     ____|               |______ _______
    /    |               |      \       \
  5:2   6:2             7:4     8:4     9:4
                                 |______
                                 |      \
                                10:8    11:8
                                 |______
                                 |      \
                                12:10   13:10

如何在 Go 中有效地选择与父 (1) 相关的所有子 ID(2 到 13)？

欢迎所有答案，包括 Iterative、Recursive、Tail-Recursive，甚至 Channel-Tail-Recursive。

更新:下面是我当前使用迭代方法的代码:

package main

import (
    "fmt"
)

type record struct {
    ID       int
    ParentID int
}

var records = make([]record, 0)

func init() {
    // Initilaize our records
    var tmpRec record
    tmpRec.ID = 1
    tmpRec.ParentID = 0
    records = append(records, tmpRec)
    tmpRec.ID = 2
    tmpRec.ParentID = 1
    records = append(records, tmpRec)
    tmpRec.ID = 3
    tmpRec.ParentID = 1
    records = append(records, tmpRec)
    tmpRec.ID = 4
    tmpRec.ParentID = 1
    records = append(records, tmpRec)
    tmpRec.ID = 5
    tmpRec.ParentID = 2
    records = append(records, tmpRec)
    tmpRec.ID = 6
    tmpRec.ParentID = 2
    records = append(records, tmpRec)
    tmpRec.ID = 7
    tmpRec.ParentID = 4
    records = append(records, tmpRec)
    tmpRec.ID = 8
    tmpRec.ParentID = 4
    records = append(records, tmpRec)
    tmpRec.ID = 9
    tmpRec.ParentID = 4
    records = append(records, tmpRec)
    tmpRec.ID = 10
    tmpRec.ParentID = 8
    records = append(records, tmpRec)
    tmpRec.ID = 11
    tmpRec.ParentID = 8
    records = append(records, tmpRec)
    tmpRec.ID = 12
    tmpRec.ParentID = 10
    records = append(records, tmpRec)
    tmpRec.ID = 13
    tmpRec.ParentID = 10
    records = append(records, tmpRec)
}

func main() {
    childIDs := getAllRelatedRecords(1)

    for _, id := range childIDs {
        fmt.Println(id)
    }
}

func getAllRelatedRecords(parentID int) []int {
    idsToProcess := make([]int, 0)
    ids := make([]int, 0)

    // Find all children of the parent.
    for i := range records {
        if records[i].ParentID == parentID {
            idsToProcess = append(idsToProcess, records[i].ID)
        }
    }

    // Find all children of each children and add each child
    // to the final list as they get processed.
    for {
        if len(idsToProcess) == 0 {
            break
        }

        // Find all children of the first child.
        for i := range records {
            if records[i].ParentID == idsToProcess[0] {
                idsToProcess = append(idsToProcess, records[i].ID)
            }
        }

        // Add first child to the final list.
        ids = append(ids, idsToProcess[0])

        // Remove first child.
        idsToProcess = append(idsToProcess[:0], idsToProcess[1:]...)
    }

    return ids
}

注意:忽略我在 records slice 中循环的部分，因为它只是 SELECT 语句的占位符。

还有什么可以提高效率的吗？

Answer 1

我无法证明这一点，但因为每条记录只有一个父项，而您拥有的数据是每条记录的父项，因此搜索记录结构会更有效。

我首先将您的记录列表转换为从 id 到 parent 的映射:

parentMap := make(map[int]int, len(records))
for _, rec := range records {
    parentMap[rec.ID] = rec.ParentID
}

因此您可以高效地查找每个 ID 的父级。然后我会创建一个映射来存储已知记录的状态:

type idStatus map[int]bool

如果 map 中存在一个 id，则意味着该 id 的状态是已知的。 bool 表示它是否是目标 parentID 的 child 。

然后您遍历所有记录并在树中向上线性搜索，直到找到状态已知的记录。找到它后，您可以标记在该搜索树中找到的所有记录的状态:

func getAllRelatedRecords(parentID int) []int {
    parentMap := makeParentMap()
    status := idStatus{
        0:        false,
        parentID: true,
    }
    var lineage []int
    for _, rec := range records {
        lineage = lineage[:0]
        id := rec.ID
        for {
            if isChild, found := status[id]; found {
                status.set(lineage, isChild)
                break
            }
            lineage = append(lineage, id)
            id = parentMap[id]
        }
    }
    var ids []int
    for id, isChild := range status {
        if id == parentID {
            continue // skip the parent itself
        }
        if isChild {
            ids = append(ids, id)
        }
    }
    return ids
}

type idStatus map[int]bool

func (status idStatus) set(lineage []int, isChild bool) {
    for _, id := range lineage {
        status[id] = isChild
    }
}

func makeParentMap() map[int]int {
    parentMap := make(map[int]int, len(records))
    for _, rec := range records {
        parentMap[rec.ID] = rec.ParentID
    }
    return parentMap
}

Live demo .