Источник: Nuances of Programming
Хеш-карты — невероятно полезная структура данных. Сопоставляя уникальные ключи с потенциально неуникальными значениями, они имеют постоянное время поиска O(1) и применяются в самых разных ситуациях.
Но есть и недостаток: обычно их нельзя сортировать. В современных языках программирования эту проблему решают по-разному. Так, в Python (начиная с версии 3.7) появилась сортировка хеш-карты с помощью лямбда-функции.
А на Go используют обычные интерфейсы и пакет sort. Интерфейс sort работает с различными структурами данных, в том числе хеш-картами: получается элегантная сортировка в несколько простых этапов.
1. Создаем пользовательские типы для представления пар и их списков
Чтобы хранить отсортированные значения, создадим два пользовательских типа данных для ключей и значений хеш-карты.
В структуре Pair свойства Key (ключ) и Value (значение) соответствуют базовым типам, находящимся в хеш-карте. Например, если хеш-карта инициализирована как map[string]bool{}, то ее Key будет с базовым типом string, а Value — с базовым типом bool.
В нашем случае Key и Value будут одного базового типа int:
type Pair struct {
Key int
Value int
}
type PairList []Pair
Затем определим type PairList, т. е. просто массив структур Pair.
2. В структуре данных «pair list» реализуем «sort.Interface»
Определив пользовательские структуры, реализуем в структуре PairList интерфейс sort.Interface. Согласно документации Golang, у него три открытых метода для реализации: Len(), Less() и Swap().
type Interface interface {
// Len — это количество элементов в коллекции.
Len() int
// Less сообщает, должен ли элемент с индексом i
// выполнять сортировку раньше элемента с индексом j.
//
// Когда Less(i, j) и Less(j, i) дают false,
// элементы с индексами i и j считаются эквивалентными.
// При сортировке Sort эквивалентные элементы в конечном результате располагаются в любом порядке,
// при Stable исходный порядок ввода эквивалентных элементов сохраняется.
//
// Less должен описывать транзитивное упорядочение:
// - когда Less(i, j) и Less(j, k) дают true, то Less(i, k) тоже должен быть true.
// - когда Less(i, j) и Less(j, k) дают false, то Less(i, k) тоже должен быть false.
//
// Обратите внимание: сравнение значений с плавающей запятой (оператор < в значениях float32 или float64)
// не является транзитивным упорядочением, когда задействуются нечисловые значения (NaN).
// Для корректной реализации значений с плавающей запятой см. Float64Slice.Less.
Less(i, j int) bool
// Swap меняет местами элементы с индексами i и j.
Swap(i, j int)
}
Чтобы добавить сортировку к любому объекту, реализуем в нем эти три метода и вызываем sort.Sort().
В нашем случае реализуем их в структуре PairList:
func (p PairList) Len() int { return len(p) }
func (p PairList) Less(i, j int) bool { return p[i].Value < p[j].Value }
func (p PairList) Swap(i, j int){ p[i], p[j] = p[j], p[i] }
Реализации простые, но их всегда можно настроить под себя. Хотите отсортировать по Key, а не по Value? Просто внесите соответствующее изменение в реализацию метода Less(). А хотите отсортировать в порядке убывания? Тогда поменяйте местами i и j. Все возможно благодаря интерфейсам Go.
3. Преобразуем карту в «pair list», отсортировываем и возвращаем «pair list»
Для примера сортировки инициализируем someMap и определяем pairList новым экземпляром PairList, равным по длине с someMap.
Перебираем someMap и присваиваем индекс для каждой пары ключ (k) — значение (v) нового экземпляра Pair внутри someMap.
Вызываем sort.Sort() в pairList.
someMap := map[int]int{
0: 2,
3: 7,
9: 3,
1: 5,
7: 6,
}
pairList := make(PairList, len(someMap))
pairListIdx := 0
for k, v := range(someMap) {
pairList[pairListIdx] = Pair{k,v}
pairListIdx++
}
fmt.Println(someMap)
fmt.Println("Unsorted PairList:", pairList)
sort.Sort(pairList)
fmt.Println("Sorted PairList:", pairList)
Запустив этот код в функции, получим вывод:
map[0:2 1:5 3:7 7:6 9:3]
Unsorted PairList: [{1 5} {7 6} {0 2} {3 7} {9 3}]
Sorted PairList: [{0 2} {9 3} {1 5} {7 6} {3 7}]
Теперь вы умеете реализовывать интерфейс sort.Sort в любой структуре данных как настоящий профессионал на Go.
Читайте также:
Перевод статьи Israel Miles: Think You Can’t Sort a Hash Map? Think Again!