我如何读取文本文件并根据这些值实现树？

Question

我正在尝试使用 Go 实现 DFS（深度优先搜索）算法，但我的实际代码需要逐个节点添加以手动构建树。我想用这个数据（例子）读取一个文本文件：7595 6417 47 8218 35 87 1020 04 83 47 65并用这些值构建树。根值将是 75，左 95，右 64，依此类推。这是我的完整代码：// Package main implements the DFS algorithmpackage mainimport (    "bufio"    "flag"    "fmt"    "log"    "os"    "strconv"    "strings"    "sync")// Node handle all the tree datatype Node struct {    Data  interface {}    Left  *Node    Right *Node}// NewNode creates a new node to the treefunc NewNode(data interface{}) *Node {    node := new(Node)    node.Data = data    node.Left = nil    node.Right = nil    return node}// FillNodes create all the nodes based on each value on filefunc FillNodes(lines *[][]string) {    nodes := *lines    rootInt, _ := strconv.Atoi(nodes[0][0])    root := NewNode(rootInt)    // add the values here    wg.Add(1)    go root.DFS()    wg.Wait()}// ProcessNode checks and print the actual nodefunc (n *Node) ProcessNode() {    defer wg.Done()    var hello []int    for i := 0; i < 10000; i++ {        hello = append(hello, i)    }    fmt.Printf("Node    %v\n", n.Data)}// DFS calls itself on each nodefunc (n *Node) DFS() {    defer wg.Done()    if n == nil {        return    }    wg.Add(1)    go n.Left.DFS()    wg.Add(1)    go n.ProcessNode()    wg.Add(1)    go n.Right.DFS()}// CheckError handle erros checkfunc CheckError(err error) {    if err != nil {        log.Fatal(err)    }}// OpenFile handle reading data from a text filefunc OpenFile() [][]string {    var lines [][]string    ftpr := flag.String("fpath", "pyramid2.txt", "./pyramid2.txt")    flag.Parse()    f, err := os.Open(*ftpr)    CheckError(err)    defer func() {        if err := f.Close(); err != nil {            log.Fatal(err)        }    }()    s := bufio.NewScanner(f)    for s.Scan() {        line := strings.Fields(s.Text())        lines = append(lines, line)    }    err = s.Err()    CheckError(err)    return lines}什么是可能的解决方案？另外，我如何以简单的方式将所有这些字符串转换为 int ？

Answer 1

这是创建树的方法（未测试）：

func FillLevel(parents []*Node, level []string) (children []*Node, err error){

    if len(parents) + 1 != len(level) {

        return nil, errors.New("params size not OK")

    }

    for i, p := range parents {

        leftVal, err := strconv.Atoi(level[i])

        rightVal, err := strconv.Atoi(level[i+1])

        if err != nil {

            return nil, err

        }

        p.Left = NewNode(leftVal)

        p.Right = NewNode(rightVal)

        children = append(children, p.Left)

        if i == len(parents) - 1 {

            children = append(children, p.Right)

        }

    }

    return children, nil

}

func FillNodes(lines *[][]string) (*Node, error){

    nodes := *lines

    rootInt, _ := strconv.Atoi(nodes[0][0])

    root := NewNode(rootInt)

    // add the values here

    parents := []*Node{root}

    for _, level := range nodes[1:] {

        parents, _ = FillLevel(parents, level)

    }

    return root, nil

}

func main() {

    nodes := OpenFile()

    r, _ := FillNodes(&nodes)

    wg.Add(1)

    r.DFS()

    wg.Wait()

}

如果这是用于生产，我的建议是对它进行 TDD，并正确处理所有错误并决定您的软件应该如何处理每个错误。您还可以编写一些基准，然后使用 goroutine 优化算法（如果适用）

你现在的做法，没有 goroutines 会更好：想象你有一个巨大的树，有 1M 个节点，DFS 函数将递归启动 1M 个 goroutines，每个 goroutines 都有内存和 CPU 额外成本而不做很多来证明它是合理的。您需要一种更好的方法来拆分工作以在更少的 goroutine 上完成，每个 goroutine 可能有 10000 个节点。

我强烈建议你编写一个没有 goroutines 的版本，研究它的复杂性，编写基准来验证预期的复杂性。一旦你有了它，就开始寻找引入 goroutines 的策略，并验证它是否比你已经拥有的更有效。