我正在尝试找出在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语句的占位符。
还有没有其他更有效率的东西?
发布于 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
}
https://stackoverflow.com/questions/52677543
复制相似问题