在Go中递归选择子对象的有效方法？
在Go中递归选择子对象的有效方法？
提问于 2018-10-06 17:18:54
我正在尝试找出在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中有效地选择与父in (1)相关的所有子in (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语句的占位符。
还有没有其他更有效率的东西？
回答 1
Stack Overflow用户
发布于 2019-02-20 18:19:15
我不能证明这一点，但是因为每个记录只有一个父记录，并且您拥有的数据是每个记录的父记录，所以搜索记录结构更有效。
我将首先将您的记录列表转换为从id到parent的映射：
parentMap := make(map[int]int, len(records))
for _, rec := range records {
parentMap[rec.ID] = rec.ParentID
}因此，您可以有效地查找每个id的父级。然后，我将创建一个map来存储已知记录的状态：
type idStatus map[int]bool如果id存在于map中，则意味着该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
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52677543
复制相关文章
相似问题