Это статья об основах программирования на Go. На канале я рассказываю об опыте перехода в IT с нуля, структурирую информацию и делюсь мнением.
UPD: спустя год после публикации, вернулся к этой теме, чтобы пересмотреть алгоритмы сортировки. Обнаружил ошибки в коде, опубликованные в этой статье. Фрагменты кода использовать на свой страх и риск.
Хой, джедаи и амазонки!
В посте я рассказываю о шести способах сортировки массивов/срезов. Показываю примеры кода, а также проверяю длительность работы алгоритмов сортировки с применением пакета "time" на массиве из 100 тысяч интовых элементах.
В конце даётся наглядное сравнение результатов, а ещё некоторые мысли о релевантности подобных экспериментов анализа эффективности алгоритмов.
1. Общая информация
Прохожу в курсе тему алгоритмов сортировки. Нам там дают всего несколько алгоритмов, а я решил копнуть глубже и нашёл много интересного.
Вообще, сортированные массивы (срезы) использовать намного проще, чем несортированные. И процесс сортировки - важный и полезный. Другой вопрос - нужно ли дотошно изучать эти алгоритмы сортировки? Для меня, как практика в первую очередь (я надеюсь им быть), скорее полезно знать - что есть разные алгоритмы сортировки, и одни эффективнее других.
1.1. Применение сортированных массивов
Где применяются сортированные массивы? В базах данных, а это:
- Социальные сети: с использованием сортированных массивов можно легко и быстро отсортировать список друзей по алфавиту, по количеству друзей, по дате последнего визита и т.д. Это делает поиск нужных контактов более удобным и быстрым.
- Телефонные книги: в телефонных книгах используются сортированные массивы, чтобы быстро найти нужный контакт. Контакты могут быть отстированы по имени, фамилии, номеру телефона или по любым другим параметрам.
- Поиск в интернете: при поиске информации в интернете сортированные массивы используются для быстрого и эффективного поиска. Например, при поиске товаров в интернет-магазине можно отсортировать их по цене, рейтингу, бренду и т.д.
А ещё сортированные массивы применяют в алгоритмах сжатия данных: такие алгоритмы позволяют уменьшить размер данных, не теряя при этом информации. Например, сортированные массивы могут использоваться для устранения повторяющихся значений в данных.
В целом, сортированные массивы - это мощный инструмент для обработки и хранения данных во многих областях IT. Они ускоряют работу с данными и позволяют быстро находить нужную информацию.
Вот какие они полезные - сортированные массивы.
1.2. Виды сортированных массивов
Какие я рассмотрю в этой статье способы:
- Cортировка пузырьком - O(n^2).
- Cортировка выбором - O(n^2).
- Cортировка вставками O(n^2).
- Быстрая сортировка - O(n x log n).
- Сортировка слиянием - O(n x log n).
В списке я использовал О-большое. Что это такое? Можно о нём почитать, например, здесь.
Я в этой статье нашёл интересную тезу:
В задачах на программирование самое сложное и интересное — попытаться обойтись простым циклом, без вложенного, или даже вообще без цикла.
Мне сразу вспомнилась задача на написание кода "ёлочка". Там я рассчитывал ширину основания ёлочки по высоте: сперва циклом, затем - формулой. Это типичный пример, как без цикла можно решить некоторые задачи.
Далее поехали разбираться с кодом.
2. Алгоритмы сортировки
Сперва мы создаём массив с использованием генератора случайных чисел. Ничего необычного.
В строке 19 указан размер массива - почему 100 000? Да просто так, методом тыка - чтобы алгоритмы прокачали "железо" более-менее, а не выполнились за одну триллионную долю секунды, или наоборот - не нагрузили.
Чтобы следовать принципам чистого кода, я стараюсь разбивать код на смысловые функции. И обеспечить, чтобы функции выполняли только что-то одно, а не множество различных действий.
Вот тут я обнаружил интересную штуку:
В Go вернуть массив произвольной длины из функции невозможно. Для этого используют срезы: массивы применяют редко, но о них нам полезно знать, т.к. срезы содержат в себе массивы.
Суть в чём - вернуть из функции массив, для которого длина задана константой - можно. Но я не хочу использовать глобальные (и любые другие) константы, а, например - иметь возможность ввести длину массива с консоли.
Это база - дальше к ней цепляем алгоритмы.
2.1. Сортировка пузырьком
В функцию main() дописываем код:
И такой фрагмент - функция сортировки пузырьком:
Что здесь интересного?
- В стоке 15 я создал пустой массив той же длины, как и созданный ранее с сгенерированными случайным образом числами.
- В строке 17 я использую функцию копирования значений массива с сгенерированными элементами в массив с нулевыми элементами. Это необходимо, чтобы при сортировке последующими алгоритмами мы продолжили использовать исходный массив, а не его отсортированную версию.
- Строка 18 и 20 даёт нам разницу во времени между операцией.
Результаты пока не показываю, скажу только - что это самый примитивный алгоритм из рассмотренных. В том плане, что самый медлительный.
2.2. Сортировка выбором
Код в main():
Алгоритм:
2.3. Сортировка вставками
Код в main():
Алгоритм сортировки
2.4. Быстрая сортировка
Код в main():
Алгоритм сортировки:
2.5. Сортировка слиянием
Код в main():
Алгоритм сортировки:
2.6. Встроенная в Go сортировка
Код в main():
Скажу так - это самый шустрый алгоритм сортировки. Что он содержит под собой? Коллеги говорят, что там аналог PD-quicksort, наподобие описанного здесь <<<
Только алгоритм сортировки Go без Block-quicksort-оптимизации.
Теперь поехали разбираться с производительностью алгоритмов.
3. Производительность алгоритмов
Полный код всех шести алгоритмов можно посмотреть на моём GitHub'e. Ниже реализация кода на моём "железе".
Далее повторил go run... и вот что вышло:
Как видим, данные разнятся. Плюс-минус результаты похожи, но тем не менее. Попробуем ещё разок:
Как видим, результат разнится уже не плюс-минус, а в два раза для времени выполнения алгоритма сортировки, встроенного в Go. В чём дело?
А дело в том, что у нас многозадачные и многопоточные операционные системы, что даёт большую погрешность для измерения. В значительной степени этот недостаток помогает компенсировать пакет "testing" с его бенчмарками.
Режим бенчмарк "гоняет" функцию в течение заранее заданного периода времени (если функция быстрая — миллиард раз, а то и больше), и усредняет полученные значения.
У меня нет сейчас большого желания разбираться с бенчмарками. Я сделаю проще - соберу среднее арифметическое из трёх значений и визуализирую информацию для ориентировочного понимания скорости работы алгоритмов:
4. Выводы
У меня нет желания разбираться в том, как эти алгоритмы устроены. По крайней мере на данном этапе обучения.
Самое главное, что нужно усвоить на мой взгляд - что можно сортировать массивы различными способами. И встроенный алгоритм сортировки в Go - очень мощный, примерно вдвое мощнее "Быстрой сортировки" или "сортировки вставками".
Чисто ради любопытства - проделаем анализ для массива длиной 100. Результаты:
Как видим, для маленьких массивов пьедестал для алгоритмов по сортировке изменился. Тоже полезно об этом знать - для больших массивов очень эффективна встроенная в Go сортировка, а для малых может быть выгодна другая сортировка.
И если вдруг появится ситуация, что нам понадобится написать собственный код сортировки - полезно знать, что есть алгоритмы сортировки не только пузырьком и выбором. И выбирать их использование в зависимости от длины массива - а ещё лучше - тестировать, какой алгоритм делает ваш код более эффективным.
--//--//--
PS Если захочешь купить курс от SkillBox, воспользуйся моей реферальной ссылкой. Ты получишь огромную скидку на курс и плюс в карму за помощь каналу.
Кста, курс Go-разработчик, по-видимому ушёл на глубокую доработку в SkillBox, т.к. его уже нет в продаже :) Намана, курс развивается.
Бро, ты уже здесь? 👉 Подпишись на канал для новичков «Войти в IT» в Telegram, будем изучать IT вместе 👨💻👩💻👨💻
