我正在尝试使用 Go 实现联合查找算法。我想使用一种结构实现不同的策略，如快速查找、快速联合和加权快速联合，UnionFind见下文。我把代码放到一个包里unionfindpackage unionfindtype Unionfind struct { elements []int}func makeUnionfind(n int) Unionfind { elements := make([]int, n) for idx := range elements { elements[idx] = idx } return Unionfind{elements}}接下来，我为不同的策略创建函数，以quick find. 下面的例子不起作用。但是我不知道在哪里放置策略特定代码，如何命名包以及如何导入公共结构类型。// create a separate package for each strategy?package quickfind// import the structure locally?import ufp "./unionfind"// prefer methods over functions for convenience?func (uf *ufp.Unionfind) union(a int, b int) { aroot := uf.elements[a] broot := uf.elements[b] for k, v := range uf.elements { if v == aroot { uf.elements[k] = broot } }}func (uf *ufp.Unionfind) connected(a int, b int) bool { return uf.elements[a] == uf.elements[b]}我应该如何组织我的代码以使快速查找算法工作但UnionFind结构分离？
3 回答
不负相思意
TA贡献1777条经验 获得超10个赞
首先要做的是清楚地解释你的问题。例如，
我想在 Go 中实现几种替代的联合查找算法。例如quick-fund、quick-union、加权QU、路径压缩、加权+路径。请参阅Union-Find Algorithms、普林斯顿大学和Sedgwick 编写的 Java 算法的第一章。
一个类似的可能是 Gocrypto包，它实现了许多替代的加密哈希函数。
喵喔喔
TA贡献1735条经验 获得超5个赞
您将无法对所有联合查找实现使用相同的结构。例如，加权快速联合除了元素之外还需要树大小的数组。
您在这里尝试实现的是以不同的方式实现相同的操作。这就是 Go 中接口的用途。
此外，使用别名进行包导入以节省一些击键并不是一个好习惯。相反，最好提出好的名称，例如包名称及其接口/结构/函数名称是有意义的。
我会将所有算法组织在一个具有以下结构的包中：
package algorithms
type UnionFind interface {
Union(a int, b int)
Connected(a int, b int) bool
}
func QuickFind(n int) UnionFind {
return &quickFind{......}
}
func QuickUnion(n int) UnionFind {
return &quickUnion{......}
}
type quickUnion struct {
....
}
func (qu *quickUnion) Union(a int, b int) {
...
}
func (qu *quickUnion) Connected(a int, b int) bool {
...
}
type quickFind struct {
....
}
func (qf *quickFind) Union(a int, b int) {
...
}
func (qf *quickFind) Connected(a int, b int) bool {
...
}
杨魅力
TA贡献1811条经验 获得超6个赞
我修改了我的代码以获得一个有效的解决方案。
为
unionfind通用类型提供库/包Unionfind使用自己的文件夹将快速查找算法放入自己的包“quickfind”中
unionfind使用默认方式导入GOPATH用函数代替方法
第一个文件是algorithms/unionfind/unionfindtype.go.
package unionfind
type Unionfind struct {
Elements []int
}
func MakeUnionfind(n int) Unionfind {
elements := make([]int, n)
for idx := range elements {
elements[idx] = idx
}
return Unionfind{elements}
}
第二个文件是algorithms/unionfind/quickfind/quickfind.go.
package quickfind
import ufp "algorithms/unionfind"
func union(uf *ufp.Unionfind, a int, b int) {
aroot := uf.Elements[a]
broot := uf.Elements[b]
for k, v := range uf.Elements {
if v == aroot {
uf.Elements[k] = broot
}
}
}
func connected(uf *ufp.Unionfind, a int, b int) bool {
return uf.Elements[a] == uf.Elements[b]
}
- 3 回答
- 0 关注
- 139 浏览
添加回答
举报
0/150
提交
取消