Sorting และ Quickselect ใน Go: ตั้งแต่ slices.Sort ถึงการหา Top-K ใน O(n)

การเรียง slice ใน Go ใช้แค่บรรทัดเดียวคือ slices.Sort(nums) แต่โจทย์จริงหลายข้อไม่ได้ต้องการ slice ที่เรียงครบทั้งหมด คำถามอย่าง "latency ที่ percentile 95 เท่าไร" หรือ "สินค้า 10 อันดับแรกที่ขายดีที่สุดคืออะไร" ต้องการแค่ตำแหน่งเดียวหรือแค่ top k ซึ่ง Go quickselect ตอบได้ในเวลาเฉลี่ย O(n) แทนที่จะเป็น O(n log n) และเพราะ standard library ของ Go ไม่มี quickselect มาให้ การรู้วิธีเขียนเองจึงมีประโยชน์

บทความนี้เริ่มจากเครื่องมือที่ใช้ทุกวัน (sort, slices, การเรียงหลาย key และการนับความถี่ด้วย map) จากนั้นสร้าง Lomuto partition, quicksort และ quickselect ขึ้นมาเอง แล้วนำไปแก้โจทย์ top-k แบบคลาสสิก

การเรียง slice ใน Go: sort เทียบกับ slices

Go มี package สำหรับเรียงข้อมูลสองตัว sort เป็นตัวดั้งเดิม ส่วน slices มาพร้อม generics ใน Go 1.21 และเป็นตัวที่ควรใช้ในปัจจุบัน ทั้งสองตัวใช้ pattern-defeating quicksort (pdqsort) อยู่เบื้องหลัง

nums := []int{5, 2, 9, 1, 5, 6}
slices.Sort(nums)  // [1 2 5 5 6 9]
sort.Ints(nums)    // same result, older API

names := []string{"mango", "Apple", "banana"}
slices.Sort(names) // [Apple banana mango]

slices.SortFunc มักเร็วกว่า sort.Slice เพราะทำงานกับค่าที่มี type ชัดเจน ไม่ต้องสลับค่าผ่านกลไกแบบ reflection และ comparator ก็อ่านง่ายกว่าด้วย

การเรียง string

การเปรียบเทียบ string ใน Go เทียบทีละ byte ตัวพิมพ์ใหญ่จึงมาก่อนตัวพิมพ์เล็ก "Apple" < "banana" ก็จริง แต่ "Zebra" < "apple" ก็จริงเช่นกัน ถ้าต้องการเรียงแบบไม่สนตัวพิมพ์ ให้เทียบสำเนาที่แปลงเป็นตัวเล็กแล้ว:

slices.SortFunc(names, func(a, b string) int {
	return strings.Compare(strings.ToLower(a), strings.ToLower(b))
})

ถ้าต้องการเรียงตัวอักษรภายใน string เช่นเพื่อเช็ก anagram ให้แปลงเป็น []rune ก่อน ตัวอักษรที่มีหลาย byte จะได้ไม่แตก:

func sortString(s string) string {
	r := []rune(s)
	slices.Sort(r)
	return string(r)
}

sortString("golang") // "agglno"

ถ้าไปเรียงเป็น []byte ตัวอักษรที่ไม่ใช่ ASCII จะพังทันที เหตุผลอธิบายไว้ใน string, byte และ rune ใน Go

เรียง struct ด้วยหลาย key

cmp.Or (Go 1.22) คืนค่าแรกที่ไม่ใช่ศูนย์ ทำให้ comparator แบบหลาย key สั้นลงมาก:

type Player struct {
	Name  string
	Score int
}

slices.SortFunc(players, func(a, b Player) int {
	return cmp.Or(
		cmp.Compare(b.Score, a.Score),  // higher score first
		strings.Compare(a.Name, b.Name), // then by name
	)
})

การสลับ a กับ b ใน cmp.Compare จะได้ลำดับจากมากไปน้อย ถ้าต้องการกลับด้าน slice ที่เรียงแล้ว ใช้ slices.Reverse

นับความถี่ด้วย map

การนับว่าแต่ละค่าปรากฏกี่ครั้งเป็นขั้นแรกของโจทย์จัดอันดับจำนวนมาก map[T]int ทำได้ในรอบเดียว:

words := strings.Fields("the cat and the dog and the bird")

counts := make(map[string]int)
for _, w := range words {
	counts[w]++ // missing keys start at zero
}

keys := make([]string, 0, len(counts))
for w := range counts {
	keys = append(keys, w)
}
slices.SortFunc(keys, func(a, b string) int {
	return cmp.Or(cmp.Compare(counts[b], counts[a]), strings.Compare(a, b))
})
// the 3, and 2, bird 1, cat 1, dog 1

ลำดับการวน map ใน Go เป็นแบบสุ่ม ถ้าลำดับของผลลัพธ์สำคัญ ต้องเรียง key เสมอ อ่านพฤติกรรมของ map เพิ่มเติมได้ใน slice, map และ pointer ใน Go

