Ordinare uno slice in Golang: slices.Sort, SortFunc e più campi

Ordinare i tipi integrati

slices.Sort ordina qualsiasi slice il cui tipo di elemento sia ordinabile: interi, float e stringhe. Ordina sul posto e non restituisce nulla.

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

Output:

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

Le stringhe si ordinano per byte, quindi ogni lettera ASCII maiuscola viene prima di ogni minuscola. Per i nomi raramente è ciò che un utente si aspetta. La prossima sezione risolve il problema.

Il pacchetto slices è arrivato con Go 1.21. Il suo Sort è un pattern-defeating quicksort: O(n log n), sul posto e non stabile.

Ordine personalizzato con SortFunc

slices.SortFunc accetta una funzione di confronto func(a, b T) int. Restituisci un numero negativo quando a deve venire prima, un numero positivo quando deve venire prima b e zero quando sono uguali. La funzione cmp.Compare restituisce esattamente questo per i tipi ordinabili.

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 dentro un confronto alloca una nuova stringa ogni volta che l'input contiene una maiuscola, e il confronto viene eseguito circa n log n volte. Per slice grandi, calcola le chiavi in minuscolo una sola volta. Per nomi in altre lingue (accenti, regole locali) usa golang.org/x/text/collate, che è fuori dalla libreria standard.

Una funzione di confronto deve essere coerente: se dice che a viene prima di b, deve dire che b viene dopo a. Una che viola questa regola (per esempio restituendo -1 ogni volta che due valori sono diversi) produce uno slice ordinato male senza alcun errore. Sottrarre interi (return a - b) sembra elegante ma va in overflow con valori grandi; usa cmp.Compare.

Ordinare struct

La funzione di confronto riceve gli elementi, quindi ordinare struct per un campo è la stessa chiamata:

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

Qui i dipendenti con lo stesso stipendio possono uscire in qualsiasi ordine, perché SortFunc non è stabile. Se ti serve un ordine garantito, risolvi i pareggi con altri campi oppure usa un ordinamento stabile.

Ordinare per più campi

Confronta prima il campo più importante e passa al successivo solo in caso di pareggio. cmp.Or (Go 1.22) restituisce il primo argomento diverso da zero, e questo riduce tutto a una riga:

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

Output:

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

Ogni confronto viene valutato anche quando il primo decide, dato che sono semplici argomenti. Per i confronti tra campi costa poco. Quando un criterio di spareggio è costoso, scrivi a mano la catena if c := ...; c != 0 { return c }.

Ordinamento stabile

Un ordinamento stabile mantiene nel loro ordine originale gli elementi che risultano uguali. Conta quando l'input ha già un ordine significativo, per esempio record ordinati per tempo che ora raggruppi per utente.

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

Stampa [{ana 2} {ana 4} {bob 1} {bob 3} {bob 5}]: dentro ogni utente, la sequenza originale resta intatta. L'ordinamento stabile fa più lavoro, quindi usalo solo quando l'ordine degli elementi uguali conta.

Ordinare una mappa

Le mappe non hanno un ordine. Per mostrare una mappa ordinata per chiave, ordina le sue chiavi: slices.Sorted(maps.Keys(m)) (Go 1.23). Per ordinare per valore, ordina le chiavi con un confronto che legge i valori:

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

Lo spareggio sulla parola è importante: senza, chan e slice (entrambe 7) verrebbero stampate in un ordine diverso a ogni esecuzione, perché le chiavi escono dalla mappa in ordine casuale. Vedi mappe per saperne di più.

Il pacchetto sort: sort.Slice e simili

Prima di Go 1.21 l'ordinamento passava dal pacchetto sort. Lo troverai in molto codice esistente:

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

Differenze utili da conoscere:

Un bug comune con sort.Slice è catturare nella closure uno slice diverso da quello che si sta ordinando, dato che la funzione less indicizza per posizione. SortFunc non può avere questo bug perché ti passa gli elementi.

Il tipo sort.Interface (Len, Less, Swap) è la forma più vecchia. Resta il modo per ordinare dati che non sono un singolo slice, come due slice paralleli che devono muoversi insieme. Da Go 1.22, sort.Ints, sort.Strings e sort.Float64s chiamano semplicemente slices.Sort.

Errori comuni

• Aspettarsi che Sort restituisca lo slice ordinato. Ordina sul posto e non restituisce nulla. Usa slices.Sorted(slices.Values(s)) se vuoi un nuovo slice ordinato, oppure prima slices.Clone.
• Dare per scontato che gli elementi uguali mantengano il loro ordine. Solo le varianti Stable lo garantiscono.
• Sottrarre per confrontare. a - b va in overflow. Usa cmp.Compare.
• Ordinare float con NaN. cmp.Compare mette NaN prima di ogni altro valore, e questo mantiene coerente l'ordinamento. Un confronto scritto a mano a < b no.