ترتيب الشرائح في Golang: slices.Sort وSortFunc وعدة حقول

ترتيب الأنواع المدمجة

ترتّب slices.Sort أي شريحة نوع عنصرها قابل للترتيب: الأعداد الصحيحة والعشرية والنصوص. ترتّب في المكان ولا تعيد شيئًا.

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 مرة. للشرائح الكبيرة احسب المفاتيح بالحروف الصغيرة مرة واحدة. وللأسماء في لغات أخرى (العلامات، وقواعد اللغة المحلية) استخدم golang.org/x/text/collate، وهي خارج المكتبة القياسية.

يجب أن تكون دالة المقارنة متّسقة: إذا قالت إن a يأتي قبل b، يجب أن تقول إن b يأتي بعد a. الدالة التي تكسر هذا (مثلًا بإعادة -1 كلما اختلفت قيمتان) تنتج شريحة مرتّبة خطأ دون أي خطأ ظاهر. طرح الأعداد الصحيحة (return a - b) يبدو أنيقًا لكنه يفيض مع القيم الكبيرة؛ استخدم cmp.Compare.

ترتيب البنى

تتلقّى دالة المقارنة العناصر، فترتيب البنى حسب حقل هو الاستدعاء نفسه:

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}]: داخل كل مستخدم يبقى التسلسل الأصلي. الترتيب المستقر يؤدّي عملًا أكثر، فاستخدمه فقط عندما يهمّ ترتيب العناصر المتساوية.

ترتيب خريطة

لا ترتيب للخرائط. لعرض خريطة مرتّبة حسب المفتاح، رتّب مفاتيحها: 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) بترتيب مختلف من تشغيل إلى آخر، لأن المفاتيح تخرج من الخريطة بترتيب عشوائي. راجع الخرائط للمزيد.

الحزمة 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 هو الإغلاق على شريحة غير الشريحة التي تُرتَّب، لأن دالة less تفهرس بالموضع. ولا يمكن أن يقع هذا الخطأ مع SortFunc لأنها تسلّمك العناصر.

النوع sort.Interface (Len وLess وSwap) هو الشكل الأقدم. وما زال الطريقة لترتيب بيانات ليست شريحة واحدة، مثل شريحتين متوازيتين يجب أن تتحرّكا معًا. ومنذ Go 1.22 تستدعي sort.Ints وsort.Strings وsort.Float64s ببساطة slices.Sort.

أخطاء شائعة

• توقّع أن تعيد Sort الشريحة المرتّبة. ترتّب في المكان ولا تعيد شيئًا. استخدم slices.Sorted(slices.Values(s)) إذا أردت شريحة مرتّبة جديدة، أو slices.Clone أولًا.
• افتراض أن العناصر المتساوية تحتفظ بترتيبها. صيغ Stable وحدها تعد بذلك.
• الطرح للمقارنة. a - b يفيض. استخدم cmp.Compare.
• ترتيب أعداد عشرية فيها NaN. يضع cmp.Compare قيمة NaN قبل كل قيمة أخرى، وهذا يبقي الترتيب متّسقًا. أما مقارنة a < b المكتوبة يدويًا فلا.