Сортировка словарей в Go

Введение

В отличие от многих других языков программирования, в Go словари (карты или maps) являются неупорядоченными коллекциями. В ходе этой лабораторной работы мы научимся сортировать словари и использовать их более гибко для решения различных задач.

Основные концепции:

Сортировка словарей
Обмен местами ключей и значений в словаре
Срезы словарей
Словари, где значениями являются срезы
Особенности словарей как ссылочных типов данных

Сортировка словарей

Создайте файл map.go в директории ~/project:

touch ~/project/map.go

Запишите следующий код в файл map.go:

package main

import (
 "fmt"
)

func main() {
 // Объявление и инициализация карты со строковыми ключами и целочисленными значениями
 // Карта хранит имена студентов и их баллы
 m := map[string]int{
  "Alice":   99, // Каждая пара ключ-значение представляет студента и его балл
  "Bob":     38,
  "Charlie": 84,
 }

 // Итерация по карте с помощью цикла for-range
 // 'key' представляет имена студентов, 'value' — баллы
 for key, value := range m {
  fmt.Println(key, value)
 }

 fmt.Println("\nInsert Data")

 // Демонстрация добавления новой пары ключ-значение в карту
 // Синтаксис: map[key] = value
 m["David"] = 25

 // Повторная итерация для отображения обновленного содержимого карты
 // Обратите внимание, что порядок может меняться при каждом выполнении
 for key, value := range m {
  fmt.Println(key, value)
 }
}

Запустите программу:

go run ~/project/map.go

Вывод программы может выглядеть примерно так:

Charlie 84
Bob 38
Alice 99

Insert Data
David 25
Charlie 84
Bob 38
Alice 99

Результат может отличаться, так как порядок вставки данных не фиксирован. Это фундаментальная особенность карт в Go — они не гарантируют определенного порядка элементов при итерации.

Вы можете попробовать запустить программу несколько раз и заметить, что последовательность вывода меняется. Это подтверждает, что нельзя полагаться на порядок элементов в map.

Однако иногда возникает необходимость отсортировать словарь после добавления данных. Как этого добиться?

Поскольку сама карта не может быть отсортирована, мы можем преобразовать её в срез (slice), а затем отсортировать этот срез.

Сортировка по ключу

Сначала разберем, как отсортировать словарь по ключу.

Алгоритм действий следующий:

Извлечь все ключи словаря в срез. Срез — это упорядоченный динамический массив, который поддается сортировке.
Отсортировать срез, используя встроенный пакет Go sort.
Получить соответствующие значения, обращаясь к словарю по упорядоченным ключам из среза.

Запишите следующий код в файл map.go:

package main

import (
 "fmt"
 "sort"
)

func main() {
 // Инициализация словаря
 m1 := map[int]string{
  3: "Bob",
  1: "Alice",
  2: "Charlie",
 }
 keys := make([]int, 0, len(m1)) // Инициализация среза с указанием емкости. Это оптимизация производительности — срез сразу выделяет память под размер карты, избегая лишних переаллокаций.
 for key := range m1 {
  // Добавление ключа в срез
  keys = append(keys, key)
 }
 // Сортировка среза ключей с помощью пакета sort. Функция sort.Ints() специально предназначена для срезов целых чисел.
 sort.Ints(keys)
 for _, key := range keys {
  // Теперь вывод будет упорядоченным
  fmt.Println(key, m1[key])
 }
}

Запустите программу:

go run ~/project/map.go

Вывод программы будет следующим:

1 Alice
2 Charlie
3 Bob

С помощью этого подхода мы реализовали сортировку словаря на основе ключа. Ключи извлекаются в срез, сортируются, а затем используются для последовательного обращения к значениям в исходной карте.

Обмен местами ключей и значений в словаре

Прежде чем перейти к сортировке по значению, научимся менять ключи и значения местами.

Инверсия словаря означает, что бывшие значения становятся ключами, а бывшие ключи — значениями, как показано на схеме ниже:

Dictionary key value swap

Реализация довольно проста. Запишите следующий код в файл map.go:

package main

import "fmt"

