מיון slice ב-Golang: slices.Sort, SortFunc וכמה שדות

מיון טיפוסים מובנים

slices.Sort ממיינת כל slice שטיפוס האיבר שלו ניתן לסידור: מספרים שלמים, מספרים עשרוניים ומחרוזות. היא ממיינת במקום ולא מחזירה כלום.

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

פלט:

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

מחרוזות ממוינות לפי בתים, כך שכל אות ASCII גדולה באה לפני כל אות קטנה. זה כמעט אף פעם לא מה שמשתמש מצפה לו בשמות. הסעיף הבא מתקן את זה.

החבילה slices הגיעה ב-Go 1.21. ה-Sort שלה הוא pattern-defeating quicksort: O(n log n), במקום, ולא יציב.

סדר מותאם עם SortFunc

slices.SortFunc מקבלת פונקציית השוואה func(a, b T) int. החזירו מספר שלילי כש-a צריך לבוא קודם, מספר חיובי כש-b צריך לבוא קודם, ואפס כשהם שווים. פונקציית העזר cmp.Compare מחזירה בדיוק את זה לטיפוסים ניתנים לסידור.

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 בתוך השוואה מקצה מחרוזת חדשה בכל פעם שבקלט שלה יש אות גדולה, וההשוואה רצה בערך n log n פעמים. ב-slices גדולים, חשבו את המפתחות באותיות קטנות פעם אחת. לשמות בשפות אחרות (סימני הטעמה, כללי locale), השתמשו ב-golang.org/x/text/collate, שנמצאת מחוץ לספרייה הסטנדרטית.

פונקציית השוואה חייבת להיות עקבית: אם היא אומרת ש-a בא לפני b, היא חייבת לומר ש-b בא אחרי a. פונקציה ששוברת את זה (למשל, מחזירה -1 בכל פעם ששני ערכים שונים) מייצרת slice בסדר שגוי בלי שום שגיאה. חיסור של מספרים שלמים (return a - b) נראה מסודר אבל גולש בערכים גדולים; השתמשו ב-cmp.Compare.

מיון structs

פונקציית ההשוואה מקבלת איברים, כך שמיון structs לפי שדה הוא אותה קריאה:

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

עובדים עם משכורות שוות יכולים לצאת כאן בכל סדר, כי SortFunc לא יציבה. אם צריך סדר מובטח, שברו שוויון עם שדות נוספים או השתמשו במיון יציב.

מיון לפי כמה שדות

השוו קודם את השדה החשוב ביותר, ועברו לבא רק במקרה של שוויון. cmp.Or (Go 1.22) מחזירה את הארגומנט הראשון שלה שאינו אפס, וזה הופך את כל זה לשורה אחת:

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

פלט:

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

כל השוואה מוערכת גם כשהראשונה כבר מכריעה, כי הן ארגומנטים רגילים. זה עולה מעט בהשוואות של שדות. כששובר השוויון יקר, כתבו ביד את השרשרת if c := ...; c != 0 { return c }.

מיון יציב

מיון יציב שומר איברים שווים בהשוואה בסדר המקורי שלהם. זה חשוב כשלקלט כבר יש סדר משמעותי, למשל רשומות שממוינות לפי זמן ושעכשיו מקבצים אותן לפי משתמש.

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

זה מדפיס [{ana 2} {ana 4} {bob 1} {bob 3} {bob 5}]: בתוך כל משתמש, הרצף המקורי נשמר. מיון יציב עושה יותר עבודה, אז השתמשו בו רק כשהסדר של איברים שווים חשוב.

מיון map

ל-maps אין סדר. כדי להציג map ממוין לפי מפתח, מיינו את המפתחות שלו: slices.Sorted(maps.Keys(m)) (Go 1.23). כדי למיין לפי ערך, מיינו את המפתחות עם השוואה שמחפשת את הערכים:

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

שובר השוויון לפי המילה חשוב: בלעדיו, chan ו-slice (שניהם 7) היו מודפסים בסדר שונה מהרצה להרצה, כי המפתחות יוצאים מה-map בסדר אקראי. ראו maps לעוד פרטים.

החבילה sort: sort.Slice והחברים שלה

לפני Go 1.21, מיון עבר דרך החבילה sort. תראו אותה בהרבה קוד קיים:

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

הבדלים ששווה להכיר:

באג נפוץ ב-sort.Slice הוא closure שסוגר על slice אחר מזה שממוינים, כי פונקציית ה-less ניגשת לפי מיקום. ב-SortFunc הבאג הזה לא יכול לקרות כי היא מעבירה לכם את האיברים.

הטיפוס sort.Interface (Len, Less, Swap) הוא הצורה הוותיקה ביותר. הוא עדיין הדרך למיין נתונים שאינם slice יחיד, כמו שני slices מקבילים שצריכים לזוז יחד. מאז Go 1.22, sort.Ints, sort.Strings ו-sort.Float64s פשוט קוראות ל-slices.Sort.

טעויות נפוצות

• ציפייה ש-Sort תחזיר את ה-slice הממוין. היא ממיינת במקום ולא מחזירה כלום. השתמשו ב-slices.Sorted(slices.Values(s)) אם רוצים slice ממוין חדש, או ב-slices.Clone קודם.
• הנחה שאיברים שווים שומרים על הסדר שלהם. רק גרסאות ה-Stable מבטיחות את זה.
• חיסור כדי להשוות. a - b גולש. השתמשו ב-cmp.Compare.
• מיון מספרים עשרוניים עם NaN. cmp.Compare מסדרת את NaN לפני כל ערך אחר, וזה שומר על מיון עקבי. השוואה a < b שנכתבה ביד לא עושה את זה.