Стабільний вивід: сортування ключів і слайсів

1. Стабільний вивід і map

Якщо ви тільки починаєте, може здаватися, що порядок виводу — річ суто естетична: усі елементи вивели, то яка різниця, у якому порядку. Проблема в тому, що порядок раптово стає важливим у двох випадках: коли ви порівнюєте результати на око («що змінилося?») і коли їх порівнює програма — автотести, скрипти чи перевірні системи.

Уявіть, що ви пишете невелику утиліту, яка виводить статистику: скільки разів траплялося кожне слово, які теги унікальні, які задачі позначено виконаними. Ви запускаєте програму двічі з однаковим введенням — і очікуєте однаковий текст. Якщо порядок рядків «плаває», нервують і люди, і тести. А нервові тести — це як кіт у стресі: він може скинути все зі столу просто тому, що сьогодні не той настрій.

Обхід map відбувається у «випадковому» порядку

Коли ми робимо:

for k, v := range m {
    fmt.Println(k, v)
}

ми отримуємо коректний обхід: усі пари «ключ → значення» будуть відвідані рівно по одному разу, якщо ви не змінюєте мапу під час обходу. Однак порядок обходу не є частиною контракту. Це означає, що не можна будувати логіку на кшталт «перший ключ — найменший» або «останній ключ — найновіший». У map у Go немає понять «перший» і «останній».

Тут є важливий практичний нюанс: навіть якщо сьогодні у вас «випадково» все виглядає відсортованим, це ще не обіцянка. Завтра буде інший запуск, інше середовище, інша версія — і порядок уже може змінитися. В офіційних матеріалах про сумісність Go окремо наводять приклад, коли зміна реалізації сортування між версіями міняла порядок рівних елементів, і через це ламалися програми, які «очікували конкретного виводу».

Звідси просте правило: якщо порядок важливий для людини або тестів, його потрібно задавати явно.

Базовий рецепт: «ключі → сортування → друк»

Найзручніший спосіб упорядкувати map звучить майже як кулінарний рецепт, тільки замість каструлі — слайс. Робимо так: збираємо всі ключі в окремий слайс, сортуємо його, а потім друкуємо пари строго в порядку відсортованих ключів. Тобто сортуємо ми не map — її напряму сортувати не можна, — а слайс ключів.

Щоб тримати картинку в голові, можна уявити це так:

flowchart TD
    A[мапа: ключ → значення] --> B["зібрали ключі в []K"]
    B --> C["відсортували []K"]
    C --> D["for _, k := range keys: друкуємо k і m[k]"]

Тепер — до коду. Почнімо з маленької заготовки для нашого прикладу: мініпрограми, яка рахує частоти слів (частотний словник). Це зручно, бо map[string]int одночасно демонструє і лічильник, і потребу в стабільному виводі.

2. Сортування простих ключів у пакеті sort

Коли ключі — рядки або числа, найпростіше скористатися пакетом sort. Пакет sort — старий, надійний і перевірений часом.

Приклад: вивід map[string]int за абеткою

Порахуємо слова й друкуватимемо частоти. Спершу покажемо нестабільний вивід — так робити не треба, — а потім виправимо.

package main

import "fmt"

func main() {
	counts := map[string]int{"go": 3, "map": 1, "sort": 2}

	for w, c := range counts {
		fmt.Println(w, c) // порядок не гарантується
	}
}

Тепер зробімо стабільний вивід: зібрали ключі, відсортували їх, вивели.

package main

import (
	"fmt"
	"sort"
)

func main() {
	counts := map[string]int{"go": 3, "map": 1, "sort": 2}

	keys := make([]string, 0, len(counts))
	for k := range counts {
		keys = append(keys, k)
	}
	sort.Strings(keys)

	for _, k := range keys {
		fmt.Println(k, counts[k]) // go 3 / map 1 / sort 2 (завжди однаково)
	}
}

Особливо корисний тут виклик make([]string, 0, len(counts)): ми одразу резервуємо місткість під усі ключі й не змушуємо append зайвий раз розширювати буфер. Це не «оптимізація заради оптимізації», а просто акуратність.

Приклад: якщо ключі — числа (sort.Ints)

Іноді ключ — не рядок, а, наприклад, ID. Рецепт той самий, змінюються лише тип ключів і сортування.

package main

import (
	"fmt"
	"sort"
)

func main() {
	m := map[int]string{10: "ten", 2: "two", 7: "seven"}

	keys := make([]int, 0, len(m))
	for k := range m {
		keys = append(keys, k)
	}
	sort.Ints(keys)

	for _, k := range keys {
		fmt.Println(k, m[k]) // 2 two / 7 seven / 10 ten
	}
}

Важлива думка: стабільність тут з’являється тому, що ключі унікальні. Якщо ключі унікальні, навіть «нестабільне» сортування все одно дає один і той самий результат, бо немає рівних елементів, які можна переставляти.

3. Сортування за правилом: sort.Slice

