Создание общих алгоритмов в go

Я не могу понять, как реализовать алгоритм, который будет работать на любом типе.

В следующем коде будут появляться ошибки, пытающиеся преобразовать строку или типизированный фрагмент в интерфейсы, и вы не можете сравнивать интерфейс {} objects: invalid operation: result[0] > result[n - 1] (operator > not defined on interface)

func main() {
    c := Algo("abc")
    //...
    c := Algo([3]int{1,2,3})
    //...
}

func Algo(list []interface{}) chan []interface{} {
    n := len(list)
    out := make(chan []interface{})
    go func () {
        for i := 0; i < n; i++ {
            result := make([]interface{}, n)
            copy(result, list)
            // an actually useful algorithm goes here:
            if (result[0] > result[n-1]) {
                result[0], result[n-1] = result[n-1], result[0]
            }
            out <- result
        }
        close(out)
    }()
    return out
}

Хотя это боль (я думаю, что она должна быть автоматической), я могу вручную вставить и набрать набранные фрагменты в интерфейс {} s, настоящая проблема выше - это сравнение. И он просто становится все более и более глупым.

a := [3]int{1,2,3}
b := make([]interface{}, len(a))
for i, _ := range a {
    b[i] = a[i]
}

Я даже думал об использовании vector.Vector, но так много людей говорят, что никогда не использовать их.

Так должен ли я просто реализовать тот же алгоритм для int slices и строк? Как насчет фрагментов myObject? Я могу создать интерфейс с настраиваемой функцией func, но как мне заставить его работать со стандартными типами?

Ответ 1

Вы можете сделать это с помощью интерфейсов Go. Функция, которая берет тип интерфейса, является общей в том смысле, что она не заботится о представлении данных базового конкретного типа. Он делает все через вызовы методов.

Чтобы сделать общую версию вашего алгоритма, вы должны определить все возможности, которые требуется алгоритму для объектов данных, и вы должны определить методы, которые абстрагируют эти возможности. Подписи абстрактных методов становятся наборами методов интерфейсов.

Чтобы тип, совместимый с таким универсальным алгоритмом, вы определяете методы для типа, которые удовлетворяют интерфейсу параметра алгоритма.

Я возьму ваш пример кода и покажу один способ сделать это. Большинство требуемых возможностей, вероятно, покрываются sort.Interface, поэтому я решил включить его. Требуется только одна другая возможность, одна - сделать копию данных.

type algoContainer interface {
    sort.Interface
    Copy() algoContainer
}

Ниже приведена полная рабочая программа, выполненная из вашего примера кода.

package main

import (
    "fmt"
    "sort"
)

func main() {
    s1 := sortableString("abc")
    c1 := Algo(s1)
    fmt.Println(s1, <-c1)

    s2 := sortable3Ints([3]int{1,2,3})
    c2 := Algo(&s2)
    fmt.Println(s2, <-c2)
}

type algoContainer interface {
    sort.Interface
    Copy() algoContainer
}

type sortableString []byte
func (s sortableString) Len() int { return len(s) }
func (s sortableString) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s sortableString) Less(i, j int) bool { return s[i] < s[j] }
func (s sortableString) Copy() algoContainer {
   return append(sortableString{}, s...)
}
func (s sortableString) String() string { return string(s) }

type sortable3Ints [3]int
func (sortable3Ints) Len() int { return 3 }
func (s *sortable3Ints) Swap(i, j int) {
   (*s)[i], (*s)[j] = (*s)[j], (*s)[i]
}
func (s sortable3Ints) Less(i, j int) bool { return s[i] < s[j] }
func (s sortable3Ints) Copy() algoContainer { c := s; return &c }

func Algo(list algoContainer) chan algoContainer {
    n := list.Len()
    out := make(chan algoContainer)
    go func () {
        for i := 0; i < n; i++ {
            result := list.Copy()
            // actually useful:
            if result.Less(n-1, 0) {
                result.Swap(n-1, 0)
            }
            out <- result
        }
        close(out)
    }()
    return out
}

Ответ 2

Так как язык программирования Go в настоящее время не поддерживает общие типы, это будет трудно сделать.

Почему у Go нет общего типа?

Обобщения могут быть добавлены в некоторых точка. Мы не чувствуем их, хотя мы понимаем некоторые программисты делают.

Дженерики удобны, но они приходят по стоимости по сложности в типе системы и времени выполнения. Мы еще не нашел дизайн, который дает ценность пропорционально сложности, хотя мы продолжаем думать о Это. Между тем, Go встроенных карт и ломтиками, а также возможность использования пустой интерфейс для построения контейнеры (с явным распаковкой) во многих случаях можно писать код, который делает какие дженерики позволят, если менее плавно.

Это остается открытой проблемой.

Посмотрите на пакет сортировки , чтобы увидеть, как он обрабатывает сравнения и другие операции, относящиеся к типу, определяя sort.Interface с помощью методов Len, Less и Swap.

Ответ 3

Go не имеет общих типов, но вы можете посмотреть, как sort работает, чтобы найти обходной путь. Они создают такой интерфейс:

type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less returns whether the element with index i should sort
    // before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

И теперь для любого настраиваемого типа вы можете создать соответствующий тип пользовательской коллекции, который можно отсортировать. Алгоритм сортировки должен иметь дело только с целыми числами и логическими значениями, и поэтому не видит и не заботится о том, каковы основные типы данных.