在 Go 中递归选择子代的有效方法？

在 Go 中，使用递归或尾递归函数来选择子代的效率较低，因为编译器未针对此类函数进行优化。为了有效地选择相关子代，可以使用迭代方法或创建从 id 到父级的映射，并通过线性搜索树来确定子代的状态。

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

假设我在地图中有以下记录结构：

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）？

欢迎所有答案，包括迭代、递归、尾递归，甚至通道尾递归。

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

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 切片的部分，因为它只是 select 语句的占位符。

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

解决方案

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

我首先将您的记录列表转换为从 id 到父级的映射：

parentmap := make(map[int]int, len(records))
for _, rec := range records {
    parentmap[rec.id] = rec.parentid
}

因此您可以有效地查找每个 id 的父级。然后，我将创建一个映射来存储已知记录的状态：

type idstatus map[int]bool

如果地图中存在 id，则表示该 id 的状态已知。布尔值指示它是否是目标 parentid 的子项。

然后循环所有记录并在树中线性搜索，直到找到状态已知的记录。找到它后，您可以标记在树上搜索中找到的所有记录的状态：

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。

本篇关于《在 Go 中递归选择子代的有效方法？》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于Golang的相关知识，请关注golang学习网公众号！