Привет!
Я — Колосов Никита, Senior Backend (PHP/Go) Developer с опытом работы более 10 лет. Живу и работаю в Новосибирском Академгородке.
Я работал в различных компаниях, занимался разными вещами в разработке. Прошёл путь от Junior до SRE Tech Lead.
Много работал с высокими нагрузками (около 100 000 RPS в API), в нескольких компаниях выстраивал Observability микросервисов с нуля.
Больше 5 лет участвую в программах менторинга и помогаю всем желающим освоить ключевые навыки для backend-разработчика, либо повысить свой грейд.
Меня можно найти на таких платформах
Solvery -https://solvery.io/mentor/nkolosov
Эйч Навыки — https://h.careers/curators/nikita-kolosov
GetMentor — https://getmentor.dev/mentor/nikita-kolosov-4184
В данном блоге буду рассказывать какие-то интересные случаи из практики, разбирать некоторые задачи по Golang, а также публиковать какие-то материалы, которые мне самому показались интересными.
Я — Колосов Никита, Senior Backend (PHP/Go) Developer с опытом работы более 10 лет. Живу и работаю в Новосибирском Академгородке.
Я работал в различных компаниях, занимался разными вещами в разработке. Прошёл путь от Junior до SRE Tech Lead.
Много работал с высокими нагрузками (около 100 000 RPS в API), в нескольких компаниях выстраивал Observability микросервисов с нуля.
Больше 5 лет участвую в программах менторинга и помогаю всем желающим освоить ключевые навыки для backend-разработчика, либо повысить свой грейд.
Меня можно найти на таких платформах
Solvery -https://solvery.io/mentor/nkolosov
Эйч Навыки — https://h.careers/curators/nikita-kolosov
GetMentor — https://getmentor.dev/mentor/nikita-kolosov-4184
В данном блоге буду рассказывать какие-то интересные случаи из практики, разбирать некоторые задачи по Golang, а также публиковать какие-то материалы, которые мне самому показались интересными.
Academ Coder [Backend/Golang] pinned «Привет! Я — Колосов Никита, Senior Backend (PHP/Go) Developer с опытом работы более 10 лет. Живу и работаю в Новосибирском Академгородке. Я работал в различных компаниях, занимался разными вещами в разработке. Прошёл путь от Junior до SRE Tech Lead. Много…»
Менторство — что это и зачем?
Для начала, хочется вспомнить старый анекдот
В менторство я пришел около 5 лет назад, кажется — во времена ковида. Сидел дома, времени свободного было много и я случайно наткнулся на такие программы. Сначала это была платформа HTML Academy. Схема там следующая: есть курс (даже несколько, по PHP), есть множество учеников и на этом курсе есть домашние задания. И вот задача ментора — проверять эти домашние задания, смотреть на корректность и качество кода и прочее, а также отвечать на вопросы. Длится это около двух месяцев, количество учеников ты выбираешь самостоятельно, по итогам курса HTML Academy оплачивает тебе за каждое проведенное занятие и проверенное домашнее задание.
Около года я подрабатывал на этой платформе, суммарно пройдя 3 или 4 потока. Однако примерно в тоже время я менял работу и менял стек, из PHP/Go переквалифицировался в чистый Go и вести курсы по PHP мне стало не интересно. При этом, экспертизы в Go такого же уровня, как по PHP у меня на тот момент не было.
И в какой-то момент я наткнулся на Solvery. Платформа меня заинтересовала, я там зарегистрировался и стал ждать первых менти. К слову, на удивление, они не заставили себя ждать, поток был постоянный, так что периодически приходится в профиле ставить статус "Не готов брать новых", просто потому что их слишком много.
В целом, все запросы на Solvery делятся на 2 типа
Менти хочет получить консультацию по одному конкретному вопросу (Например, "Как правильно сделать Dashboard в Grafana" или "Спроектировать архитектуру для сервиса N)" или "Хочу оценить свой текущий уровень прежде чем идти по собеседованиям".
Другая история — менти хочет подтянуть свой текущий грейд, либо изучить и получить практику "с нуля"
С такими менти типа #1 как правило проводится одна встреча, на которой мы решаем все эти вопросы и на этом наше общение заканчивается
А вот менти #2 как правильно подразумевают долговременное сотрудничество.
В стандартной схеме — первой встречей мы проводим mock-интервью в формате собеседования (5 минут — рассказ о текущем опыте и целях занятия, 35 минут — говорим про Go, 20 минут — платформа (БД, брокеры, архитектура)
По результатам этой встречи составляется примерный план по занятиям, по тем темам, которые стоит подтянуть.
При этом я никогда не ограничиваю план просто Level Up.
Что я тут имею ввиду?
Допустим, от Junior требуется знать X, от миддла — X + Y, от Senior — X + Y + Z.
Пришел менти Уровня Junior и хочет подтянуться до уровня Middle.
Мы будем разбирать на занятии X + Y + Z, то есть максимум информации, а не только "необходимый минимум" в виде "X + Y"
#Менторство #Менторинг #Менти #ИзЖизни
Для начала, хочется вспомнить старый анекдот
Учитель — учителю:
— Ну и класс мне попался тупой! Объясняю теорему — не понимают.
Объясняю второй раз. Не понимают! В третий раз объясняю. Сам уже понял. А они не понимают…
В менторство я пришел около 5 лет назад, кажется — во времена ковида. Сидел дома, времени свободного было много и я случайно наткнулся на такие программы. Сначала это была платформа HTML Academy. Схема там следующая: есть курс (даже несколько, по PHP), есть множество учеников и на этом курсе есть домашние задания. И вот задача ментора — проверять эти домашние задания, смотреть на корректность и качество кода и прочее, а также отвечать на вопросы. Длится это около двух месяцев, количество учеников ты выбираешь самостоятельно, по итогам курса HTML Academy оплачивает тебе за каждое проведенное занятие и проверенное домашнее задание.
Около года я подрабатывал на этой платформе, суммарно пройдя 3 или 4 потока. Однако примерно в тоже время я менял работу и менял стек, из PHP/Go переквалифицировался в чистый Go и вести курсы по PHP мне стало не интересно. При этом, экспертизы в Go такого же уровня, как по PHP у меня на тот момент не было.
И в какой-то момент я наткнулся на Solvery. Платформа меня заинтересовала, я там зарегистрировался и стал ждать первых менти. К слову, на удивление, они не заставили себя ждать, поток был постоянный, так что периодически приходится в профиле ставить статус "Не готов брать новых", просто потому что их слишком много.
В целом, все запросы на Solvery делятся на 2 типа
Менти хочет получить консультацию по одному конкретному вопросу (Например, "Как правильно сделать Dashboard в Grafana" или "Спроектировать архитектуру для сервиса N)" или "Хочу оценить свой текущий уровень прежде чем идти по собеседованиям".
Другая история — менти хочет подтянуть свой текущий грейд, либо изучить и получить практику "с нуля"
С такими менти типа #1 как правило проводится одна встреча, на которой мы решаем все эти вопросы и на этом наше общение заканчивается
А вот менти #2 как правильно подразумевают долговременное сотрудничество.
В стандартной схеме — первой встречей мы проводим mock-интервью в формате собеседования (5 минут — рассказ о текущем опыте и целях занятия, 35 минут — говорим про Go, 20 минут — платформа (БД, брокеры, архитектура)
По результатам этой встречи составляется примерный план по занятиям, по тем темам, которые стоит подтянуть.
При этом я никогда не ограничиваю план просто Level Up.
Что я тут имею ввиду?
Допустим, от Junior требуется знать X, от миддла — X + Y, от Senior — X + Y + Z.
Пришел менти Уровня Junior и хочет подтянуться до уровня Middle.
Мы будем разбирать на занятии X + Y + Z, то есть максимум информации, а не только "необходимый минимум" в виде "X + Y"
#Менторство #Менторинг #Менти #ИзЖизни
План обучения
В целом, за годы менторства план занятий более-менее пришел к единому виду и мало отличается от менти к менти.
Сначала мы разбираем базовую теорию по языку, закрепляем синтаксис, знакомимся с основными принципами разработки на Go.
Далее, мы постепенно изучаем платформу (БД, брокеры сообщений) и паттерны с ними связанные. Домашняя работа из небольших библиотек с конкретным функционалом превращается в разработку небольшого набора микросервисов, чтобы познакомиться со всеми технологиями, которые мы обсуждали на занятиях.
Как строится обучение?
В общем, обучение строится следующим образом:
Проводим мок-интервью
Я формирую верхнеуровневый план по темам и занятиям, которые нам необходимо пройти с менти
Подробно описываю темы и задание на практику на ближайшее занятие
Менти самостоятельно готовится по заданным темам. При необходимости, может обратиться ко мне за рекомендацией конкретных материалов по темам.
На встрече мы проверяем домашнее задание, я отвечаю на вопросы, которые возникли у менти в процессе подготовки, а также устраиваем такое же mock-интервью, но грубоко и по ограниченному списку тем (на первой встрече - обсуждаем "всё", на номерных встречах — небольшой объём тем
По итогам курса, когда у мы прошли все запланированные темы — проводим повторное мок-интервью для оценки прогресса, а также обнаружения проблем по каким-то темам, которые можем при необходимости повторить или рассмотреть чуть глубже.
Эйч.Навыки
Спустя какое-то время увидел рекламу менторской программы "Навыки", зарегистрировался в том числе и там. В остальном формат абсолютно аналогичен Solvery.
GetMentor
А недавно опубликовал свой профиль ещё и на платформе GetMentor, опять же, с точки зрения всего остального — по цели все платформы абсолютно идентичны. Есть ментор, есть менти, они находят друг друга, а далее уже взаимодействуют в удобном формате. Преимущество платформ Solvery и Эйч.Навыки для меня, как для ментора, в том, что я не беспокоюсь в целом об оплате, не заморачиваюсь с чеками самозанятого (всё формируется в приложении "Мой налог" автоматически), остаётся только раз в месяц оплатить налог.
#Менторство #Менторинг #Менти #ИзЖизни
В целом, за годы менторства план занятий более-менее пришел к единому виду и мало отличается от менти к менти.
Сначала мы разбираем базовую теорию по языку, закрепляем синтаксис, знакомимся с основными принципами разработки на Go.
Далее, мы постепенно изучаем платформу (БД, брокеры сообщений) и паттерны с ними связанные. Домашняя работа из небольших библиотек с конкретным функционалом превращается в разработку небольшого набора микросервисов, чтобы познакомиться со всеми технологиями, которые мы обсуждали на занятиях.
Как строится обучение?
В общем, обучение строится следующим образом:
Проводим мок-интервью
Я формирую верхнеуровневый план по темам и занятиям, которые нам необходимо пройти с менти
Подробно описываю темы и задание на практику на ближайшее занятие
Менти самостоятельно готовится по заданным темам. При необходимости, может обратиться ко мне за рекомендацией конкретных материалов по темам.
На встрече мы проверяем домашнее задание, я отвечаю на вопросы, которые возникли у менти в процессе подготовки, а также устраиваем такое же mock-интервью, но грубоко и по ограниченному списку тем (на первой встрече - обсуждаем "всё", на номерных встречах — небольшой объём тем
По итогам курса, когда у мы прошли все запланированные темы — проводим повторное мок-интервью для оценки прогресса, а также обнаружения проблем по каким-то темам, которые можем при необходимости повторить или рассмотреть чуть глубже.
Эйч.Навыки
Спустя какое-то время увидел рекламу менторской программы "Навыки", зарегистрировался в том числе и там. В остальном формат абсолютно аналогичен Solvery.
GetMentor
А недавно опубликовал свой профиль ещё и на платформе GetMentor, опять же, с точки зрения всего остального — по цели все платформы абсолютно идентичны. Есть ментор, есть менти, они находят друг друга, а далее уже взаимодействуют в удобном формате. Преимущество платформ Solvery и Эйч.Навыки для меня, как для ментора, в том, что я не беспокоюсь в целом об оплате, не заморачиваюсь с чеками самозанятого (всё формируется в приложении "Мой налог" автоматически), остаётся только раз в месяц оплатить налог.
#Менторство #Менторинг #Менти #ИзЖизни
Возьмем типичный план "прокачки" Go-разработчика
- Базовые типы данных. Указатели. Строки, Slice, Map. Внутреннее устройство типов данных. Структуры. Интерфейсы.
- Процессы и потоки ОС. Модель памяти.
- Горутины. Планировщик Go. Go Runtime. GC.
- Работа с многопоточностью (каналы, мультиплексирование, контексты).
- Паттерны многопоточной обработки данных (Worker Pool, Pipeline)
- Обработка ошибок и паник в Go. Метрики и логирование.
- Работа с HTTP / gRPC в Go. Middleware.
- Алгоритмы и структуры данных.
- ACID. Типы индексов PostgreSQL. Репликация и партицирование. Работа с БД в Go.
- Брокеры сообщений. Kafka. Работа с Kafka в Go
- Тестирование приложений в Go. Профилирование. Race Detection.
- System Design. Паттерны микросервисной архитектуры.
Я считаю, что хорошее понимание данного набора тем — это необходимый минимум для того, чтобы считать себя backend-разработчиком на Go и в дальнейшем успешно проходить собеседования.
#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий
- Базовые типы данных. Указатели. Строки, Slice, Map. Внутреннее устройство типов данных. Структуры. Интерфейсы.
- Процессы и потоки ОС. Модель памяти.
- Горутины. Планировщик Go. Go Runtime. GC.
- Работа с многопоточностью (каналы, мультиплексирование, контексты).
- Паттерны многопоточной обработки данных (Worker Pool, Pipeline)
- Обработка ошибок и паник в Go. Метрики и логирование.
- Работа с HTTP / gRPC в Go. Middleware.
- Алгоритмы и структуры данных.
- ACID. Типы индексов PostgreSQL. Репликация и партицирование. Работа с БД в Go.
- Брокеры сообщений. Kafka. Работа с Kafka в Go
- Тестирование приложений в Go. Профилирование. Race Detection.
- System Design. Паттерны микросервисной архитектуры.
Я считаю, что хорошее понимание данного набора тем — это необходимый минимум для того, чтобы считать себя backend-разработчиком на Go и в дальнейшем успешно проходить собеседования.
#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий
Далее посмотрим уже на детальные планы. Точный состав тем может отличаться в ту или иную сторону на занятиях, здесь публикую что-то усредненное.
На первом занятии подробно проходимся по примитивам Go, разбираемся как устроены структуры и интерфейсы, как разботает наследование, композиция и агреггация, какие есть отличия между разными версиями языка, разбираем некоторые тонкости данных тем.
Занятие 1
Пакет builtin. Базовые типы данных. Указатели. Zero-Value. Пустой интерфейс. Пустая структура. Пользовательские структуры. Pointer / Value Receiver.
Операции new / make
Выравнивание структур. Композиция и агрегация.
Упражнение
Данное упражнение не несет особого практического смысла с точки зрения бизнес логики, а скорее направлено просто на отработку базового синтаксиса языка, его основных конструкций и знакомит нас с Git, GoLand (или VS Code).
Реализовать структуру Point (координаты X и Y на плоскости)
Реализовать методы для вычисления расстояния между двумя точками.
Реализовать метод для проверки "попадает ли точка в радиус N относительно другой точки"
Реализовать структуру "Полигон" (набор точек, образующих замкнутый многоугольник)
Реализовать метод для проверки "Находится ли точка внутри полигона"
Написать тесты для этого.
При помощи пакета flag или pflag реализовать работу с точками через консольное приложение, пример
#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий #Занятие1 #Упражнение
На первом занятии подробно проходимся по примитивам Go, разбираемся как устроены структуры и интерфейсы, как разботает наследование, композиция и агреггация, какие есть отличия между разными версиями языка, разбираем некоторые тонкости данных тем.
Занятие 1
Пакет builtin. Базовые типы данных. Указатели. Zero-Value. Пустой интерфейс. Пустая структура. Пользовательские структуры. Pointer / Value Receiver.
Операции new / make
Выравнивание структур. Композиция и агрегация.
Упражнение
Данное упражнение не несет особого практического смысла с точки зрения бизнес логики, а скорее направлено просто на отработку базового синтаксиса языка, его основных конструкций и знакомит нас с Git, GoLand (или VS Code).
Реализовать структуру Point (координаты X и Y на плоскости)
Реализовать методы для вычисления расстояния между двумя точками.
Реализовать метод для проверки "попадает ли точка в радиус N относительно другой точки"
Реализовать структуру "Полигон" (набор точек, образующих замкнутый многоугольник)
Реализовать метод для проверки "Находится ли точка внутри полигона"
Написать тесты для этого.
При помощи пакета flag или pflag реализовать работу с точками через консольное приложение, пример
# ./point --point=2,0 --point=0,0 --distance
> 2
#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий #Занятие1 #Упражнение
На первом занятии мы подробно разобрали примитивные типы данных, на втором - начинаем разбирать составные типы, массивы и слайсы. Разбираемся, в чем их отличия и особенности использования, разбираемся как работает append.
Также, рассматриваем простейшие структуры данных, реализуемые при помощи слайсов, разбираемся, в каких случаях вместо массивов стоит использовать односвязные или двусвязные списки
Занятие 2
Массивы. Устройство массивов. Слайсы. Внутреннее устройство слайсов. Отличия массивов и слайсов. Адресная арифметика.
Команды make / append / copy.
Структуры данных. Стек. Очередь. Односвязный и двусвязный список.
Упражнение
Реализовать структуру данных "Стек"
Реализовать структуру данных "Очередь"
Написать тесты
#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий #Занятие2 #Упражнение
Также, рассматриваем простейшие структуры данных, реализуемые при помощи слайсов, разбираемся, в каких случаях вместо массивов стоит использовать односвязные или двусвязные списки
Занятие 2
Массивы. Устройство массивов. Слайсы. Внутреннее устройство слайсов. Отличия массивов и слайсов. Адресная арифметика.
Команды make / append / copy.
Структуры данных. Стек. Очередь. Односвязный и двусвязный список.
Упражнение
Реализовать структуру данных "Стек"
Реализовать структуру данных "Очередь"
Написать тесты
#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий #Занятие2 #Упражнение
Строки в Go — во многом похожи на слайсы, однако имеют некоторые важные особенности. Иммутабельность, кодирование в UTF-8 и представление в виде байт и рун.
Разбираемся, чем отличается Unicode от UTF-8, как максимально эффективно работать со строками.
Занятие 3
Строки. Внутреннее устройство строк в Go.
Байты. Руны. Кодировка. Unicode. UTF-8.
Пакет strings, unicode/utf8.
Форматирование строк. Преобразование типов данных. Пакеты fmt, strconv.
Упражнение
Необходимо написать Go функцию, осуществляющую примитивную распаковку строки, содержащую повторяющиеся символы/руны, например:
Как видно из примеров, разрешено использование цифр, но не чисел.
В случае, если была передана некорректная строка, функция должна возвращать ошибку. При необходимости можно выделять дополнительные функции / ошибки.
Написать тесты на весь функционал
(*) Дополнительное задание: поддержка экранирования через \:
(обратите внимание на косые кавычки)
Как видно из примера, заэкранировать можно только цифру или слэш.
(*) Дополнительное задание: Написать упаковку строк (обратное преобразование)
#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий #Занятие3 #Упражнение
Разбираемся, чем отличается Unicode от UTF-8, как максимально эффективно работать со строками.
Занятие 3
Строки. Внутреннее устройство строк в Go.
Байты. Руны. Кодировка. Unicode. UTF-8.
Пакет strings, unicode/utf8.
Форматирование строк. Преобразование типов данных. Пакеты fmt, strconv.
Упражнение
Необходимо написать Go функцию, осуществляющую примитивную распаковку строки, содержащую повторяющиеся символы/руны, например:
"a4bc2d5e" => "aaaabccddddde"
"abcd" => "abcd"
"3abc" => "" (некорректная строка)
"45" => "" (некорректная строка)
"aaa10b" => "" (некорректная строка)
"aaa0b" => "aab"
"" => ""
"d\n5abc" => "d\n\n\n\n\nabc"Как видно из примеров, разрешено использование цифр, но не чисел.
В случае, если была передана некорректная строка, функция должна возвращать ошибку. При необходимости можно выделять дополнительные функции / ошибки.
Написать тесты на весь функционал
(*) Дополнительное задание: поддержка экранирования через \:
(обратите внимание на косые кавычки)
`qwe\4\5` => "qwe45"
`qwe\45` => "qwe44444"
`qwe\\5` => `qwe\\\\\`
`qw\ne` => "" (некорректная строка)Как видно из примера, заэкранировать можно только цифру или слэш.
(*) Дополнительное задание: Написать упаковку строк (обратное преобразование)
aaaabccddddde => a4bc2d5e#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий #Занятие3 #Упражнение
Следующий тип данных в Go - это map. Map - это реализация структуры HashMap, которая обеспечивает сложность доступа по ключу в О(1).
Занятие 4
Тип данных map. Внутреннее устройство map. Бакеты.
Hash-функция. Коллизии. Алгоритмы разрешения коллизий.
Устройство памяти. Процесс эвакуации. Взятие указателя на значение map по ключу.
Многопоточная работа с map. Особенности работы с sync.Map
#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий #Занятие4
Занятие 4
Тип данных map. Внутреннее устройство map. Бакеты.
Hash-функция. Коллизии. Алгоритмы разрешения коллизий.
Устройство памяти. Процесс эвакуации. Взятие указателя на значение map по ключу.
Многопоточная работа с map. Особенности работы с sync.Map
#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий #Занятие4
Ранее мы познакомились с основными типами и структурами данных, теперь мы постепенно начинаем применять их на практике.
Одна из наиболее часто используемых структур в production - это LRU-Cache.
Структура представляет из себя кеш ограниченного размера, при этом при добавлении новых элементов, в ситуации, когда кэш заполнен, старые элементы - удаляются. При этом удаляются те элементы, которые давно не были использованы на чтение.
Предполагается, что те элементы, которые мы часто читаем - удалять из кеша не надо, а те элементы, что на чтение не используются - нет смысла в этом кеше хранить.
Упражнение
Реализовать LRU-Cache. При создании кеша указываем его размер при помощи функциональных опций. Если размер не задан - используем размер по-умолчанию.
Кеш должен быть вынесен в отдельный пакет.
Пакет должен иметь тесты на весь функционал.
#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий #Занятие4 #Упражнение
Одна из наиболее часто используемых структур в production - это LRU-Cache.
Структура представляет из себя кеш ограниченного размера, при этом при добавлении новых элементов, в ситуации, когда кэш заполнен, старые элементы - удаляются. При этом удаляются те элементы, которые давно не были использованы на чтение.
Предполагается, что те элементы, которые мы часто читаем - удалять из кеша не надо, а те элементы, что на чтение не используются - нет смысла в этом кеше хранить.
Упражнение
Реализовать LRU-Cache. При создании кеша указываем его размер при помощи функциональных опций. Если размер не задан - используем размер по-умолчанию.
Кеш должен быть вынесен в отдельный пакет.
Пакет должен иметь тесты на весь функционал.
#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий #Занятие4 #Упражнение
Зачастую, приходится работать со структурой под название "Множество" или "Set".
Данная структура представляет из себя набор уникальных элементов.
Упражнение
Реализовать структуру данных Set
Реализовать методы "Пересеченме двух множеств", "Объединение двух множеств", "Вычитание множества"
#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий #Занятие4 #Упражнение
Данная структура представляет из себя набор уникальных элементов.
Упражнение
Реализовать структуру данных Set
Реализовать методы "Пересеченме двух множеств", "Объединение двух множеств", "Вычитание множества"
#Менторство #Менторинг #Менти #GoLang #Go #Backend #ПланЗанятий #Занятие4 #Упражнение
Какие источники стоит изучить при изучении Go и прохождении курсов?
☑️Основы
Основы Go на официальном сайте https://go.dev/learn/
Прохождение Go Tour https://go.dev/tour/
☑️Официальная документация
https://go.dev/doc/
Более подробная документация по внутренностям языка https://go.dev/doc/effective_go
Литература
☑️По языку
📓Язык программирования Go, Алан А.А. Донован, Брайан У.Керниган
📓Golang для профи. Михалис Цукалос.
📓Go: идиомы и паттерны проектирования. Джон Боднер
☑️Алгоритмы и структуры данных
📓Грокаем алгоритмы. Адидтья Бхаргава.
📓Совершенный алгоритм. Тим Рафгарден.
📓Продвинутые алгоритмы и структуры данных. М. Ла. Рокка
☑️ОС и сети
📓Архитектура компьютера. Э. Таненбаум. Т. Остин
📓Современные операционные системы. Э. Таненбаум. Х. Бос.
📓Компьютерные сети. Э. Таненбаум. Д. Уэзеролл.
☑️Архитектура
📓Фундаментальный подход к программной архитектуре: паттерны, свойства, проверенные методы. Ричардс М. , Форд Н.
📓Современный подход к программной архитектуре: сложные компромиссы. Ричардс М. , Форд Н. , Садаладж П., Дехгани Ж.
📓Создание микросервисов. Сэм Ньюмен.
📓Микросервисы. Крис Ричардсон.
📓Высоконагруженные приложения. Программирование. Масштабирование. Поддержка. М. Клеппман.
📓System Design. Подготовка к сложному интервью. Алекс Сюй.
☑️Технологии
📓PostgreSQL 16 изнутри. Егор Рогов.
📓Apache Kafka. Потоковая обработка и анализ данных. Гвен Шапира, Тодд Палино, Раджини Сиварам, Крит Петти.
☑️Observability
📓Site Reliability Engineering. Надежность и безопасность как в Google. Бетси Бейер, Крис Джоунс, Дженнифер Петофф, Нейл Ричард Мёрфи.
📓Site Reliability Workbook: практическое применение. Бетси Бейер, Нейл Ричард Мёрфи, Дэвид Рензин, Кент Кавахара, Стивен Торн
#Go #Backend #Литература #ПолезныеМатериалы
☑️Основы
Основы Go на официальном сайте https://go.dev/learn/
Прохождение Go Tour https://go.dev/tour/
☑️Официальная документация
https://go.dev/doc/
Более подробная документация по внутренностям языка https://go.dev/doc/effective_go
Литература
☑️По языку
📓Язык программирования Go, Алан А.А. Донован, Брайан У.Керниган
📓Golang для профи. Михалис Цукалос.
📓Go: идиомы и паттерны проектирования. Джон Боднер
☑️Алгоритмы и структуры данных
📓Грокаем алгоритмы. Адидтья Бхаргава.
📓Совершенный алгоритм. Тим Рафгарден.
📓Продвинутые алгоритмы и структуры данных. М. Ла. Рокка
☑️ОС и сети
📓Архитектура компьютера. Э. Таненбаум. Т. Остин
📓Современные операционные системы. Э. Таненбаум. Х. Бос.
📓Компьютерные сети. Э. Таненбаум. Д. Уэзеролл.
☑️Архитектура
📓Фундаментальный подход к программной архитектуре: паттерны, свойства, проверенные методы. Ричардс М. , Форд Н.
📓Современный подход к программной архитектуре: сложные компромиссы. Ричардс М. , Форд Н. , Садаладж П., Дехгани Ж.
📓Создание микросервисов. Сэм Ньюмен.
📓Микросервисы. Крис Ричардсон.
📓Высоконагруженные приложения. Программирование. Масштабирование. Поддержка. М. Клеппман.
📓System Design. Подготовка к сложному интервью. Алекс Сюй.
☑️Технологии
📓PostgreSQL 16 изнутри. Егор Рогов.
📓Apache Kafka. Потоковая обработка и анализ данных. Гвен Шапира, Тодд Палино, Раджини Сиварам, Крит Петти.
☑️Observability
📓Site Reliability Engineering. Надежность и безопасность как в Google. Бетси Бейер, Крис Джоунс, Дженнифер Петофф, Нейл Ричард Мёрфи.
📓Site Reliability Workbook: практическое применение. Бетси Бейер, Нейл Ричард Мёрфи, Дэвид Рензин, Кент Кавахара, Стивен Торн
#Go #Backend #Литература #ПолезныеМатериалы
Алгоритмы и структуры данных
В информатике существует множество структур, которые удобны для работы с различными данными в различных сценариях. Некоторые из них нативно представлены в языках программирования, некоторые — требуется реализовать самому, либо же использовать готовые библиотеки.
Тоже самое касается классических алгоритмов. Как правило, разработчику не требуется их реализовывать самостоятельно, всё необходимое уже либо есть в языке, либо есть в сторонних библиотеках, на крайний случай — в Google. Однако, чтобы понять что именно искать в библиотеках и в Google необходимо хотя бы базовую информацию всё же знать.
Сразу отмечу, я не понимаю смысла алгоритмических собеседований при трудоустройстве и считаю, что они бесполезны и даже вредны, так как они ничего не говорят об уровне разработчика при решении реальных бизнес-задач. Если разработчик может быстро написать алгоритм обхода графа в ширину, это лишь значит, что он хорошо знает этот алгоритм, либо прорешал множество подобных задач на leetcode и подобных сервисах. При этом совершенно не факт, что он сможет написать, например, обработчик HTTP-запроса, либо CronJob, которая выгрузит данные из БД, сохранит в файл и отправит его по e-mai за какое-то разумное время, а ведь именно с подобными задачами разработчик и будет сталкиваться после трудоустройства.
В следующих постах, постараемся разобраться, что необходимо знать любому разработчику, какие вообще бывают структуры данных, алгоритмы, для чего они применяются, как оценить сложность того или иного алгоритма.
Я не буду углубляться в тонкости алгоритмов хеширования, криптографии и прочего, различного матана в алгоритмах сжатия, работы с графикой и прочим, поговорим только о самых базовых структурах и алгоритмах, которые необходимы для понимания работы большинства backend-приложений, а также понимания устройства некоторых технологий, с которыми сталкивается разработчик (например, баз данных)
В информатике существует множество структур, которые удобны для работы с различными данными в различных сценариях. Некоторые из них нативно представлены в языках программирования, некоторые — требуется реализовать самому, либо же использовать готовые библиотеки.
Тоже самое касается классических алгоритмов. Как правило, разработчику не требуется их реализовывать самостоятельно, всё необходимое уже либо есть в языке, либо есть в сторонних библиотеках, на крайний случай — в Google. Однако, чтобы понять что именно искать в библиотеках и в Google необходимо хотя бы базовую информацию всё же знать.
Сразу отмечу, я не понимаю смысла алгоритмических собеседований при трудоустройстве и считаю, что они бесполезны и даже вредны, так как они ничего не говорят об уровне разработчика при решении реальных бизнес-задач. Если разработчик может быстро написать алгоритм обхода графа в ширину, это лишь значит, что он хорошо знает этот алгоритм, либо прорешал множество подобных задач на leetcode и подобных сервисах. При этом совершенно не факт, что он сможет написать, например, обработчик HTTP-запроса, либо CronJob, которая выгрузит данные из БД, сохранит в файл и отправит его по e-mai за какое-то разумное время, а ведь именно с подобными задачами разработчик и будет сталкиваться после трудоустройства.
В следующих постах, постараемся разобраться, что необходимо знать любому разработчику, какие вообще бывают структуры данных, алгоритмы, для чего они применяются, как оценить сложность того или иного алгоритма.
Я не буду углубляться в тонкости алгоритмов хеширования, криптографии и прочего, различного матана в алгоритмах сжатия, работы с графикой и прочим, поговорим только о самых базовых структурах и алгоритмах, которые необходимы для понимания работы большинства backend-приложений, а также понимания устройства некоторых технологий, с которыми сталкивается разработчик (например, баз данных)
Для начала, поговорим о структурах данных.
Как правило, их изучение начинается с самых простых структур — массивов (в случае Go — ещё и слайсов), поэтому, первая тема —
Массивы и их внутреннее устройство.
Что такое массив?
Массив это набор элементов одного типа, расположенный в памяти последовательно. Как правило, массив — это указатель на начало нужного куска памяти, и информация о том, какого типа значения хранятся в массиве.
Таким образом, если мы знаем индекс нужного нам элемента, мы можем быстро его найти.
Как? За счет адресной арифметики. Адреса всех переменных в памяти — это просто числа, если к какому-то адресу прибавить (или вычесть) какое-то значение, мы получим адрес какого-то другого элемента в памяти. Как уже сказано выше, массив — это набор элементов одного типа, расположенных в памяти последовательно. А значит, если мы знаем адрес одного элемента массива, то для того, чтобы найти следующий нам всего лишь надо к адресу этого элемента прибавить число, равное размеру одного элемента в памяти.
Рассмотрим на примере:
Допустим, у нас есть массив из пяти элементов типа int64. Пусть будет массив arr = [1 2 3 4 5], начало массива расположено в ячейке памяти с номером 365 (конкретное число нам тут не важно). Каждая ячейка памяти занимает один байт. Каждая переменная занимает 8 байт, а значит и 8 ячеек памяти.
Таким образом, в ячейках 365-372 хранится число 4. В ячейках 373-380 хранится число 3, а заканчивается массив на ячейке 404. В ячейке 405 будут находиться уже какие-то другие данные (или она будет пустая, нам невжано, к нашему массиву она уже не имеет отношения).
Итого, всего у нас занято 8 * 5 = 40 ячеек памяти.
При этом, у нас хранится указатель на начало этого массива (то есть значение 365). Теперь, при обращении к arr[0] мы получаем значение из ячеек 365-372, при обращении к arr[4] получаем значение из ячеек 397-404.
И тут кроется ответ на вопрос, почему нумерация индексов в массивах идет с нуля.
Для получения значения по индексу в массиве, используется следующая формула:
Несложно заметить, что данная формула не зависит от количества элементов в массиве, мы одинаково легко можем найти адрес как первого элемента массива, так и 100500-го элемента в массиве из 1000000000 значений (не вдаваясь в подробности, что тут будет происходить с памятью, конечно)
Таким образом, сложность поиска элемента массива по его индексу — константная, или по-другому — О(1). С О-нотацией разберемся позже.
В следующей части — об особенностях массивов в Go
#Алгоритмы #Массивы #Go
Как правило, их изучение начинается с самых простых структур — массивов (в случае Go — ещё и слайсов), поэтому, первая тема —
Массивы и их внутреннее устройство.
Что такое массив?
Массив это набор элементов одного типа, расположенный в памяти последовательно. Как правило, массив — это указатель на начало нужного куска памяти, и информация о том, какого типа значения хранятся в массиве.
Таким образом, если мы знаем индекс нужного нам элемента, мы можем быстро его найти.
Как? За счет адресной арифметики. Адреса всех переменных в памяти — это просто числа, если к какому-то адресу прибавить (или вычесть) какое-то значение, мы получим адрес какого-то другого элемента в памяти. Как уже сказано выше, массив — это набор элементов одного типа, расположенных в памяти последовательно. А значит, если мы знаем адрес одного элемента массива, то для того, чтобы найти следующий нам всего лишь надо к адресу этого элемента прибавить число, равное размеру одного элемента в памяти.
Рассмотрим на примере:
package main
import (
"fmt"
)
func main() {
a := [5]int{1, 2, 3, 4, 5}
fmt.Println(&a)
fmt.Println(&a[0])
fmt.Println(&a[1])
fmt.Println(&a[2])
fmt.Println(&a[3])
fmt.Println(&a[4])
}
Допустим, у нас есть массив из пяти элементов типа int64. Пусть будет массив arr = [1 2 3 4 5], начало массива расположено в ячейке памяти с номером 365 (конкретное число нам тут не важно). Каждая ячейка памяти занимает один байт. Каждая переменная занимает 8 байт, а значит и 8 ячеек памяти.
Таким образом, в ячейках 365-372 хранится число 4. В ячейках 373-380 хранится число 3, а заканчивается массив на ячейке 404. В ячейке 405 будут находиться уже какие-то другие данные (или она будет пустая, нам невжано, к нашему массиву она уже не имеет отношения).
Итого, всего у нас занято 8 * 5 = 40 ячеек памяти.
При этом, у нас хранится указатель на начало этого массива (то есть значение 365). Теперь, при обращении к arr[0] мы получаем значение из ячеек 365-372, при обращении к arr[4] получаем значение из ячеек 397-404.
И тут кроется ответ на вопрос, почему нумерация индексов в массивах идет с нуля.
Для получения значения по индексу в массиве, используется следующая формула:
АдресЗначения = НачалоМассива + Индекс * РазмерОдногоЭлемента
АдресЗначения = 365 + index * 8, где индекс принимает значения от нуля до четырех.Несложно заметить, что данная формула не зависит от количества элементов в массиве, мы одинаково легко можем найти адрес как первого элемента массива, так и 100500-го элемента в массиве из 1000000000 значений (не вдаваясь в подробности, что тут будет происходить с памятью, конечно)
Таким образом, сложность поиска элемента массива по его индексу — константная, или по-другому — О(1). С О-нотацией разберемся позже.
В следующей части — об особенностях массивов в Go
#Алгоритмы #Массивы #Go
Особенности массивов в Go.
Фактически, массивы в Go не используются. Лично по своему опыту могу сказать, что за 10 лет опыта разработки на Go не использовал массивы ни разу, всегда лучше работать со слайсами.
Основная причина — длина массива не может изменяться. Мы не можем добавить туда новые элементы, количество элементов в слайсе должно быть известно на этапе компиляции, а не в runtime, а работаем мы как правило с неизвестным количеством элементов, поэтому слайсы более удобны в большинстве сценариев.
Исчерпывающая информация по поводу массивов дана в официальной документации (https://go.dev/doc/effective_go#arrays)
- Массивы передаются по значению.
- Присвоение переменной другого массива приведет к полному копированию всех данных. В частности, если вы передаете массив как параметр функции, она получит копию массива, а не указатель на неё
- Размер массива является частью его типа. Тип [10]int и [20]int — это разные типы.
При этом, в некоторых случаях (при достаточно большом размере массива), компилятор может решить, что аллоцировать массив в стеке — невыгодно (придется его постоянно копировать по стеку), поэтому в таких ситуациях массив аллоцируется в куче.
#Алгоритмы #Массивы #Go
Фактически, массивы в Go не используются. Лично по своему опыту могу сказать, что за 10 лет опыта разработки на Go не использовал массивы ни разу, всегда лучше работать со слайсами.
Основная причина — длина массива не может изменяться. Мы не можем добавить туда новые элементы, количество элементов в слайсе должно быть известно на этапе компиляции, а не в runtime, а работаем мы как правило с неизвестным количеством элементов, поэтому слайсы более удобны в большинстве сценариев.
Исчерпывающая информация по поводу массивов дана в официальной документации (https://go.dev/doc/effective_go#arrays)
- Массивы передаются по значению.
- Присвоение переменной другого массива приведет к полному копированию всех данных. В частности, если вы передаете массив как параметр функции, она получит копию массива, а не указатель на неё
- Размер массива является частью его типа. Тип [10]int и [20]int — это разные типы.
При этом, в некоторых случаях (при достаточно большом размере массива), компилятор может решить, что аллоцировать массив в стеке — невыгодно (придется его постоянно копировать по стеку), поэтому в таких ситуациях массив аллоцируется в куче.
#Алгоритмы #Массивы #Go
Go Slices
Слайсы (или "срезы") в Go — это структура данных, в основе которой лежит массив.
Подробное описание, как всегда, в официальной документации (https://go.dev/doc/effective_go#slices) и в исходном коде Go
С точки зрения языка, слайс — это структура, определяемая следующим образом.
Как и в случае массивов, при присвоении переменных и передаче слайса в функцию в качестве аргумента, передается копия слайса. Однако, тут важно понимать, что копирование самой структуры слайса не приводит к копированию данных в массиве.
Рассмотрим вот такой пример
Что происходит "под капотом"?
Под капотом мы имеем что-то подобное
Теперь, копируем переменную a в переменную b
Получаем копию всех значений полей
Обратите внимание, data — это просто переменная указатель, которая по факту содержит число (номер ячейки в памяти, которая указывает на начало массива)
От того, что мы скопировали это число, сам массив (то есть данные по этому адресу) никуда сами по себе не были скопированы. И это важно помнить при работе со слайсами
Теперь, когда мы знаем как массивы и слайсы устроены, поговорим о том, какие алгоритмы существуют и помогают разработчику решать свои задачи.
Слайсы (или "срезы") в Go — это структура данных, в основе которой лежит массив.
Подробное описание, как всегда, в официальной документации (https://go.dev/doc/effective_go#slices) и в исходном коде Go
С точки зрения языка, слайс — это структура, определяемая следующим образом.
type slice struct {
array unsafe.Pointer
len int
cap int
}
Как и в случае массивов, при присвоении переменных и передаче слайса в функцию в качестве аргумента, передается копия слайса. Однако, тут важно понимать, что копирование самой структуры слайса не приводит к копированию данных в массиве.
Рассмотрим вот такой пример
a = []int{1, 2, 3}
b = a
b[0] = 10
fmt.Println(a[0]) // 10
Что происходит "под капотом"?
Под капотом мы имеем что-то подобное
a = {
data = 52394
len = 3
cap = 3
}
Теперь, копируем переменную a в переменную b
Получаем копию всех значений полей
b = {
data = 52394
len = 3
cap = 3
}
Обратите внимание, data — это просто переменная указатель, которая по факту содержит число (номер ячейки в памяти, которая указывает на начало массива)
От того, что мы скопировали это число, сам массив (то есть данные по этому адресу) никуда сами по себе не были скопированы. И это важно помнить при работе со слайсами
Теперь, когда мы знаем как массивы и слайсы устроены, поговорим о том, какие алгоритмы существуют и помогают разработчику решать свои задачи.
Алгоритмы и О-нотация
Мы уже знаем, что сложность поиска элемента в массиве, когда мы знаем его индекс выполняется за константное время, или имеет цикломатическую сложность О(1).
А что с другими операциями?
Если найти мы можем за константное время, то и изменить значение, зная его индекс, тоже можем за константное время.
Добавление нового элемента в массив потребует выделения нового участка памяти, а значит нам придется скопировать данные из старой памяти в новую, зависимость тут линейная (на каждый элемент массива нам потребуется одно и то же количество операция, и соответственно, чем больше массив — тем больше операций будет сделано), то есть О(N)
Да, поиск по индексу — достаточно эффективен, однако в основном мы сталкиваемся с поиском по значению (то есть как раз решаем обратную задачу, находим индекс элемента, зная его значение)
Самые базовые алгоритмы, с которыми приходится работать — это поиск и сортировка. Здесь мы не будем углубляться в алгоритмы хэширования, криптографии и прочее, будем говорить о тех вещах, которые нужны разработчику "на старте".
Что нужно знать о таких алгоритмах?
Во-первых, необходимо начать с О-нотации.
Что это такое? Если не углубляться в математическое определение, то это оценка сложности алгоритма (а значит и его эффективность).
По факту, при помощи О-нотации мы можем описать количество операций, которые выполнит ваш программный код для реализации данного алгоритма. При этом операции могут быть разные. Для каких-то алгоритмов — это сравнение, для каких-то — копирование и так далее.
Сложность бывает:
- Константная, или О(1). Это означает, что сложность алгоритма не зависит от количества обрабатываемых элементов. То есть если мы точно знаем количество производимых операций, даже если операция не одна, не две и даже не 10, но какое-то конечное число, которое не зависит ни от чего, мы говорим, что сложность алгоритма О(1)
- Линейная, или О(N). Сложность алгоритма зависит от количества элементов, над которыми проводится операция. Например, простой поиск по неоотсортированному массиву
- Логарифмическая, или О(log N), к таким алгоритмам относится, например, двоичный поиск
- Линейно-логарифмическая O( N * log N) (в основном, это касается алгоритмов сортировки)
- Квадратичная — O(n^2), слабо эффективные алгоритмы типа "сортировки пузырьком)
Более детально можно посмотреть, например, на Wikipedia
https://ru.wikipedia.org/wiki/%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0
Далее — рассмотрим основные алгоритмы сортировки массивов
#Алгоритмы #Массивы
Мы уже знаем, что сложность поиска элемента в массиве, когда мы знаем его индекс выполняется за константное время, или имеет цикломатическую сложность О(1).
А что с другими операциями?
Если найти мы можем за константное время, то и изменить значение, зная его индекс, тоже можем за константное время.
Добавление нового элемента в массив потребует выделения нового участка памяти, а значит нам придется скопировать данные из старой памяти в новую, зависимость тут линейная (на каждый элемент массива нам потребуется одно и то же количество операция, и соответственно, чем больше массив — тем больше операций будет сделано), то есть О(N)
Да, поиск по индексу — достаточно эффективен, однако в основном мы сталкиваемся с поиском по значению (то есть как раз решаем обратную задачу, находим индекс элемента, зная его значение)
Самые базовые алгоритмы, с которыми приходится работать — это поиск и сортировка. Здесь мы не будем углубляться в алгоритмы хэширования, криптографии и прочее, будем говорить о тех вещах, которые нужны разработчику "на старте".
Что нужно знать о таких алгоритмах?
Во-первых, необходимо начать с О-нотации.
Что это такое? Если не углубляться в математическое определение, то это оценка сложности алгоритма (а значит и его эффективность).
По факту, при помощи О-нотации мы можем описать количество операций, которые выполнит ваш программный код для реализации данного алгоритма. При этом операции могут быть разные. Для каких-то алгоритмов — это сравнение, для каких-то — копирование и так далее.
Сложность бывает:
- Константная, или О(1). Это означает, что сложность алгоритма не зависит от количества обрабатываемых элементов. То есть если мы точно знаем количество производимых операций, даже если операция не одна, не две и даже не 10, но какое-то конечное число, которое не зависит ни от чего, мы говорим, что сложность алгоритма О(1)
- Линейная, или О(N). Сложность алгоритма зависит от количества элементов, над которыми проводится операция. Например, простой поиск по неоотсортированному массиву
- Логарифмическая, или О(log N), к таким алгоритмам относится, например, двоичный поиск
- Линейно-логарифмическая O( N * log N) (в основном, это касается алгоритмов сортировки)
- Квадратичная — O(n^2), слабо эффективные алгоритмы типа "сортировки пузырьком)
Более детально можно посмотреть, например, на Wikipedia
https://ru.wikipedia.org/wiki/%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0
Далее — рассмотрим основные алгоритмы сортировки массивов
#Алгоритмы #Массивы
С этого алгоритма обычно знакомят с понятием сортировки массивов.
Имплементация на Go может выглядеть, например, так
func BubbleSort(array[] int)[]int {
for i:=0; i< len(array)-1; i++ {
for j:=0; j < len(array)-i-1; j++ {
if (array[j] > array[j+1]) {
array[j], array[j+1] = array[j+1], array[j]
}
}
}
return array
}
Как мы видим, для каждого элемента массива, делается еще один проход по массиву, который "выталкивает" значения больше вверх, как пузырек в кипящей кастрюле.
Сложность - O(n^2)
Затраты памяти - О(1), т.к. не требует дополнительных затрат памяти
Подробнее можно ознакомиться на Википедии
https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D1%83%D0%B7%D1%8B%D1%80%D1%8C%D0%BA%D0%BE%D0%BC
Один из наиболее популярных алгоритмов сортировки, по факту является улучшенной версией "сортировки пузырьком"
Идея в том, что мы можем разделить массив пополам, взять число посередине массива, после чего передвинуть "влево" все элементы меньше него, а "вправо" - больше. При этом, применяя тот же алгоритм рекурсивно к левой и правой половине
Реализация на Go может выглядеть следующим образом
func quickSort(arr []int, low, high int) []int {
if low < high {
var p int
arr, p = partition(arr, low, high)
arr = quickSort(arr, low, p-1)
arr = quickSort(arr, p+1, high)
}
return arr
}
func partition(arr []int, low, high int) ([]int, int) {
pivot := arr[high]
i := low
for j := low; j < high; j++ {
if arr[j] < pivot {
arr[i], arr[j] = arr[j], arr[i]
i++
}
}
arr[i], arr[high] = arr[high], arr[i]
return arr, i
}
Средняя сложность O(n log n)
Память O(n)
Недостатки
При большом количестве элементов рекурсия может вызвать переполнение стека
Кроме того, при неудачных входных данных сложность возрастает до O(n^2)
Более подробно на Википедии
https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
#Алгоритмы #Массивы #Сортировка
Please open Telegram to view this post
VIEW IN TELEGRAM
Wikipedia
Сортировка пузырьком
простой алгоритм сортировки