วิธีนี้ใช้ O(n) ในการนับ บวก O(m log m) ในการเรียง key ที่ไม่ซ้ำกัน m ตัว ถ้าต้องการแค่ไม่กี่อันดับแรก quickselect ช่วยตัดขั้นการเรียงออกได้

Lomuto partition: หัวใจของ quicksort

quicksort กับ quickselect ใช้ชิ้นส่วนพื้นฐานเดียวกันคือ partition เลือก pivot มาหนึ่งตัว แล้วจัด slice ใหม่ให้ทุกตัวที่น้อยกว่า pivot อยู่ทางซ้าย ที่เหลืออยู่ทางขวา pivot จะไปอยู่ในตำแหน่งสุดท้ายที่ถูกต้องพอดี

Lomuto เป็นแบบที่เขียนให้ถูกได้ง่ายที่สุด ใช้ index i หนึ่งตัวเป็นขอบของโซน "น้อยกว่า pivot" แล้วใช้ j ไล่ scan:

// partition rearranges a[lo..hi] around a random pivot and returns
// the pivot's final index p: a[lo..p-1] < a[p] <= a[p+1..hi].
func partition(a []int, lo, hi int) int {
	p := lo + rand.IntN(hi-lo+1) // math/rand/v2
	a[p], a[hi] = a[hi], a[p]    // move the pivot to the end
	pivot := a[hi]

	i := lo // a[lo..i-1] holds elements smaller than pivot
	for j := lo; j < hi; j++ {
		if a[j] < pivot {
			a[i], a[j] = a[j], a[i]
			i++
		}
	}
	a[i], a[hi] = a[hi], a[i] // place the pivot between the two parts
	return i
}

ลองไล่ดูด้วย pivot 4 บน [7 2 9 1 4]:

ทำไม pivot ต้องสุ่ม

แบบในตำราใช้ตัวสุดท้ายเป็น pivot เสมอ ถ้า input เรียงมาแล้ว pivot จะเป็นค่ามากที่สุดทุกครั้ง แต่ละรอบ partition ตัดออกได้แค่ตัวเดียว เวลาที่ใช้จะกลายเป็น O(n²) การสุ่ม pivot ทำให้กรณีแย่ที่สุดนี้แทบไม่มีโอกาสเกิด ไม่ว่า input จะเป็นแบบไหน

math/rand/v2 (Go 1.22) มี rand.IntN(n) ที่คืนตัวเลขในช่วง [0, n) ส่วน math/rand แบบเดิมมีฟังก์ชันเดียวกันในชื่อ rand.Intn(n) ตั้งแต่ Go 1.20 ทั้งสองตัว seed ให้อัตโนมัติ ไม่ต้องเรียก rand.Seed อีกแล้ว

Quicksort ใน Go

พอมี partition แล้ว quicksort เหลือ logic แค่สามบรรทัด คือ partition แล้วเรียงแต่ละฝั่ง:

func quickSort(a []int, lo, hi int) {
	if lo >= hi {
		return
	}
	p := partition(a, lo, hi)
	quickSort(a, lo, p-1)
	quickSort(a, p+1, hi)
}

quickSort(nums, 0, len(nums)-1)

การเขียน quicksort เองเป็นแบบฝึกหัดที่ดี แต่ใน production ให้ใช้ slices.Sort ซึ่งรับมือกับค่าซ้ำและ input ที่จงใจทำให้ช้าได้ดีกว่ามาก จุดอ่อนที่รู้กันของ Lomuto คือเมื่อมี element ที่เท่ากันจำนวนมาก partition จะเอียงข้างเดียว และประสิทธิภาพจะตกลงไปใกล้ O(n²) วิธีแก้คือ three-way partition (น้อยกว่า เท่ากัน มากกว่า)

Go quickselect: หา element ลำดับที่ k ใน O(n)

quicksort ลงไปทำต่อทั้ง สองฝั่ง ของ pivot แต่ quickselect สังเกตว่าหลัง partition หนึ่งรอบ เรารู้แน่นอนแล้วว่าตัวที่ k อยู่ฝั่งไหน จึงไปต่อแค่ฝั่งนั้นฝั่งเดียว

// quickSelect returns the k-th smallest element (0-based).
// It reorders a in place.
func quickSelect(a []int, k int) int {
	lo, hi := 0, len(a)-1
	for lo < hi {
		p := partition(a, lo, hi)
		switch {
		case p == k:
			return a[k]
		case p < k:
			lo = p + 1 // answer is on the right
		default:
			hi = p - 1 // answer is on the left
		}
	}
	return a[k]
}

โดยเฉลี่ยแต่ละรอบ partition จะลดช่วงที่เหลือลงครึ่งหนึ่ง งานรวมจึงประมาณ n + n/2 + n/4 + … ≈ 2n หรือ O(n) กรณีแย่สุดยังเป็น O(n²) แต่ถ้าสุ่ม pivot ก็แทบไม่เกิด

element ที่ มากที่สุด ลำดับที่ k คือตัวที่น้อยที่สุดลำดับที่ (len-k) ซึ่งใช้แก้โจทย์ LeetCode ที่รู้จักกันดีอย่าง "Kth Largest Element in an Array" ได้:

