如何在包中组织 Go 代码

Question

我正在尝试使用 Go 实现联合查找算法。我想使用一种结构 quick find、quick union 和 weighted quick union 等不同的策略 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 开始的不同策略创建函数。下面的示例不起作用。但我不知道策略具体代码放在哪里，如何命名包以及如何导入公共结构类型。

// 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 结构分开？

Answer 1

首先要做的是把你的问题解释清楚。例如，

我想在 Go 中实现几个可供选择的联合查找算法。比如quick-fund、quick-union、weighted QU、path compression、weighted + path。参见 Union-Find Algorithms, Princeton University and Chapter one of Algorithms in Java by Sedgwick。

类似的可能是 Go crypto 包，它实现了许多替代加密哈希函数。

Answer 2

我调整了我的代码以获得可行的解决方案。

为普通类型提供一个library/packageunionfindUnionfind
将 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 的建议。

Answer 3

您将无法对所有联合查找实现使用相同的结构。例如 weighted quick union 除了元素之外还需要树大小数组。

您在这里想要实现的是让相同的操作以不同的方式实现。这就是 Go 中的接口。

此外，为包导入使用别名来节省一些按键并不是一个好习惯。相反，最好想出好名字，例如包名及其 interace/struct/function 名称才有意义。

我会将所有算法组织在一个包中，结构如下：

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 {
    ...
}

如何在包中组织 Go 代码

How to organize Go code in packages

go

code-structure