Golang Slice Sıralama: slices.Sort, SortFunc ve Birden Fazla Alan

Yerleşik tipleri sıralamak

slices.Sort, eleman tipi sıralanabilir olan her slice'ı sıralar: tam sayılar, float'lar ve string'ler. Yerinde sıralar ve hiçbir şey döndürmez.

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

Çıktı:

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

String'ler baytlara göre sıralanır, bu yüzden her büyük ASCII harfi her küçük harften önce gelir. Adlar için bir kullanıcının beklediği nadiren budur. Bir sonraki bölüm bunu düzeltiyor.

slices paketi Go 1.21'de geldi. Sort'u bir pattern-defeating quicksort'tur: O(n log n), yerinde ve kararlı değil.

SortFunc ile özel sıra

slices.SortFunc bir karşılaştırma fonksiyonu func(a, b T) int alır. a önce gelmeliyse negatif, b önce gelmeliyse pozitif, eşitlerse sıfır döndürün. cmp.Compare yardımcısı sıralanabilir tipler için tam olarak bunu döndürür.

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

Bir karşılaştırmanın içindeki strings.ToLower, girdisinde büyük harf olduğunda her seferinde yeni bir string ayırır ve karşılaştırma yaklaşık n log n kez çalışır. Büyük slice'lar için küçük harfli anahtarları bir kez hesaplayın. Başka dillerdeki adlar (aksanlar, yerel ayar kuralları) için standart kütüphanenin dışındaki golang.org/x/text/collate'i kullanın.

Bir karşılaştırma fonksiyonu tutarlı olmalıdır: a'nın b'den önce geldiğini söylüyorsa b'nin a'dan sonra geldiğini de söylemelidir. Bunu bozan bir fonksiyon (örneğin iki değer farklı olduğunda her zaman -1 döndüren) hiçbir hata vermeden yanlış sıralanmış bir slice üretir. Tam sayıları çıkarmak (return a - b) şık görünür ama büyük değerlerde taşar; cmp.Compare kullanın.

Struct'ları sıralamak

Karşılaştırma fonksiyonu elemanları alır, bu yüzden struct'ları bir alana göre sıralamak aynı çağrıdır:

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

Maaşları eşit olan çalışanlar burada herhangi bir sırayla çıkabilir, çünkü SortFunc kararlı değildir. Garantili bir sıraya ihtiyacınız varsa eşitlikleri daha fazla alanla bozun ya da kararlı bir sıralama kullanın.

Birden fazla alana göre sıralamak

En önemli alanı önce karşılaştırın ve yalnızca eşitlikte bir sonrakine geçin. cmp.Or (Go 1.22) sıfır olmayan ilk argümanını döndürür, bu da bunu tek bir satıra çevirir:

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

Çıktı:

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

Düz argümanlar oldukları için ilki karar verse bile her karşılaştırma değerlendirilir. Alan karşılaştırmaları için bunun maliyeti azdır. Bir eşitlik bozucu pahalıysa if c := ...; c != 0 { return c } zincirini elle yazın.

Kararlı sıralama

Kararlı bir sıralama, eşit karşılaştırılan elemanları orijinal sıralarında tutar. Girdinin zaten anlamlı bir sırası olduğunda bu önemlidir; örneğin zamana göre sıralanmış ve şimdi kullanıcıya göre grupladığınız kayıtlar.

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

Bu [{ana 2} {ana 4} {bob 1} {bob 3} {bob 5}] yazdırır: her kullanıcının içinde orijinal dizilim korunur. Kararlı sıralama daha fazla iş yapar, bu yüzden onu yalnızca eşit elemanların sırası önemli olduğunda kullanın.

Bir map'i sıralamak

Map'lerin sırası yoktur. Bir map'i anahtara göre sıralı göstermek için anahtarlarını sıralayın: slices.Sorted(maps.Keys(m)) (Go 1.23). Değere göre sıralamak için anahtarları değerlere bakan bir karşılaştırmayla sıralayın:

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

Kelimeye göre eşitlik bozmak önemlidir: o olmadan chan ve slice (ikisi de 7) çalıştırmadan çalıştırmaya farklı sırayla yazdırılırdı, çünkü anahtarlar map'ten rastgele sırayla çıkar. Daha fazlası için map'ler sayfasına bakın.

sort paketi: sort.Slice ve diğerleri

Go 1.21'den önce sıralama sort paketi üzerinden yapılıyordu. Var olan birçok kodda onu göreceksiniz:

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

Bilmeye değer farklar:

Yaygın bir sort.Slice hatası, less fonksiyonu konuma göre indekslediği için sıralanandan farklı bir slice'ı yakalamaktır. SortFunc size elemanları verdiği için bu hataya sahip olamaz.

sort.Interface tipi (Len, Less, Swap) en eski biçimdir. Birlikte hareket etmesi gereken iki paralel slice gibi tek bir slice olmayan veriyi sıralamanın yolu hâlâ odur. Go 1.22'den beri sort.Ints, sort.Strings ve sort.Float64s basitçe slices.Sort'u çağırır.

Sık yapılan hatalar

• Sort'un sıralanmış slice'ı döndürmesini beklemek. Yerinde sıralar ve hiçbir şey döndürmez. Yeni bir sıralı slice istiyorsanız slices.Sorted(slices.Values(s)) kullanın ya da önce slices.Clone yapın.
• Eşit elemanların sıralarını koruduğunu varsaymak. Bunu yalnızca Stable çeşitleri vaat eder.
• Karşılaştırmak için çıkarma yapmak. a - b taşar. cmp.Compare kullanın.
• NaN içeren float'ları sıralamak. cmp.Compare, NaN'ı diğer her değerden önce sıralar ve bu da sıralamayı tutarlı tutar. Elle yazılmış bir a < b karşılaştırması bunu yapmaz.