На этом шаге рассмотрим примеры сортировки срезов и поиска значений.

Задание 1. Сравнить результаты сортировки строк библиотечной функцией sort.Strings и пользовательской SortFoldedStrings (рис.1):

Рис.1. Пример работы приложения

Раскрыть/скрыть решение и комментарии.

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

Функция sort.Strings() из стандартной библиотеки принимает срез типа []string и сортирует строки на месте, в порядке возрастания по значениям составляющих их байт. Если все строки закодированы с применением одного и того же способа отображения символов в байты (например, все они были созданы текущей программой или другой программой на языке Go), строки будут отсортированы по кодовым пунктам.

Пользовательская функция SortFoldedStrings() действует точно так же, за исключением того, что она сортирует строки без учета регистра символов, используя универсальную функцию sort.Sort().

Функция sort.Sort() способна сортировать элементы любого типа, предоставляющего методы, объявляемые интерфейсом sort.Interface, то есть элементы, имеющие методы Len(), Less() и Swap() с требуемыми сигнатурами.

Приведем пример пользовательской функции:

/*Функция SortFoldedStrings() просто вызывает функцию sort.Sort() из стандартной
библиотеки, преобразуя указанный срез типа []string в значение типа FoldedStrings
с помощью стандартного синтаксиса преобразования. Вообще говоря, всякий раз,
когда определяется пользовательский тип, основанный на встроенном типе,
значение встроенного типа можно преобразовать в значение пользовательского типа,
используя простой синтаксис преобразования.*/
func SortFoldedStrings(slice []string) {
	sort.Sort(FoldedStrings(slice))
}
/*Тип FoldedStrings предоставляет три метода, объявляемые интерфейсом sort.Interface.
Все методы имеют очень простую реализацию. Нечувствительность к регистру символов
в этом типе достигается за счет использования функции strings.ToLower() в методе
Less(). Если потребуется реализовать сортировку в порядке возрастания, достаточно
просто заменить в методе Less() оператор < на оператор >.
type FoldedStrings []string

func (slice FoldedStrings) Len() int { return len(slice) }
func (slice FoldedStrings) Less(i, j int) bool {
	return strings.ToLower(slice[i]) < strings.ToLower(slice[j])
}
func (slice FoldedStrings) Swap(i, j int) {
	slice[i], slice[j] = slice[j], slice[i]
}

Архив примера можно взять здесь.

Задание 2. Реализовать поиск определенного значения в срезе (рис.2):

Рис.2. Пример работы приложения

Раскрыть/скрыть решение и комментарии.

Простой линейный поиск пригоден только при работе с несортированными данными и только для небольших срезов (до нескольких сотен элементов). Но для огромных срезов, особенно когда поиск требуется выполнить многократно, линейный алгоритм оказывается весьма неэффективным – для поиска элемента в среднем приходится сравнить с искомым значением половину элементов.

В языке Go имеется метод sort.Search(), реализующий алгоритм поиска методом половинного деления: для выполнения поиска он требует выполнить не более log₂(n) сравнений (где n – количество элементов). Если взглянуть с этой точки зрения, алгоритм линейного поиска по 1 000 000 элементов требует в среднем выполнить 500 000 сравнений и в худшем случае – 1 000 000 сравнений; а алгоритм поиска методом половинного деления потребует выполнить максимум 20 сравнений, даже в самом худшем случае.

Задание 3. Реализовать поиск значения в срезе методом половтнного деления (рис.3):

Рис.3. Пример работы приложения

Раскрыть/скрыть решение и комментарии.

На следующем шаге рассмотрим понятие "отображения" в Go.

Предыдущий шаг Содержание Следующий шаг