Ir: ¿Hay alguna manera de evitar la implementación de la ordenación completa? ¿Intercalación para segmentos de estructuras?

Question

Si tengo una matriz/rebanada de estructuras en Go y quiero ordenar el uso de la clasificación de paquetes me parece que tengo que poner en práctica toda la interfaz especie que contiene 3 métodos:

• Len
• Intercambiar
• Menos

parece que Len y de intercambio siempre deben tener la misma aplicación sin importar el tipo de estructura se encuentra en la matriz.

¿Hay alguna manera de evitar tener el implemento Len e Intercambiar cada vez o esto es solo una limitación por la falta de genéricos en Go?

Answer 1

Tu propia respuesta es correcta. En su caso de una matriz o división, las implementaciones de Len() y Swap() son simples. Al igual que len() Go podría proporcionar un swap nativo() aquí. Pero la interfaz que se usa ahora también se puede usar para estructuras de datos más complejas como BTrees. Aún permite que la función Sort() funcione (como mi quicksort paralelo, que usa la misma interfaz de clasificación).

Answer 2

Si está implementando varias operaciones de comparación diferentes en el mismo tipo de división, puede usar la incorporación para evitar redefinir Len e Intercambiar cada vez. También puede usar esta técnica para agregar parámetros a la ordenación, por ejemplo, ordenar en reversa o no dependiendo de algún valor de tiempo de ejecución.

p. Ej.

package main 

import (
    "sort" 
) 

type T struct { 
    Foo int 
    Bar int 
} 

// TVector is our basic vector type. 
type TVector []T 

func (v TVector) Len() int { 
    return len(v) 
} 

func (v TVector) Swap(i, j int) { 
    v[i], v[j] = v[j], v[i] 
} 

// default comparison. 
func (v TVector) Less(i, j int) bool { 
    return v[i].Foo < v[j].Foo 
} 

// TVectorBarOrdered embeds TVector and overrides 
// its Less method so that it is ordered by the Bar field. 
type TVectorBarOrdered struct { 
    TVector 
} 

func (v TVectorBarOrdered) Less(i, j int) bool { 
    return v.TVector[i].Bar < v.TVector[j].Bar 
} 

// TVectorArbitraryOrdered sorts in normal or reversed 
// order depending on the order of its Reversed field. 
type TVectorArbitraryOrdered struct { 
    Reversed bool 
    TVector 
} 

func (v TVectorArbitraryOrdered) Less(i, j int) bool { 
    if v.Reversed { 
     i, j = j, i 
    } 
    return v.TVector[i].Foo < v.TVector[j].Foo 
} 

func main() { 
    v := []T{{1, 3}, {0, 6}, {3, 2}, {8, 7}} 
    sort.Sort(TVector(v)) 
    sort.Sort(TVectorBarOrdered{v}) 
    sort.Sort(TVectorArbitraryOrdered{true, v}) 
} 

Answer 3

Aunque esta es una vieja pregunta, me gustaría señalar el paquete github.com/bradfitz/slice . Pero como un ejemplo o prueba de concepto único, me no recomendar esta realidad ser utilizado (se documenta con la palabra "bruto"):

Utiliza operaciones, de bajo nivel bruto para hacer más fácil para ordenar sectores arbitrarios con solo una función menor, sin definir un nuevo tipo con operaciones Len e Intercambiar.

En código real, creo que es completamente trivial, rápido y corto, fácil de leer, y no distraer a simplemente hacer algo como:

type points []point 

func (p []points) Len() int  { return len(p) } 
func (p []points) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 
func (p []points) Less(i, j int) bool { 
     // custom, often multi-line, comparison code here 
} 

Aquí gofmt insiste en una línea en blanco entre el type y func líneas pero no tiene ningún problema con múltiples funciones de una línea sin líneas en blanco y alinea muy bien los cuerpos de las funciones. Me parece una buena forma compacta legible para tales cosas.

En cuanto a su comentario de que:

Parece que Len y de intercambio siempre deben tener la misma aplicación sin importar el tipo de estructura se encuentra en la [rebanada]

simplemente la otra semana necesito una especie que mantuvo pares de elementos en una rebanada juntos (para entrada a strings.NewReplacer) que requiere una variación trivial como:

type pairByLen []string 

func (p pairByLen) Len() int   { return len(p)/2 } 
func (p pairByLen) Less(i, j int) bool { return len(p[i*2]) > len(p[j*2]) } 
func (p pairByLen) Swap(i, j int) { 
     p[i*2], p[j*2] = p[j*2], p[i*2] 
     p[i*2+1], p[j*2+1] = p[j*2+1], p[i*2+1] 
} 

Esto no es compatible con una interfaz como la de github.com/bradfitz/slice. Una vez más, considero que este diseño es fácil, compacto y legible. Aunque (tal vez más en este caso), otros pueden estar en desacuerdo.

Answer 4

Si desea ordenar las rebanadas (para el que Len y de intercambio siempre tienen la misma aplicación), la clasificación de paquetes tiene ahora una función que sólo requiere una implementación de Menos:

func Slice(slice interface{}, less func(i, j int) bool)