2

我正在尝试将算法从 Python 移植到 Go。它的中心部分是使用 dicts 构建的树，它应该保持这种方式，因为每个节点可以有任意数量的子节点。所有叶子都在同一级别，因此最低级别的字典包含其他字典，而最低级别的包含浮点数。像这样：

tree = {}
insert(tree, ['a', 'b'], 1.0)
print tree['a']['b']

因此，在尝试将代码移植到 Go 并同时学习语言时，我开始测试基本思想：

func main() {
    tree := make(map[string]interface{})
    tree["a"] = make(map[string]float32)
    tree["a"].(map[string]float32)["b"] = 1.0
    fmt.Println(tree["a"].(map[string]float32)["b"])
}

这按预期工作，因此下一步是将其变成一个例程，该例程将采用“树”、路径和值。我选择了递归方法并想出了这个：

func insert(tree map[string]interface{}, path []string, value float32) {
    node := path[0]
    l := len(path)
    switch {
    case l > 1:
        if _, ok := tree[node]; !ok {
            if l > 2 {
                tree[node] = make(map[string]interface{})
            } else {
                tree[node] = make(map[string]float32)
            }
        }
        insert(tree[node], path[1:], value) //recursion
    case l == 1:
        leaf := tree
        leaf[node] = value
    }
}

这就是我想象的例程应该如何结构化，但我无法让标有“递归”的行工作。如果我尝试对tree[node]. 这样做的正确方法是什么？

4

2 回答 2

7

对于像这样的通用数据结构，Go 可能不是理想的解决方案。类型断言使之成为可能，但操作其中的数据需要您在 python 和其他脚本语言中习惯的更多工作。

关于您的具体问题：您在insert()调用中缺少类型断言。的值在那个时候tree[node]是类型的。interface{}该函数需要 type map[string]interface{}。类型断言将解决这个问题。

这是一个工作示例：

package main

import "fmt"

type Tree map[string]interface{}

func main() {
    t := make(Tree)
    insert(t, []string{"a", "b"}, 1.0)

    v := t["a"].(Tree)["b"]
    fmt.Printf("%T %v\n", v, v)

    // This prints: float32 1
}

func insert(tree Tree, path []string, value float32) {
    node := path[0]
    len := len(path)

    switch {
    case len == 1:
        tree[node] = value

    case len > 1:
        if _, ok := tree[node]; !ok {
            tree[node] = make(Tree)
        }

        insert(tree[node].(Tree), path[1:], value) //recursion
    }
}

请注意，我为地图创建了一个新类型。这使得代码更容易理解。我还对树节点和叶子使用相同的“map[string]interface{}”。如果你想从结果树中得到一个浮点数，则需要另一个类型断言：

leaf := t["a"].(Tree)["b"]  // leaf is of type 'interface{}`.
val := leaf.(float32)
于 2012-06-05T15:22:42.410 回答
6

好吧...问题是您正在尝试使用 Python 习语编写 Go 代码，并且您正在使用...哈希表制作一棵树？嗯？然后你必须保持键是唯一的并做一堆其他的事情，如果你只是把一组孩子切成薄片，你就可以免费得到那种东西。

我不会让 Tree 成为一个明确的 map[string]interface{}。树和树上的节点实际上是一回事，因为它是递归数据类型。

type Tree struct {
    Children []*Tree
    Value    interface{}
}

func NewTree(v interface{}) *Tree {
    return &Tree{
        Children: []*Tree{},
        Value:    v,
    }
}

所以要添加一个孩子...

func (t *Tree) AddChild(child interface{}) {
    switch c := child.(type) {
    case *Tree:
        t.Children = append(t.Children, c)
    default:
        t.Children = append(t.Children, NewTree(c))
    }
}

如果你想实现一些递归函数......

func (t *Tree) String() string {
    return fmt.Sprint(t.Value)
}

func (t *Tree) PrettyPrint(w io.Writer, prefix string) {
    var inner func(int, *Tree)
    inner = func(depth int, child *Tree) {
        for i := 0; i < depth; i++ {
            io.WriteString(w, prefix)
        }
        io.WriteString(w, child.String()+"\n") // you should really observe the return value here.
        for _, grandchild := range child.Children {
            inner(depth+1, grandchild)
        }
    }
    inner(0, t)
}

类似的东西。任何节点都可以成为某棵树的根，因为子树本身就是一棵树。有关工作示例，请参见此处：http ://play.golang.org/p/rEx43vOnXN

那里有一些文章，例如“Python 不是 Java”（http://dirtsimple.org/2004/12/python-is-not-java.html），因此，Go 不是 Python。

于 2012-06-05T21:23:38.497 回答