英文:
How to organize Go code in packages
问题
我正在尝试使用Go实现并查集算法。我想要实现不同的策略,如“快速查找”、“快速合并”和“加权快速合并”,并使用一个名为UnionFind
的结构体来实现。我将代码放在了一个名为unionfind
的包中。
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}
}
接下来,我创建了不同策略的函数,从quick find
开始。下面的示例代码并不能正常工作。但我不知道应该将策略特定的代码放在哪里,如何命名包以及如何导入公共结构类型。
// 为每个策略创建一个单独的包?
package quickfind
// 在本地导入结构体?
import ufp "./unionfind"
// 为方便起见,使用方法而不是函数?
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
结构体分离出来?
英文:
I'm trying to implement the union find algorithm using Go. I want to implement different strategies like quick find, quick union and weighted quick union using one structure UnionFind
see below. I put the code into a package unionfind
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}
}
Next I create the functions for the different strategies starting with quick find
. The example below isn't working. But I have no idea where to put the strategy specific code, how to name the package and how to import the common structure type.
// 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]
}
How should I organize my code the get the quick find algorithm working but have the UnionFind
structure separated?
答案1
得分: 3
首先要做的是清楚地解释你的问题。例如,
我想在Go语言中实现几种不同的并查集算法,比如quick-find、quick-union、加权QU、路径压缩以及加权+路径。可以参考普林斯顿大学的并查集算法和Sedgwick的《算法在Java中的实现》第一章。
一个类似的例子是Go语言的crypto
包,它实现了许多不同的加密哈希函数。
英文:
The first thing to do is to explain your problem clearly. For example,
I want to implement several alternative union-find algorithms in Go. For example, quick-fund, quick-union, weighted QU, path compression, and weighted + path. See Union-Find Algorithms, Princeton University and Chapter one of Algorithms in Java by Sedgwick.
An analog might be the Go crypto
package which implements many alternative cryptographic hash functions.
答案2
得分: 1
你将无法在所有并查集实现中使用相同的结构体。例如,“加权快速合并”除了元素之外,还需要一个树大小的数组。
你在这里尝试实现的是相同的操作以不同的方式。这就是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 {
...
}
希望对你有帮助!
英文:
You won't be able to use the same struct for all union find implementations. For example weighted quick union requires array of tree sizes in addition to the elements.
What you are trying to achieve here is to have the same operations implemented differently. This is what interfaces are for in Go.
Additionally using aliases for package imports to save a few key strokes is not a good practice. Instead it is better to come up with good names such as package name together with its interace/struct/function names makes sense.
I would organize all algorithms in one package with the following structure:
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 {
...
}
答案3
得分: 0
我调整了我的代码以获得一个可行的解决方案。
- 为常见类型
Unionfind
提供一个名为unionfind
的库/包。 - 将“quick find”算法放入自己的包
quickfind
中,并拥有自己的文件夹。 - 使用
GOPATH
以默认方式导入unionfind
。 - 将方法替换为函数。
第一个文件是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]
}
感谢JimB和fl0cke的建议。
英文:
I adapted my code to get a working solution.
- provide a library/package
unionfind
for the common typeUnionfind
- put the quick find algorithm into its own package 'quickfind' with its own folder
- import the
unionfind
the default way using theGOPATH
- replace the methods by functions
The first file is 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}
}
The second file is 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]
}
Thanks to JimB and fl0cke for the suggestions.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论