Что учить из классической Computer Science?
Last updated
Last updated
В предыдущей главе мы описали, как вы можете самостоятельно составить список технологий для изучения. Но в описаниях вакансий кроме названий конкретных библиотек и инструментов часто всплывает и "понимание алгоритмов и структур данных". Что это и что из этого нужно знать?
Тем, кто входит в ИТ по классическому пути через ВУЗ в этом плане проще. Уж что-что, а фундаментальную подготовку в области Computer Science, включающую курс по алгоритмам, университеты дают. Остальным придется изучать данную тему самостоятельно.
При написании программ часто возникают типовые задачи. Есть массив элементов, как отсортировать их по порядку? Есть большой набор объектов, в котором надо часто искать нужный, как делать это быстрее? Есть точки на карте, как найти кратчайшие пути между ними?
За десятки лет было изобретено множество готовых решений - тех самых алгоритмов и структур для хранения данных, позволяющих эффективно выполнять такие задачи.
На собеседованиях на junior разработчика от вас, скорее всего, захотят понимания следующих трех тем:
Выбирая алгоритм или структуру данных для решения своей задачи вы должны понимать, насколько эффективно они будут работать. Для оценки времени работы и потребляемых ресурсов разработана целая теория.
По этой теории написано много книг и серьезных научных статей, в которых может быть непросто разобраться новичку. Но для первых собеседований вам хватит простого бытового понимания, неплохо описанного в статьях https://tproger.ru/articles/computational-complexity-explained/ или https://bimlibik.github.io/posts/complexity-of-algorithms/
Вкратце, оценка сложности показывает порядок количества операций или потребляемой памяти в зависимости от размера входных данных.
Например, чтобы найти нужное число в списке неотсортированных чисел, вам в среднем придется просмотреть примерно половину всех чисел. Иногда вы будете его находить раньше, иногда позже, но в среднем время работы будет прямо пропорционально размеру массива. Такая сложность называется линейной и записывается как О(n), где n - размер входных данных, а что такое функция О - рассказывают в курсе матанализа, и для базового понимания это не сильно важно.
Линейная сложность означает, что в среднем, если дать на вход в два раза больший массив данных, алгоритм будет работать тоже в два раза дольше. В пять раз больше данных - в пять раз дольше. И так далее.
А вот если вы хотите найти нужное значение в отсортированном массиве, вы можете использовать алгоритм двоичного поиска. Деля каждый раз массив напополам, вы сможете найти нужное значение в массиве из 100 элементов в среднем всего за 5 операций (а не за 50), а в массиве из 1000000 элементов - всего за 20 вместо 500000. Такая трудоемкость обозначается как O(log N), так как количество операций является логарифмом (обычно двоичным, но в целом основание не так важно) от числа элементов. Получается, что при увеличении размера массива в 10 000 раз алгоритм двоичного поиска замедлился всего в 4 раза, в то время как линейный поиск замедлился в те же самые 10 000 раз.
На этом примере наглядно видно, что на больших наборах данных (а в реальной разработке легко встречаются задачи по поиску и сортировке в многомиллионных списках и базах) хороший алгоритм может работать на порядки быстрее плохих. И в этом и заключается ценность хороших алгоритмов (и вас, как специалиста, если вы в них разбираетесь). Когда ваш алгоритм работает сутки, замена его на имеющий лучшую сложность может сократить время работы до часов, а то и минут. Что может привести как в экономии времени (можно быстрее обрабатывать данные и выдавать клиенту) так и денег (можно не тратиться на новые сервера, а эффективнее использовать существующие).
Типичные сложности алгоритмов таковы:
O(1) - константная сложность. Время работы алгоритма не зависит от размера входных данных. Например, получение элемента массива по индексу: независимо от размера массива мы вычисляем сдвиг в памяти и сразу получаем нужную ячейку по ее адресу.
O(log N) - логарифмическая сложность. Это очень хороший вариант для большинства алгоритмов, но к сожалению не всегда достижимый. Примеры - приведенная выше дихотомия, поиск элементов в деревьях.
O (N) - линейная сложность. Поиск элемента в списке, где нам нужно последовательно просмотреть все элементы. Удаление элемента из массива, так как после этого надо сдвинуть все элементы правее него на одну ячейку влево.
O (N * log N) - похуже линейной, получше квадратичной. Эту сложность имеют популярные алгоритмы сортировки массивов.
O (N^2) - квадратичная сложность. Уже достаточно плохой вариант, ведь если для 1000 элементов алгоритм будет работать секунду, до для 10000 (в 10 раз больше) сложность увеличится как квадрат - не в десять, а в сто раз, то есть уже полторы минуты. А для 100 000 ( в 100 раз больше) время работы увеличится в 10 000 раз и составит уже почти три часа. Такую сложность имеют наивные алгоритмы сортировки, навроде "попарно сравнивать элементы массива и менять местами те, которые идут в неправильном порядке".
Все, что выше, уже редко имеет практическое применение, так как время работы слишком быстро растет с ростом размера входных данных.
Любая программа - это манипулирование с какими-либо данными. И сразу встает вопрос: как именно эти данные хранить?
Для многих типовых задач придуманы различные структуры данных, ускоряющие доступ к ним. Используя известные оценки из теории сложности (рассмотренной выше), можно выбрать структуру, оптимально подходящую к вашей задаче.
В стандартных библиотеках языков программирования как правило есть следующие типовые структуры данных: массивы, списки, стеки, очереди, деревья, словари, хеш-таблицы.
Более подробных статей с описаниями - тысячи в интернете, например https://habr.com/ru/post/422259/ https://robotdreams.cc/blog/58-structure-your-data-please https://netology.ru/blog/10-data-structures https://nuancesprog.ru/p/12140/
От вас, как от разработчика, потребуется понимание, когда и какие нужно использовать. Например, в Java есть два класса списка: ArrayList и LinkedList. И у вас есть необходимость хранить большой объем объектов, элементы из которого приходится часто добавлять и удалять.
Вы берете привычный ArrayList, но замечаете, что в какой-то момент приложение начинает тормозить, а добавление каждого следующего элемента занимает все больше и больше времени. А почему так? А потому, что ArrayList реализован поверх массива (что ясно из названия), а для массива добавление элемента имеет трудоемкость O(N) (в реалности чуть сложнее, но это не так важно для базового понимания). Так как массив имеет фиксированный размер, и чтобы добавить в него новый элемент нужно перевыделить массив большего размера и скопировать в него содержимое старого массива.
Заменив реализацию на LinkedList, использующий связный список и имеющий трудоемкость добавления O(1), вы сможете значительно повысить производительность.
Таким образом, использование правильных структур данных позволяет избежать ошибок и неоптимальной скорости работы и потребления ресурсов.
Существует ряд типовых алгоритмов, в которых тоже желательно ориентироваться. Не обязательно уметь их реализовывать, вряд ли вам придется самим хоть раз писать какой-нибудь QuickSort, так как его готовые реализации есть во всех популярных ЯП. Но вы должны хотя бы знать его название, что он есть и что имеет такую трудоемкость, чтобы выбирать правильные алгоритмы в правильных местах.
Основные алгоритмы, которые чаще всего спрашивают на собеседованиях, можно разделить на основные группы:
Сортировки. Отсортировать массив пользователей по набранным очкам и вывести таблицу лидеров, или найти наиболее популярный товар среди ассортимента магазина - все это задачи на сортировку массивов объектов.
Алгоритмы, связанные со структурами данных. Например, как именно работает поиск в бинарном дереве.
Алгоритмы на графах, востребованы в первую очередь там, где нужно искать какие-то пути. Ваш навигатор в смартфоне прокладывает вам маршрут по карте именно с помощью алгоритмов этой категории.
Остальное будет зависеть от специфики предстоящей работы. Могут и по алгоритмам сжатия погонять, и по каким-нибудь алгоритмам оптимизации, что уже на стыке с вычислительной математикой.
Алгоритмы и структуры данных - фундамент Computer Science, и существуют фундаментальные классические книги, входящие в состав ВУЗовских курсов.
Мы в свое время учились по следующим книгам:
Кормен "Алгоритмы: построение и анализ". Классическая книга по теории сложности и типичным структурам данных. https://ru.wikipedia.org/wiki/Алгоритмы:_построение_и_анализ
Четырехтомник Кнута "Искусство программирования" https://ru.wikipedia.org/wiki/Искусство_программирования
Седжвик "Фундаментальные алгоритмы на С++"
Лафоре "Структуры данных и алгоритмы на Java"
В этих книгах вы найдете как необходимую теорию по анализу сложности алгоритмов, так и конкретные реализации на разных языках.
Кроме алгоритмов и структур данных на собеседованиях могут спросить, а в жизни может пригодиться:
Знание паттернов проектирования. Если алгоритмы это про то, какой код написать чтобы все эффективно работало, то паттерны - про то, как именно его написать, чтобы это было читаемо и поддерживаемо. Это типовые решения архитектурных задач. Обзор разных паттернов с их описаниями дан, например, на сайте https://refactoring.guru/ru/design-patterns/ Названия самых популярных паттернов можно точно так же поискать в описаниях вакансий и вопросов к собеседованиям: Listener, Singleton, Factory и ряд других употребляются повсеместно. Большинство паттернов представляют собой по сути просто умные названия для довольно очевидных концепций (например Singleton - когда у нас в приложении какой-то объект может существовать в одном и только одном экземпляре), плюс типовые реализации их на разных ЯП. Вполне можно использовать паттерны в своей работе, даже не зная об этом, большинство из них интуитивно понятны и до них вполне можно додуматься самостоятельно. Изучение их общепринятых названий, однако, будет все равно полезным: для собеседований и чтобы говорить с коллегами на одном языке.
Понимание многопоточной работы. Как только ваш код начинает выполняться параллельно в нескольких потоках сразу, вы открываете для себя чудный новый мир странных трудноотлавливаемых ошибок: Race Condition, Deadlock и прочих увлекательных развлечений. Классической иллюстрацией таких проблем в распределенных системах, понятной даже неспециалисту, и с которой начинается любой курс по многопоточности, является задача об обедающих философах. Для борьбы с возникающими проблемами приходится использовать специальные алгоритмы и структуры данных. Существует много статей, посвященных как общему описанию таких алгоритмов, так и использованию их реализаций в различных ЯП. Например . Есть и книги на эту тему, например классикой для Java является "".