Go: Есть ли способ избежать реализации полной сортировки. Интерфейс для кусочков структур?

Question

Если у меня есть массив / фрагмент структур в Go и я хочу отсортировать их с помощью пакета sort, мне кажется, что мне нужно реализовать весь интерфейс сортировки, который содержит 3 метода:

• Len
• Swap
• Меньше

Кажется, что Len и Swap всегда должны иметь одинаковую реализацию независимо от типа структуры в массиве.

Есть ли способ избежать использования Len и Swap каждый раз, или это всего лишь ограничение из-за отсутствия Generics in Go?

Answer 1

Если вы выполняете несколько разных операций сравнения для одного и того же типа среза, вы можете использовать встраивание, чтобы избежать переопределения Len и Swap каждый раз.Вы также можете использовать эту технику для добавления параметров в сортировку, например, для сортировки в обратном порядке или нет, в зависимости от некоторого значения времени выполнения.

например,

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 2

Ваш собственный ответ правильный. В вашем случае массива или слайса реализации Len () и Swap () просты. Как len () Go может предоставить здесь собственный swap (). Но интерфейс, который используется сейчас, также может быть использован для более сложных структур данных, таких как BTrees. Это все еще позволяет функции Sort () работать (как моя параллельная быстрая сортировка, которая использует тот же интерфейс сортировки).

Answer 3

Если вы хотите отсортировать фрагменты (для которых Len и Swap всегда имеют одинаковую реализацию), пакет сортировки теперь имеет функцию, которая требует только реализации Less:

func Slice (интерфейс среза {}, меньше func (i, j int) bool)

Answer 4

Хотя это старый вопрос, я бы хотел указать на пакет github.com/bradfitz/slice.Но только в качестве примера или подтверждения концепции я бы не рекомендовал бы использовать это на самом деле (это задокументировано словом "брутто"):

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

В реальном коде я нахожу это совершенно тривиальным, быстрым, коротким,удобочитаемым и не отвлекающим просто сделать что-то вроде:

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
}

Здесь gofmt настаивает на пустой строке между строками type и func, но у него нет проблем с несколькими однострочнымифункции без пустых строк, и это хорошо выстраивает тела функций.Я нахожу это удобной для чтения компактной формой для таких вещей.

Что касается вашего комментария:

Кажется, что Len и Swap всегда должны иметь одну и ту же реализацию, независимо от типаstruct находится в [slice]

как раз на прошлой неделе мне нужна сортировка, которая объединяла пары элементов в срезе (для ввода в strings.NewReplacer), что требовало тривиального изменения, такого как:

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

Это не поддерживается интерфейсом, подобным интерфейсу github.com/bradfitz/slice.Опять же, я нахожу этот макет простым, компактным и читаемым.Хотя (возможно, даже больше в этом случае) другие могут не согласиться.