如何在包中组织 Go 代码

Question

我正在尝试使用 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. 下面的例子不起作用。但是我不知道在哪里放置策略特定代码，如何命名包以及如何导入公共结构类型。

// 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、加权QU、路径压缩、加权+路径。请参阅Union-Find Algorithms、普林斯顿大学和Sedgwick 编写的 Java 算法的第一章。一个类似的可能是 Gocrypto包，它实现了许多替代的加密哈希函数。

Answer 2

您将无法对所有联合查找实现使用相同的结构。例如，加权快速联合除了元素之外还需要树大小的数组。您在这里尝试实现的是以不同的方式实现相同的操作。这就是 Go 中接口的用途。此外，使用别名进行包导入以节省一些击键并不是一个好习惯。相反，最好提出好的名称，例如包名称及其接口/结构/函数名称是有意义的。我会将所有算法组织在一个具有以下结构的包中：package algorithmstype 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 {    ...}

Answer 3

我修改了我的代码以获得一个有效的解决方案。为unionfind通用类型提供库/包Unionfind使用自己的文件夹将快速查找算法放入自己的包“quickfind”中unionfind使用默认方式导入GOPATH用函数代替方法第一个文件是algorithms/unionfind/unionfindtype.go.package unionfindtype 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 quickfindimport 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]}