Это статья об основах программирования на Go. На канале я рассказываю об опыте перехода в IT с нуля, структурирую информацию и делюсь мнением.
Хой, джедаи и амазонки!
Продолжаю изучать алгоритмы по книге Грокаем алгоритмы, решать задачи с LeetCode и CodeRun, чтобы наработать навыки, требуемые при поступлении на стажировки Яндекс, Т-банк, ВК, Сбер и т.д.
Поговорим о слайсах в Golang, а точнее - как добавить и удалить элемент из слайса и сколько это требует времени. Познакомимся со связанным списком. Далее посмотрим на два способа сортировки слайса, оба выбором, но с разной реализацией. И порешаем алгоритмические задачи уровня easy. А сперва пробежимся по работе памяти. Go.
1. Хранение данных в памяти
Рассмотрим код:
Создали слайс с типом данных bool. Код выводит в терминал адреса в памяти каждого элемента слайса в шестнадцатеричном формате.
Можно рассмотреть память в виде таблицы. Взглянем на иллюстрацию ниже, по которой видно, как хранятся данные слайса в памяти:
0xc00005c727 - адрес ячейки памяти, в которой хранится какая-то информация (в данном случае везде хранится false).
Когда мы сохраняем в памяти значения, мы запрашиваем у компьютера место в памяти. А компьютер выделяет память и выдаёт адрес для сохранения значения.
Немного доработаем код, чтобы адреса выводились в десятичном более понятном формате:
Как видно, каждый адрес возрастает на единицу. Вспомним, что переменная типа bool занимает 1 байт памяти. Если сделать слайс int-овым, результат будет следующим (int64 занимает 8 байт).
Видим, что каждый результат отличается уже на 8 (байт).
Элементам слайса требуются свободные ячейки памяти. Т.е. если у нас 1 млн элементов типа bool в слайсе, нам нужно 1 млн пустых последовательных ячеек. Если слайс с типом данных int64, то нужно 8 млн последовательных свободных ячеек. Может возникнуть ситуация, когда мы хотим увеличить слайс, а следующая ячейка занята.
Управлением памятью в Go занимается сборщик мусора (garbage collector или GC). В случае, когда понадобилось увеличение размера слайса, GC ищет новый свободный участок памяти и копирует существующие элементы на новый участок: долго.
Для связанных списков не нужны последовательные свободные ячейки, данные в нём хранятся в разных ячейках, в зависимости от того - какая ячейка окажется свободной, см. иллюстрацию ниже:
Когда нам нужно добавить элемент в список, ситуация копирования всех элементов в новую область памяти исключена по-определению: быстро. Разберём теперь связанный список подробнее.
2. Связанный список
В стандартной библиотеке Go нет структуры данных "Связанный список" (далее, список). Причины скорее всего следующие:
- Связанные списки обычно требуют более сложного управления памятью, чем другие структуры данных, и имеют накладные расходы по сравнению со слайсами и картами.
- Go нацелен на простоту и чистоту кода, и стандартная библиотека предоставляет широкий спектр функций и инструментов для работы с слайсами, картами и другими структурами данных, которые охватывают основные потребности разработчиков.
Но если потребность возникнет, то список можно создать. Список, как структура данных, выглядит примерно так:
При использовании списка, как сообщил выше, элементы могут располагаться где-угодно в памяти. И в каждом элементе хранится адрес следующего элемента.
Списки используют только последовательный доступ (массивы/слайсы - произвольный по индексу). Если мы хотим прочитать 1000-й элемент списка, то должны прочитать и 999 элементов до необходимого. Долго.
Но если нам нужно вставить новый элемент например в середину списка, то мы делаем это относительно быстро, т.к. нам просто нужно поменять указатель, а не искать новое место в памяти, куда нужно скопировать элементы списка.
Связанные списки могут быть полезны, когда требуется частая вставка/удаление элементов в середине списка с известной позицией элемента. Сравнение времени выполнения операций со списками и массивами ниже.
Что такое О-большое можно почитать в предыдущей публикации. Кратко, О-большое - это количество операций, необходимых для выполнения алгоритма в худшем случае. Используется для оценки возрастания роста операций (или памяти) от увеличения объёма входных данных.
Теперь пройдёмся по вставке и удалению из слайсов.
3. Вставка и удаление элемента слайса
И вставка, и удаление элемента слайса выполняется через встроенную функцию append:
Фактически, append возвращает новый слайс, который содержит все элементы из исходного слайса и дополнительные элементы, которые мы добавляем. Вот, что об этом говорится в документации к Go:
Удаление и вставка элемента выполняется за О(n) - за линейное время. Напомню, как выглядит шкала О-большого:
В этом разделе я показал, как добавляются и удаляются элементы из слайса. Потому что за два с половиной года изучения Go к своему удивлению обнаружил, что не знал как удалять элемент из слайса.
4. Сортировка выбором
Суть сортировки выбором: проходиться по списку элементов, находить наименьший и ставить его в начало или после уже отсортированных элементов.
Сложность сортировки выбором составляет О(n^2).
4.1. Первая редакция кода сортировки выбором
Рассмотрим код:
В функцию sortSlice подаётся несортированный слайс, возвращается отсортированный по-возрастанию слайс.
Каждый раз при поиске наименьшего элемента, мы проходимся по всем элементам исходного слайса. Когда находим наименьший элемент, добавляем его в новый слайс. При этом удаляем наименьший элемент из исходного слайса.
Можно немного усовершенствовать код.
4.2. Вторая редакция кода сортировки выбором
Рассмотрим код:
Что здесь интересного:
- Мы не создаём новый слайс;
- Мы не возвращаем слайс.
Суть остаётся прежней: мы ищем наименьший элемент и ставим его после уже отсортированных элементов, или на первое место, если это первая итерация сортировки.
Не знаю, канонично ли менять слайс, не возвращая его - но я посчитал что можно слайс и не возвращать, поскольку его длина не изменяется в функции. И мы теоретически экономим 24 байта: напоминаю, при передачи слайса в функцию, передаётся три поля структуры слайс:
- Ссылка на базовый массив;
- Длина слайса;
- Ёмкость слайса - длина базового массива.
Каждый из этих элементов весит по 8 байт.
Насколько это важно для современных компьютеров? Думаю, не важно. Но мало ли, знать это считаю полезным.
Код сортировки выбором на GitHub.
Далее порешаем алгоритмические задачи.
5. Алгоритмические задачи
5.1. Повторение бинарного поиска
Прошла неделя с предыдущего поста об алгоритмах, в котором рассказывал о бинарном поиске. Решил потренироваться и первым делом проверить, помню ли я алгоритм бинарного поиска.
Код написал, задача выполнена.
5.2. LeetCode и прочее
Задачи с литкода и CodeRun уже не публикую - много время уходит на их форматирование, да я уже и не помню - какие публиковал, какие - нет. Их можно посмотреть в моей песочнице на GitHub. Напомню только, что на сайте LeetCode можно решать алгоритмические задачи разной сложности.
На LeetCode, кстати, есть анализ О-большого решённых задач:
Удобно когда пишешь код, проверять что о твоём коде думают алгоритмы сайта.
На сайте CodeRun от Яндекса 27 июня 2024 стартует новый сезон. Можно на него зарегистрироваться, а можно и не регистрируясь порешать в этом тренажёре алгоритмические задачи.
6. Итоги
Ещё одна ступенька на пути к овладению алгоритмами освоена.
Впереди ещё много ступенек на пути становления go-разработчиком.
Попутно подаю отклики на джунские позиции go-разработчика. Будем смотреть, куда дует ветер и что приоритетнее изучать. Пока изучаешь алгоритмы, забывается REST, изучаешь REST, забывается Docker.
Нужно искать работу, чтобы всё это усваивалось и закреплялось практикой. Для этого рекомендуют отправлять 8 осмысленных откликов в неделю, в т.ч. с адекватными сопроводительными письмами. Осмысленный отклик - в плане не во все подряд позиции, где сеньоры или мидлы требуются. А на те позиции, которые подходят процентов на 70 тебе по навыками, зарплатным предложениям, городу и т.д. Подробнее об этом рассказывал здесь <<<
Бро, раз ты уже здесь 👉 Подпишись на канал для новичков «Войти в IT» в Telegram, будем изучать IT вместе 👨💻👩💻👨💻
