1

我有一个 DisjointSets 数据结构（从 Cormen 中提取），在 Go 中实现以使用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 回答
1

您在使用接口时偶然发现的问题是什么？您应该能够轻松地翻译该代码以interface{}用作元素类型，并使其与为其定义了相等性的任何类型一起使用（可以用作映射键）。

类似于以下内容：

于 2013-09-12T03:47:34.637 回答
0

看起来您正在尝试实现经典的联合查找算法。

为什么你不能保留你所拥有的东西，而只是在此之上添加一个从你想要的任何东西（float64,string等）到 的映射int64？然后您根本不必更改原始代码。想想作文。

具体来说，从您想要的任何域添加地图，例如string：

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

然后，每当您想弄清楚它属于哪个集合时，请使用m1从字符串转到元素的整数表示，然后使用原始代码查找父代表。

于 2013-09-12T04:06:32.193 回答