2

Python から Go にアルゴリズムを移植しようとしています。その中心部分は辞書を使用して構築されたツリーであり、各ノードは任意の数の子を持つことができるため、このままにしておく必要があります。すべてのリーフは同じレベルにあるため、最下位レベルのディクテーションには他のディクテーションが含まれ、最下位レベルのディクテーションにはフロートが含まれます。このような：

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 に答える