如何在包中组织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中的用途。

此外，使用包导入别名来保存一些关键笔画并不是一个好做法。相反，最好想出好的名称，比如包名以及它的interace/struct/函数名，这是有意义的。

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

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

Answer 2

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

我想在Go中实现几种替代的联合查找算法。例如，快速基金、快速合并、加权QU、路径压缩和加权+路径.见普林斯顿大学联合查找算法和第一章Java中的Sedgwick算法。

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

Answer 3

我修改了我的代码以得到一个有效的解决方案。

• 为常见类型的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]
}

感谢JimB和fl0cke的建议。