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

Введение

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

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

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

Skills Graph

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

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

touch ~/project/map.go

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

package main

import (
	"fmt"
)

func main() {
	// Declare and initialize a map with string keys and integer values
	// The map stores student names and their scores
	m := map[string]int{
		"Alice":   99, // Each key-value pair represents a student and their score
		"Bob":     38,
		"Charlie": 84,
	}

	// Iterate through the map using a for-range loop
	// 'key' represents student names, 'value' represents scores
	for key, value := range m {
		fmt.Println(key, value)
	}

	fmt.Println("\nInsert Data")

	// Demonstrate how to add a new key-value pair to the map
	// The syntax is: map[key] = value
	m["David"] = 25

	// Iterate again to show the updated map contents
	// Note that the order may be different in each execution
	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

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

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

Но иногда нам нужно отсортировать словарь после вставки данных. Как это можно сделать?

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

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

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

Вот шаги:

• Преобразуйте ключи словаря в срез (slice). Срез представляет собой упорядоченный динамический массив, который можно отсортировать.
• Отсортируйте срез с помощью встроенного пакета sort в Go.
• Получите соответствующие значения с использованием метода поиска в словаре. Поскольку мы знаем порядок ключей в нашем срезе, мы можем найти значения в словаре (map), и они будут отображены в отсортированном порядке ключей.

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

package main

import (
	"fmt"
	"sort"
)

func main() {
	// Initialize the dictionary
	m1 := map[int]string{
		3: "Bob",
		1: "Alice",
		2: "Charlie",
	}
	keys := make([]int, 0, len(m1)) // Initialize the slice with capacity. This is a performance optimization -  the slice will allocate memory equal to the size of the map initially, avoiding re-allocations.
	for key := range m1 {
		// Convert the key to a slice
		keys = append(keys, key)
	}
	// Sort the key slice using the sort package. The `sort.Ints()` function specifically sorts a slice of integers.
	sort.Ints(keys)
	for _, key := range keys {
		// The output is in order now
		fmt.Println(key, m1[key])
	}
}

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

go run ~/project/map.go

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

1 Alice
2 Charlie
3 Bob

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

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

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

Обмен ключей и значений означает замену положений ключей и значений в словаре, как показано на следующем рисунке:

Реализация кода проста. Напишите следующий код в файл 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() {
	// Initialize the dictionary
	m1 := map[string]int{
		"Alice":   99,
		"Bob":     38,
		"Charlie": 84,
	}

	// Initialize the reversed dictionary
	m2 := map[int]string{}
	for key, value := range m1 {
		// Generate the reversed dictionary m2 by swapping the key-value pairs
		m2[value] = key
	}

	values := make([]int, 0) // Initialize the sorting slice
	for _, value := range m1 {
		// Convert the values of the original dictionary to a slice
		values = append(values, value)
	}
	// Sort the value slice using the sort package
	sort.Ints(values)

	for _, value := range values {
		// The output is in order now
		fmt.Println(m2[value], value)
	}
}

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

go run ~/project/map.go

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

Bob 38
Charlie 84
Alice 99

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

Сортировка с использованием sort.Slice

Если версия Go позднее 1.7, мы можем использовать функцию sort.Slice для быстрой сортировки словаря (map) по ключу или значению. Функция 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 и измените код из предыдущего раздела, чтобы отсортировать словарь (map) в порядке убывания по значению.

Ожидаемый вывод:

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

go run ~/project/map2.go

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

Требования:

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

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

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

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

package main

import "fmt"

func main() {
	// Declare a slice of maps and initialize it using make
	var mapSlice = make([]map[string]string, 3) // Creates a slice with a capacity of 3, where each element can be a `map[string]string`.
	for index, value := range mapSlice {
		fmt.Printf("index:%d value:%v\n", index, value)
	}
	fmt.Println("Initialization")
	// Assign values to the first element of the slice
	mapSlice[0] = make(map[string]string, 10) // Creates a map at the first index.
	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[]

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

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

Мы также можем использовать словари (map), в которых значениями являются срезы, чтобы хранить больше данных в словаре. Это позволяет нам связать несколько значений с одним ключом в словаре, фактически создавая "один-ко-многим" (one-to-many) отношение.

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

package main

import "fmt"

func main() {
	var sliceMap = make(map[string][]string, 3) // Declares a map where keys are strings and values are slices of strings. The 3 is a capacity hint.
	key := "labex"
	value, ok := sliceMap[key]  // Checks if the key exists
	if!ok {
		value = make([]string, 0, 2) // If it doesn't exist, initialize a new slice with capacity.
	}
	value = append(value, "Paris", "Shanghai") // Appends values to the slice.
	sliceMap[key] = value // Sets the slice as the value for our key in the map.
	fmt.Println(sliceMap)
}

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

go run ~/project/map.go

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

map[labex:[Paris Shanghai]]

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

Характеристики словарей как ссылочного типа

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

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

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

package main

import "fmt"

func modifyMap(x map[string]int) {
	x["Bob"] = 100 // Modifies the map that was passed as an argument.
}

func main() {
	a := map[string]int{
		"Alice":   99,
		"Bob":     38,
		"Charlie": 84,
	}
	// Because the map is passed by reference, the modification in modifyMap changes the original dictionary
	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 является ссылкой на одни и те же базовые данные словаря. Это поведение важно понимать при передаче словарей в функции.

Итог

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

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

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