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

Question

I'm trying to figure out the best way to select all related children recursively from a parent in Golang (the order doesn't matter), but I hear the compiler isn't optimized for both recursive and tail-recursive functions, so they are expensive to do.

Say I have the following record structure in a 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

How do I select all child IDs (2 to 13) that are related to the parent (1) efficiently in Go?

All answers are welcome, including Iterative, Recursive, Tail-Recursive, and even Channel-Tail-Recursive.

UPDATE: Below is my current code using an Iterative approach:

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
}

NOTE: Ignore the part where I'm looping through the records slice because it's just a placeholder for a SELECT statement.

Is there anything else that can be made more efficient?

Answer 1

I can't prove it but because each record only has one parent and the data you have is the parent for each record it is more efficient to search up the record structure.

I would start by converting your list of records into a map from id to parent:

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

So you can efficiently lookup the parent for each id. Then I would create a map to store the status of a record once it is known:

type idStatus map[int]bool

if an id is present in the map then it means the status of that id is known. The bool indicates if it is a child of the target parentID or not.

Then you loop over all records and search linearly up the tree until you get to a record with known status. Once you find it you can mark the status of all the records you have found in that search up the tree:

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.