How to organize Go code in packages

huangapple go评论82阅读模式
英文:

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 UnionFindstructure 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 type Unionfind
  • put the quick find algorithm into its own package 'quickfind' with its own folder
  • import the unionfind the default way using the GOPATH
  • 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.

huangapple
  • 本文由 发表于 2016年2月16日 04:27:38
  • 转载请务必保留本文链接:https://go.coder-hub.com/35418451.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定