Как организовать код 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

Вы не сможете использовать одну и ту же структуру для всех реализаций поиска 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 { 
    ... 
} 

Answer 2

Первое, что нужно сделать, это четко объяснить вашу проблему. Например,

Я хочу реализовать несколько альтернативных алгоритмов объединения в Go. Например, быстрый фонд, быстрый союз, взвешенный QU, сжатие пути и взвешенный + путь. См. Union-Find Algorithms, Princeton University и Chapter one of Algorithms in Java by Sedgwick.

---

Аналог может быть Go crypto пакет, который реализует множество альтернативных криптографические хэш-функции.

Answer 3

Я адаптировал свой код для получения рабочего решения.

• обеспечивает библиотеку/пакет unionfind для общего типа Unionfind
• поставить быстро найти алгоритм в свой собственный пакет «QuickFind» со своей собственной папкой
• импортом на unionfind пути по умолчанию с помощью GOPATH
• заменить методы, с помощью функций

пихты st файл 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 за предложения.