Sortowanie slice w Golang: slices.Sort, SortFunc i wiele pól

Sortowanie typów wbudowanych

slices.Sort sortuje dowolny slice, którego typ elementu jest uporządkowany: liczby całkowite, zmiennoprzecinkowe i stringi. Sortuje w miejscu i nic nie zwraca.

package main

import (
	"fmt"
	"slices"
)

func main() {
	nums := []int{42, 7, 19, 3, 88}
	slices.Sort(nums)
	fmt.Println(nums)

	names := []string{"lisa", "Bob", "alice", "Carl"}
	slices.Sort(names)
	fmt.Println(names) // byte order: uppercase before lowercase

	fmt.Println(slices.IsSorted(nums))

	i, found := slices.BinarySearch(nums, 19)
	fmt.Println(i, found)
}

Wynik:

[3 7 19 42 88]
[Bob Carl alice lisa]
true
2 true

Stringi są sortowane według bajtów, więc każda wielka litera ASCII trafia przed każdą małą. Rzadko tego oczekuje użytkownik przy imionach. Następna sekcja to naprawia.

Pakiet slices pojawił się w Go 1.21. Jego Sort to pattern-defeating quicksort: O(n log n), w miejscu i niestabilny.

Własna kolejność z SortFunc

slices.SortFunc przyjmuje funkcję porównującą func(a, b T) int. Zwróć liczbę ujemną, gdy a ma być pierwsze, dodatnią, gdy pierwsze ma być b, i zero, gdy są równe. Funkcja pomocnicza cmp.Compare zwraca dokładnie to dla typów uporządkowanych.

package main

import (
	"cmp"
	"fmt"
	"slices"
	"strings"
)

func main() {
	names := []string{"lisa", "Bob", "alice", "Carl"}
	slices.SortFunc(names, func(a, b string) int {
		return cmp.Compare(strings.ToLower(a), strings.ToLower(b))
	})
	fmt.Println(names)

	// Descending: swap a and b.
	nums := []int{42, 7, 19, 3, 88}
	slices.SortFunc(nums, func(a, b int) int {
		return cmp.Compare(b, a)
	})
	fmt.Println(nums)

	// By length, shortest first.
	words := []string{"banana", "fig", "apple", "kiwi"}
	slices.SortFunc(words, func(a, b string) int {
		return cmp.Compare(len(a), len(b))
	})
	fmt.Println(words)
}

strings.ToLower wewnątrz porównania alokuje nowy string za każdym razem, gdy wejście ma wielką literę, a porównanie wykonuje się około n log n razy. Dla dużych slice'ów oblicz klucze małymi literami raz. Dla imion w innych językach (znaki diakrytyczne, reguły lokalne) użyj golang.org/x/text/collate, który jest poza biblioteką standardową.

Funkcja porównująca musi być spójna: jeśli mówi, że a jest przed b, musi też mówić, że b jest po a. Funkcja, która to łamie (na przykład zwraca -1 zawsze, gdy dwie wartości się różnią), daje źle posortowany slice bez żadnego błędu. Odejmowanie liczb (return a - b) wygląda zgrabnie, ale przepełnia się dla dużych wartości; użyj cmp.Compare.

Sortowanie struktur

Funkcja porównująca dostaje elementy, więc sortowanie struktur po polu to to samo wywołanie:

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Employee struct {
	Name   string
	Dept   string
	Salary int
}

func main() {
	staff := []Employee{
		{"Ana", "eng", 120},
		{"Bob", "sales", 90},
		{"Cy", "eng", 150},
		{"Dee", "sales", 90},
		{"Eve", "eng", 120},
	}

	slices.SortFunc(staff, func(a, b Employee) int {
		return cmp.Compare(a.Salary, b.Salary)
	})
	for _, e := range staff {
		fmt.Println(e.Salary, e.Name)
	}
}

Pracownicy z równą pensją mogą tu wyjść w dowolnej kolejności, bo SortFunc nie jest stabilne. Jeśli potrzebujesz gwarantowanej kolejności, rozstrzygaj remisy kolejnymi polami albo użyj sortowania stabilnego.

Sortowanie po wielu polach

Najpierw porównaj najważniejsze pole i przejdź do następnego tylko przy remisie. cmp.Or (Go 1.22) zwraca pierwszy niezerowy argument, co zamienia to w jedną linię:

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Employee struct {
	Name   string
	Dept   string
	Salary int
}