Дуже швидко вам захочеться не просто «за абеткою», а «за змістом». Наприклад: вивести слова за спаданням частоти, а якщо частоти рівні — за абеткою. Або вивести рядки за довжиною. Або вивести числа так, щоб спочатку були парні, а потім непарні.

Для таких випадків у пакеті sort є універсальний інструмент — sort.Slice. Він сортує будь-який слайс, якщо ви дасте правило порівняння у вигляді функції less(i, j int) bool.

Під капотом усе просто: елемент з індексом i має йти раніше елемента з індексом j, якщо less(i, j) == true.

Приклад: сортуємо рядки за довжиною і додаємо tie-breaker

package main

import (
	"fmt"
	"sort"
)

func main() {
	words := []string{"go", "gopher", "map", "slices"}

	sort.Slice(words, func(i, j int) bool {
		if len(words[i]) != len(words[j]) {
			return len(words[i]) < len(words[j])
		}
		return words[i] < words[j] // додаткове правило для детермінізму
	})

	fmt.Println(words) // [go map gopher slices]
}

Зверніть увагу на другу гілку: return words[i] < words[j]. Це tie-breaker, тобто додаткове правило для рівних елементів. Воно дуже важливе, якщо ви хочете справді детермінований вивід.

Чому це важливо? Тому що різні версії й різні реалізації сортування можуть по-різному переставляти елементи, які за вашим основним критерієм вважаються рівними. У матеріалах про сумісність Go прямо підкреслюється, що зміни реалізації сортування можуть змінювати порядок рівних елементів, і спиратися на «випадковий» порядок рівних не можна.

Приклад: сортуємо ключі мапи за значеннями

Повернімося до нашого map[string]int з лічильником. Ми хочемо вивести найчастіше слово першим. Оскільки сортувати map не можна, ми сортуємо ключі, але порівнюємо їх через значення в мапі.

package main

import (
	"fmt"
	"sort"
)

func main() {
	counts := map[string]int{"go": 3, "map": 1, "sort": 3}

	keys := make([]string, 0, len(counts))
	for k := range counts {
		keys = append(keys, k)
	}

	sort.Slice(keys, func(i, j int) bool {
		wi, wj := keys[i], keys[j]
		if counts[wi] != counts[wj] {
			return counts[wi] > counts[wj] // більше — раніше
		}
		return wi < wj // рівні частоти впорядкуємо за абеткою
	})

	for _, k := range keys {
		fmt.Println(k, counts[k])
	}
}

Зауважте, як акуратно ми задаємо додаткове правило: якщо частоти рівні, ми все одно впорядковуємо ключі через wi < wj. Це робить вивід залізобетонним: однаковий ввід — однаковий вивід.

4. Пакет slices: Sort і SortFunc

Починаючи з Go 1.21, стандартна бібліотека отримала пакет slices, який містить багато зручних операцій над слайсами, зокрема й сортування. Зазвичай він читається простіше, ніж комбінації через sort.Interface. У релізних нотатках окремо зазначається, що slices додає функції для сортування й загалом робить роботу зі слайсами зручнішою та ергономічнішою.

Нас сьогодні цікавлять дві функції: slices.Sort (коли елементи можна природно впорядкувати — числа, рядки) і slices.SortFunc (коли потрібен власний порядок).

slices.Sort: сортування рядків і чисел «у лоб»

package main

import (
	"fmt"
	"slices"
)

func main() {
	nums := []int{5, 2, 10, 2}
	slices.Sort(nums)

	fmt.Println(nums) // [2 2 5 10]
}

Важливо пам’ятати: slices.Sort сортує на місці і нічого не повертає. Така модель для сортування цілком нормальна: перестановка елементів не змінює довжину слайса, отже повертати новий слайс не обов’язково.

До речі, у пакеті slices є й функції, які повертають новий слайс, наприклад для видалення діапазону. І тут типова помилка новачка — проігнорувати значення, яке повертається. У матеріалах Go якраз розбирають такі граблі: slices.Sort(s) справді не повертає значення, а от slices.Delete повертає новий слайс, і ігнорувати результат не можна.

slices.SortFunc: сортування за компаратором

sort.Slice просить less(i, j) bool, а slices.SortFunc просить функцію порівняння елементів: cmp(a, b T) int.

Контракт зазвичай такий:

• якщо a має йти раніше b, повертаємо від’ємне число;
• якщо пізніше — додатне;
• якщо з точки зору сортування вони рівні — 0.

Зробімо сортування рядків за довжиною, як раніше, але через slices.SortFunc:

package main

import (
	"fmt"
	"slices"
)

func main() {
	words := []string{"go", "gopher", "map", "slices"}

	slices.SortFunc(words, func(a, b string) int {
		if len(a) != len(b) {
			return len(a) - len(b)
		}
		if a < b {
			return -1
		}
		if a > b {
			return 1
		}
		return 0
	})

	fmt.Println(words) // [go map gopher slices]
}

Так, тут трохи більше рядків, ніж хотілося б, зате логіка порівняння тепер працює безпосередньо з елементами a і b, без індексів. Для початківців це часто читається легше: ви порівнюєте значення, а не «елементи з індексом i».