func main() {
 m := map[string]int{
  "Alice":   99,
  "Bob":     38,
  "Charlie": 84,
 }
 m2 := map[int]string{}
 for key, value := range m {
  m2[value] = key
 }
 fmt.Println(m2)
}

Запустите программу:

go run ~/project/map.go

Вывод программы будет следующим:

map[38:Bob 84:Charlie 99:Alice]

Суть этого кода заключается в извлечении пар из исходного словаря и их повторной вставке в новый словарь с переменой ролей. Обратите внимание: так как map не упорядочен, порядок вывода пар в инвертированном словаре может быть произвольным.

Сортировка по значению

Объединив логику сортировки по ключу и технику обмена ключей и значений, мы можем отсортировать словарь по значению.

Принцип работы: мы меняем ключи и значения местами, а затем используем новые ключи (которые были исходными значениями) как базу для сортировки. После этого мы используем отсортированные "ключи" для поиска соответствующих оригинальных ключей в инвертированной карте.

Запишите следующий код в файл map.go:

package main

import (
 "fmt"
 "sort"
)

func main() {
 // Инициализация словаря
 m1 := map[string]int{
  "Alice":   99,
  "Bob":     38,
  "Charlie": 84,
 }

 // Инициализация инвертированного словаря
 m2 := map[int]string{}
 for key, value := range m1 {
  // Создаем m2, меняя местами ключ и значение
  m2[value] = key
 }

 values := make([]int, 0) // Инициализация среза для сортировки
 for _, value := range m1 {
  // Переносим значения исходного словаря в срез
  values = append(values, value)
 }
 // Сортируем срез значений
 sort.Ints(values)

 for _, value := range values {
  // Теперь вывод упорядочен по значению
  fmt.Println(m2[value], value)
 }
}

Запустите программу:

go run ~/project/map.go

Вывод программы будет следующим:

Bob 38
Charlie 84
Alice 99

Теперь мы отсортировали словарь на основе его значений. Мы преобразовали значения в срез, отсортировали его и использовали эти данные для извлечения соответствующих ключей из вспомогательной карты.

Сортировка с помощью sort.Slice

Если вы используете версию Go выше 1.7, можно применять функцию sort.Slice для быстрой сортировки карты по ключу или значению. sort.Slice позволяет задать произвольную функцию сравнения.

Вот пример:

package main

import (
 "fmt"
 "sort"
)

func main() {
 m1 := map[int]int{
  21: 99,
  12: 98,
  35: 17,
  24: 36,
 }

 // Определяем структуру для хранения пары ключ-значение
 type kv struct {
  Key   int
  Value int
 }

 var s1 []kv

 for k, v := range m1 {
  s1 = append(s1, kv{k, v})
 }

 // Сортируем срез структур с помощью пользовательской функции
 sort.Slice(s1, func(i, j int) bool {
  return s1[i].Key < s1[j].Key
 })

 fmt.Println("Sorted in ascending order by key:")
 for _, pair := range s1 {
  fmt.Printf("%d, %d\n", pair.Key, pair.Value)
 }
}

Запустите программу:

go run ~/project/map.go

Вывод будет следующим:

Sorted in ascending order by key:
12, 98
21, 99
24, 36
35, 17

В этой программе мы использовали структуру kv для хранения пар из карты. Затем мы отсортировали срез этих структур с помощью sort.Slice() и анонимной функции сравнения. Эта функция (func(i, j int) bool) определяет порядок сортировки на основе поля Key.

Мы также можем использовать sort.Slice для сортировки в порядке убывания или по значению, просто изменив логику в функции сравнения. Это дает огромную гибкость при работе с данными словаря.

Небольшой тест

Создайте файл map2.go и измените код из предыдущего раздела так, чтобы отсортировать карту в порядке убывания на основе значения.

Ожидаемый результат:

Запустите программу:

go run ~/project/map2.go

Sorted in descending order by value:
21, 99
12, 98
24, 36
35, 17

Требования:

Файл map2.go должен находиться в директории ~/project.
Вы должны использовать функцию sort.Slice. Вам потребуется изменить функцию сравнения, использованную в предыдущем примере.

Срезы словарей

Подобно тому, как мы используем массивы или срезы для хранения обычных данных, мы можем создавать срезы, элементами которых являются словари. Это позволяет хранить коллекции структурированной информации.

