algorithm - ejemplos - algoritmos geneticos pdf

hacer algoritmos genéricos en ir

Question

No puedo encontrar una manera limpia de implementar un algoritmo que funcione en cualquier tipo.

El siguiente código producirá errores al intentar convertir una cadena o segmento en las interfaces, y no se pueden comparar los objetos de la interfaz {}: 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
}

Aunque es un fastidio (creo que debería ser automático), puedo encapsular y unboxing rebanadas manualmente en la interfaz {} s, el problema real anterior es la comparación. Y cada vez se vuelve más y más kludgy.

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

Incluso he pensado en usar vector.Vector, pero mucha gente dice nunca usarlos.

Entonces, ¿debería implementar el mismo algoritmo para int slices y strings? ¿Qué hay de las porciones de myObject? Puedo hacer una interfaz con un func de comparación personalizado, pero ¿cómo hago que funcione con tipos estándar?

Answer 1

Dado que el Lenguaje de programación Go no admite actualmente tipos genéricos, esto será difícil de hacer.

¿Por qué Go no tiene tipos genéricos?

Los genéricos bien pueden agregarse en algún momento. No sentimos una urgencia para ellos, aunque entendemos que algunos programadores sí.

Los genéricos son convenientes pero tienen un costo en complejidad en el sistema de tipo y el tiempo de ejecución. Todavía no hemos encontrado un diseño que proporcione un valor proporcional a la complejidad, aunque seguimos pensando en ello. Mientras tanto, los mapas y sectores incorporados de Go, además de la capacidad de usar la interfaz vacía para construir contenedores (con unboxing explícito) significan en muchos casos que es posible escribir código que haga lo que los genéricos habilitarían, aunque con menos dificultad.

Esto sigue siendo un problema abierto.

Mire el paquete de ordenación Go para ver cómo maneja las comparaciones y otras operaciones específicas de un tipo definiendo el tipo sort.Interface con los métodos Len, Less e Swap.

Answer 2

Go no tiene tipos genéricos, pero puede echar un vistazo a cómo funciona el género para encontrar una solución alternativa. Lo que hacen es crear una interfaz como esta:

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)
}

Y ahora, para cualquier tipo personalizado, puede crear un tipo de colección personalizada correspondiente que pueda clasificarse. El algoritmo de ordenación solo tiene que tratar con enteros y booleanos, por lo que no ve ni se preocupa por los tipos de datos subyacentes.

Answer 3

Puede hacer esto en Ir usando interfaces. Una función que toma un tipo de interfaz es genérica en el sentido de que no le importa la representación de datos del tipo concreto subyacente. Hace todo a través de llamadas de método.

Para crear una versión genérica de su algoritmo, debe identificar todas las capacidades que el algoritmo requiere de los objetos de datos y debe definir los métodos que abstraen estas capacidades. Las firmas de métodos abstractos se convierten en conjuntos de métodos de interfaces.

Para hacer que un tipo sea compatible con este tipo de algoritmo genérico, defina métodos del tipo para satisfacer la interfaz del parámetro del algoritmo.

Tomaré tu código de ejemplo y mostraré una forma de hacerlo. La mayoría de las capacidades requeridas están cubiertas por sort.Inface, así que elegí incrustarlo. Solo se necesita una otra capacidad, una para hacer una copia de los datos.

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

A continuación se muestra un programa de trabajo completo realizado a partir de su código de ejemplo.

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
}