І знову зверніть увагу: додаткове правило обов’язкове, якщо ви хочете детермінований результат. 0 повертаємо лише тоді, коли рядки справді однакові; інакше краще самостійно впорядкувати їх додатковим правилом.

5. Приклад: частотний словник зі стабільним виводом

Тепер зберемо все в маленьку програму, яка читає слова зі стандартного вводу, рахує частоти й друкує результат у стабільному вигляді. Ми покажемо два режими виводу: за абеткою та за частотою. Це не повноцінний застосунок, але це чесний шматок практики: ви побачите, як мапа перетворюється на акуратний, передбачуваний звіт.

Читання слів і підрахунок

package main

import "fmt"

func main() {
	counts := make(map[string]int)

	for {
		var w string
		_, err := fmt.Scan(&w)
		if err != nil {
			break
		}
		counts[w]++
	}

	fmt.Println("унікальних слів:", len(counts)) // наприклад: унікальних слів: 3
}

Тут ми використовуємо fmt.Scan у циклі «до помилки». Коли введення завершиться (EOF), Scan поверне помилку, і ми вийдемо з циклу. Нам не потрібно заглиблюватися у види помилок; достатньо самого факту: є помилка — значить, читання завершено.

Стабільний вивід за абеткою (sort.Strings)

package main

import (
	"fmt"
	"sort"
)

func printAlpha(counts map[string]int) {
	keys := make([]string, 0, len(counts))
	for k := range counts {
		keys = append(keys, k)
	}
	sort.Strings(keys)

	for _, k := range keys {
		fmt.Println(k, counts[k])
	}
}

Цю функцію приємно викликати: вона не змінює мапу, а просто друкує. І друкує завжди однаково.

Стабільний вивід за частотою (sort.Slice)

package main

import (
	"fmt"
	"sort"
)

func printByCount(counts map[string]int) {
	keys := make([]string, 0, len(counts))
	for k := range counts {
		keys = append(keys, k)
	}

	sort.Slice(keys, func(i, j int) bool {
		a, b := keys[i], keys[j]
		if counts[a] != counts[b] {
			return counts[a] > counts[b]
		}
		return a < b
	})

	for _, k := range keys {
		fmt.Println(k, counts[k])
	}
}

Навіть якщо два слова трапилися однакову кількість разів, ми все одно друкуємо їх в одному порядку — за абеткою. Саме такі дрібниці й роблять програму передбачуваною.

Викличемо обидва варіанти з main

package main

import "fmt"

func main() {
	counts := map[string]int{"go": 3, "map": 1, "sort": 3}

	fmt.Println("== за абеткою ==")
	printAlpha(counts)

	fmt.Println("== за частотою ==")
	printByCount(counts)
}

6. Типові помилки під час стабільного виводу та сортування

Помилка №1: «Я відсортував ключі, але друкую через range по map».
Це виглядає так: ви зробили sort.Strings(keys), а потім випадково написали for k, v := range m { ... }. У результаті ключі у вас відсортовані, але вони взагалі не використовуються, і порядок знову «танцює». Правильна думка тут проста: відсортоване джерело порядку — це слайс keys, тож друкувати потрібно саме for _, k := range keys.

Помилка №2: немає додаткового правила під час сортування за вторинним критерієм.
Наприклад, ви сортуєте слова за частотою і повертаєте counts[a] > counts[b], а якщо частоти рівні — просто повертаєте false. Тоді рівні елементи можуть переставлятися як завгодно, і вивід стане нестабільним. Це особливо прикро, бо «майже завжди працює», а потім раптом починає блимати в тестах. Оновлення реалізації сортування між версіями Go можуть змінити порядок рівних елементів, тож спиратися на це не можна.

Помилка №3: очікувати, що сортування поверне новий слайс, і далі працювати зі старим.
Функції сортування в sort і slices змінюють слайс на місці. Тому якщо ви хочете зберегти початковий порядок, спершу зробіть копію (наприклад, через append([]T(nil), s...)) і сортуйте її. Окремо майте на увазі, що в пакеті slices є функції, які змінюють дані на місці (наприклад, slices.Sort), і є функції, які повертають новий слайс (наприклад, slices.Delete), тож ігнорування результату в другому випадку — класична пастка.

Помилка №4: намагатися «відсортувати map».
Іноді новачок шукає щось на кшталт sort.Map(m) або намагається перетворити мапу на «відсортовану мапу». У Go такого немає в базовому вигляді: map — це структура для швидкого доступу за ключем, а не для зберігання елементів у порядку. Якщо потрібен порядок — його задають поверх мапи: ключі в слайс, сортування, вивід.

Помилка №5: компаратор у slices.SortFunc повертає «що завгодно».
Якщо функція порівняння іноді повертає 1, іноді -1 для однакових значень або порушує здоровий глузд «якщо a < b, то b > a», сортування може поводитися дивно. Тримайтеся простого контракту: від’ємне — «раніше», додатне — «пізніше», нуль — «рівні». І намагайтеся повертати 0 лише тоді, коли елементи справді рівні; інакше краще розв’язати порядок додатковим правилом.