func findKthLargest(nums []int, k int) int {
	a := slices.Clone(nums) // don't reorder the caller's slice
	return quickSelect(a, len(a)-k)
}

findKthLargest([]int{3, 2, 1, 5, 6, 4}, 2) // 5

หา top-k ที่พบบ่อยที่สุดด้วย quickselect

พอเอา map นับความถี่มารวมกับ quickselect ก็แก้โจทย์ "Top K Frequent Elements" ได้โดยไม่ต้องเรียง key ทั้งหมด อัลกอริทึมเดิมเขียนเป็น generic ที่รับฟังก์ชัน less ได้แบบนี้:

// selectBy reorders a so that a[k] is the element that would be at index k
// if a were sorted by less, with every element before it not greater.
func selectBy[T any](a []T, k int, less func(x, y T) bool) {
	lo, hi := 0, len(a)-1
	for lo < hi {
		p := lo + rand.IntN(hi-lo+1)
		a[p], a[hi] = a[hi], a[p]
		i := lo
		for j := lo; j < hi; j++ {
			if less(a[j], a[hi]) {
				a[i], a[j] = a[j], a[i]
				i++
			}
		}
		a[i], a[hi] = a[hi], a[i]
		switch {
		case i == k:
			return
		case i < k:
			lo = i + 1
		default:
			hi = i - 1
		}
	}
}

func topKFrequent(nums []int, k int) []int {
	freq := make(map[int]int)
	for _, n := range nums {
		freq[n]++
	}
	keys := make([]int, 0, len(freq))
	for n := range freq {
		keys = append(keys, n)
	}
	if k >= len(keys) {
		return keys
	}
	// "less" means "more frequent", so the k most frequent land in keys[:k].
	selectBy(keys, k-1, func(x, y int) bool { return freq[x] > freq[y] })
	return keys[:k]
}

topKFrequent([]int{1, 1, 1, 2, 2, 3}, 2) // [1 2] in some order

ผลลัพธ์คือ top k แต่ไม่ได้เรียงกันเองภายใน ถ้าต้องการจัดอันดับ ให้เรียงแค่ k ตัวนั้นทีหลัง ซึ่งใช้ O(k log k)

เปรียบเทียบ Big-O

มีวิธีที่รับประกัน O(n) แม้ในกรณีแย่สุดอยู่ (median of medians) แต่ค่าคงที่สูงจนในทางปฏิบัติช้ากว่า quickselect แบบสุ่ม pivot

Big-O ไม่ได้บอกเวลาจริงเสมอไปเมื่อ input มีขนาดเล็ก ถ้าการเลือกมีผลจริง ให้ benchmark และ profile ด้วย pprof

คำถามที่พบบ่อย

sort.Slice ใน Go เป็น stable ไหม

ไม่ sort.Slice และ slices.SortFunc อาจสลับลำดับของ element ที่เท่ากันได้ ถ้าต้องรักษาลำดับเดิมของค่าที่เท่ากัน ให้ใช้ sort.SliceStable หรือ slices.SortStableFunc

sort.Slice กับ slices.SortFunc ต่างกันอย่างไร

sort.Slice รับ less(i, j int) bool ที่ทำงานกับ index ส่วน slices.SortFunc รับ comparator แบบ generic ที่ทำงานกับค่าโดยตรงและคืนค่าเป็น int slices.SortFunc จึง type-safe อ่านง่ายกว่า และมักเร็วกว่า

Go มี quickselect ในตัวไหม

ไม่มี standard library ไม่มีฟังก์ชันแบบ nth_element ของ C++ ทางเลือกคือเรียงแล้วดึงตาม index, ใช้ container/heap หรือเขียน quickselect เองตามตัวอย่างข้างบน

ควรใช้ quickselect หรือ heap สำหรับ top k

ใช้ quickselect เมื่อข้อมูลอยู่ใน slice ที่แก้ลำดับได้ และต้องการความเร็วเฉลี่ยสูงสุด ใช้ heap ขนาด k เมื่อข้อมูลเข้ามาเป็น stream, แก้ไข input ไม่ได้ หรือต้องการการรับประกัน O(n log k)

สรุปสิ่งที่ควรจำ

• ใช้ slices.Sort และ slices.SortFunc กับงานเรียงทั่วไป และใช้ cmp.Or เมื่อต้องเรียงหลาย key
• เรียง []rune ไม่ใช่ []byte เมื่อต้องจัดลำดับตัวอักษร
• นับด้วย map และเรียง key เมื่อลำดับมีความหมาย
• ใช้ quickselect เมื่อต้องการแค่ตำแหน่งเดียวหรือ top k แบบไม่เรียง และสุ่ม pivot เสมอ
• วัดผลก่อนตัดสินใจเอาโค้ดที่เขียนเองมาแทน sort ของ standard library

ถ้าทีมของคุณต้องการความช่วยเหลือกับ Go service ที่ต้องการประสิทธิภาพสูง Vectorkub รับพัฒนาและรีวิวระบบ backend