1

Go to work で実装された DisjointSets データ構造 (Cormen から取得) がありint64ます。

type DisjointSets struct {
    ranks map[int64]int64
    p map[int64]int64
}

// New returns a new DisjointSets
func NewDisjointSets() *DisjointSets {
    d := DisjointSets{map[int64]int64{}, map[int64]int64{}}
    return &d
}

// MakeSet adds element x to the disjoint sets in its own set
func (d *DisjointSets) MakeSet(x int64) {
    d.p[x] = x
    d.ranks[x] = 0
}

// Link assigns x to y or vice versa, depending on the rank of each
func (d *DisjointSets) Link(x, y int64) {
    if d.ranks[x] > d.ranks[y] {
        d.p[y] = x
    } else {
        d.p[x] = y
        if d.ranks[x] == d.ranks[y] {
            d.ranks[y] += 1
        }
    }
}

// FindSet returns the set in which an element x sits
func (d *DisjointSets) FindSet(x int64) int64 {
    if x != d.p[x] {
        d.p[x] = d.FindSet(d.p[x])
    }
    return d.p[x]
}

// Union combines two elements x and y into one set.
func (d *DisjointSets) Union(x, y int64) {
    d.Link(d.FindSet(x), d.FindSet(y))
}

float64、などでこの構造を使用するためのインクリメンタル コードをできるだけ少なく書きたいのですがstring、どうすればよいですか?

これまでに試したこと

インターフェイスについてできる限りのことを読みましたが、型ごとに完全な実装を書かなくてもそれを適用する方法を理解していないようです。

4

3 に答える 3

1

Go にはテンプレートがないため、これを行うエレガントな方法はないと思います。interface{}int64 の代わりに取得するクラスを変更してみてください。

于 2013-09-12T03:00:22.030 に答える
0

古典的な共用体検索アルゴリズムを実装しようとしているようです。

持っているものを保持して、この上に、必要なもの ( 、 など) から へのマッピングを重ねることができないfloat64のstringはなぜint64ですか? その後、元のコードをまったく変更する必要はありません。構成を考えます。

具体的には、次のように、必要なドメインからマップを追加しますstring。

var m1 map[string]int64
...
m1["hello"] = 0
m2["world"] = 1

次に、それがどのセットに属しているかを把握したいときはいつでも、 を使用m1して文字列から要素の整数表現に移動し、元のコードで親の代表を見つけます。

于 2013-09-12T04:06:32.193 に答える