Запишите следующий код в файл map.go:

package main

import "fmt"

func main() {
 // Объявление среза карт и его инициализация с помощью make
 var mapSlice = make([]map[string]string, 3) // Создает срез емкостью 3, где каждый элемент — это map[string]string.
 for index, value := range mapSlice {
  fmt.Printf("index:%d value:%v\n", index, value)
 }
 fmt.Println("Initialization")
 // Присвоение значений первому элементу среза
 mapSlice[0] = make(map[string]string, 10) // Инициализируем карту по первому индексу.
 mapSlice[0]["name"] = "labex"
 mapSlice[0]["password"] = "123456"
 mapSlice[0]["address"] = "Paris"
 for index, value := range mapSlice {
  fmt.Printf("index:%d value:%v\n", index, value)
 }
}

Запустите программу:

go run ~/project/map.go

Вывод программы будет следующим:

index:0 value:map[]
index:1 value:map[]
index:2 value:map[]
Initialization
index:0 value:map[address:Paris name:labex password:123456]
index:1 value:map[]
index:2 value:map[]

Этот код демонстрирует инициализацию среза карт. Изначально каждый элемент среза является пустой (nil) картой. Затем мы создаем и присваиваем карту первому элементу, заполняя её данными. Это показывает, как управлять списком словарей.

Словари со срезами в качестве значений

Мы также можем использовать словари, где значениями являются срезы. Это позволяет связать несколько значений с одним ключом, создавая связь типа "один ко многим".

Запишите следующий код в файл map.go:

package main

import "fmt"

func main() {
 var sliceMap = make(map[string][]string, 3) // Карта, где ключи — строки, а значения — срезы строк.
 key := "labex"
 value, ok := sliceMap[key]  // Проверка существования ключа
 if !ok {
  value = make([]string, 0, 2) // Если ключа нет, инициализируем новый срез.
 }
 value = append(value, "Paris", "Shanghai") // Добавляем значения в срез.
 sliceMap[key] = value // Сохраняем срез как значение для ключа в карте.
 fmt.Println(sliceMap)
}

Запустите программу:

go run ~/project/map.go

Вывод программы будет следующим:

map[labex:[Paris Shanghai]]

Код сначала объявляет тип карты со срезами. Перед добавлением элементов в срез выполняется проверка на существование ключа — это стандартный паттерн при работе с картами срезов.

Особенности словарей как ссылочных типов

Массивы в Go являются типами значений, поэтому при их присваивании или передаче в функцию создается копия. Изменения в копии не влияют на оригинал. Однако карты (maps) являются ссылочными типами. Это означает, что при передаче карты в функцию передается ссылка на те же базовые данные.

Это критически важно: любые изменения, внесенные внутри функции, отразятся на исходном словаре.

Запишите следующий код в файл map.go:

package main

import "fmt"

func modifyMap(x map[string]int) {
 x["Bob"] = 100 // Изменяет карту, переданную в качестве аргумента.
}

func main() {
 a := map[string]int{
  "Alice":   99,
  "Bob":     38,
  "Charlie": 84,
 }
 // Поскольку карта передается по ссылке, изменения в modifyMap затронут оригинал
 modifyMap(a)
 fmt.Println(a) // map[Alice:99 Bob:100 Charlie:84]
}

Запустите программу:

go run ~/project/map.go

Вывод программы будет следующим:

map[Alice:99 Bob:100 Charlie:84]

В этом примере мы наглядно увидели ссылочную природу словаря. Функция modifyMap изменила исходную карту, так как переменная a ссылается на ту же область памяти, где хранятся данные карты.

Резюме

В ходе этой лабораторной работы мы изучили продвинутые способы использования карт в Go, включая:

Сортировку карт по ключу или значению путем преобразования карты в срез и последующей сортировки среза.
Инверсию карт (обмен ключей и значений местами).
Использование срезов карт для создания коллекций структурированных данных.
Использование карт со срезами в качестве значений для реализации связей "один ко многим".
Ссылочную природу карт, из-за которой изменения в переданной карте отражаются на оригинале.

Понимание этих концепций позволит вам эффективно использовать словари Go в реальных приложениях.