func main() {
	staff := []Employee{
		{"Ana", "eng", 120},
		{"Bob", "sales", 90},
		{"Cy", "eng", 150},
		{"Dee", "sales", 90},
		{"Eve", "eng", 120},
	}

	// Department A to Z, then salary high to low, then name A to Z.
	slices.SortFunc(staff, func(a, b Employee) int {
		return cmp.Or(
			cmp.Compare(a.Dept, b.Dept),
			cmp.Compare(b.Salary, a.Salary),
			cmp.Compare(a.Name, b.Name),
		)
	})
	for _, e := range staff {
		fmt.Printf("%-6s %4d %s\n", e.Dept, e.Salary, e.Name)
	}
}

Wynik:

eng     150 Cy
eng     120 Ana
eng     120 Eve
sales    90 Bob
sales    90 Dee

Każde porównanie jest obliczane, nawet gdy pierwsze już rozstrzyga, bo to zwykłe argumenty. Przy porównywaniu pól kosztuje to niewiele. Gdy rozstrzyganie remisu jest drogie, napisz łańcuch if c := ...; c != 0 { return c } ręcznie.

Sortowanie stabilne

Sortowanie stabilne zachowuje pierwotną kolejność elementów, które są sobie równe. Ma to znaczenie, gdy dane wejściowe mają już sensowną kolejność, na przykład rekordy posortowane po czasie, które teraz grupujesz według użytkownika.

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Event struct {
	User string
	Seq  int
}

func main() {
	events := []Event{
		{"bob", 1}, {"ana", 2}, {"bob", 3}, {"ana", 4}, {"bob", 5},
	}
	slices.SortStableFunc(events, func(a, b Event) int {
		return cmp.Compare(a.User, b.User)
	})
	fmt.Println(events)
}

To wypisuje [{ana 2} {ana 4} {bob 1} {bob 3} {bob 5}]: w obrębie każdego użytkownika pierwotna kolejność zostaje zachowana. Sortowanie stabilne wykonuje więcej pracy, więc używaj go tylko wtedy, gdy kolejność równych elementów ma znaczenie.

Sortowanie mapy

Mapy nie mają kolejności. Aby pokazać mapę posortowaną po kluczu, posortuj jej klucze: slices.Sorted(maps.Keys(m)) (Go 1.23). Aby posortować po wartości, posortuj klucze funkcją porównującą, która odczytuje wartości:

package main

import (
	"cmp"
	"fmt"
	"maps"
	"slices"
)

func main() {
	wordCount := map[string]int{"go": 12, "map": 3, "slice": 7, "chan": 7}

	keys := slices.Collect(maps.Keys(wordCount))
	slices.SortFunc(keys, func(a, b string) int {
		return cmp.Or(
			cmp.Compare(wordCount[b], wordCount[a]), // count, high first
			cmp.Compare(a, b),                       // then word, for a stable result
		)
	})
	for _, k := range keys {
		fmt.Println(k, wordCount[k])
	}
}

Rozstrzyganie remisu po słowie ma znaczenie: bez niego chan i slice (oba 7) wypisywałyby się w innej kolejności przy każdym uruchomieniu, bo klucze wychodzą z mapy w losowej kolejności. Więcej na stronie o mapach.

Pakiet sort: sort.Slice i spółka

Przed Go 1.21 sortowanie odbywało się przez pakiet sort. Zobaczysz go w dużej ilości istniejącego kodu:

sort.Ints(nums)
sort.Strings(names)
sort.Slice(staff, func(i, j int) bool {
	return staff[i].Salary < staff[j].Salary
})
sort.SliceStable(staff, func(i, j int) bool { ... })

Różnice, które warto znać:

Częsty błąd z sort.Slice to domknięcie na innym slice'ie niż ten, który jest sortowany, bo funkcja less indeksuje według pozycji. SortFunc nie może mieć tego błędu, bo przekazuje ci elementy.

Typ sort.Interface (Len, Less, Swap) to najstarsza forma. Nadal służy do sortowania danych, które nie są pojedynczym slice'em, na przykład dwóch równoległych slice'ów, które muszą przesuwać się razem. Od Go 1.22 sort.Ints, sort.Strings i sort.Float64s po prostu wywołują slices.Sort.

Typowe błędy

• Oczekiwanie, że Sort zwróci posortowany slice. Sortuje w miejscu i nic nie zwraca. Użyj slices.Sorted(slices.Values(s)), jeśli chcesz nowy posortowany slice, albo najpierw slices.Clone.
• Założenie, że równe elementy zachowają kolejność. Obiecują to tylko warianty Stable.
• Odejmowanie w porównaniu. a - b się przepełnia. Użyj cmp.Compare.
• Sortowanie liczb zmiennoprzecinkowych z NaN. cmp.Compare stawia NaN przed każdą inną wartością, co zachowuje spójność sortowania. Ręcznie napisane porównanie a < b tego nie robi.