Коротко про алгоритмы и структуры данных

d40b5bbd5b4d4c6c8447845ffb6187e1.jpg

Привет, Хабр! Меня зовут Ричард, я работаю в команде kPHP в VK, занимаюсь разработкой kPHP, плагинов для IDE, а также другого инструментария, делая жизнь разработчиков проще. В своей работе мне приходится иметь дело с PSI деревьями, AST, самописными структурами данных и их модификациями, и даже QuickSelect (и более сложные алгоритмы) мне доводилось реализовывать. Хочу немного поговорить про один из краеугольных, пожалуй, камней в IT, а именно про «алгоритмы и структуры данных» — тема не теряет актуальности со времен появления Хабра. Заранее оговорюсь, мой пост на 90% состоит из личного опыта во время обучения, работы и преподавания.

Сразу дам короткий TL; DR и ответы на вопросы:

1. Нужно ли программисту знать «структуры данных»? Да, нужно.

2. Нужно ли ему знать алгоритмы? Не обязательно. Однако нужно их понимать, уметь в них разобраться.

Из второго пункта можно вывести и другой вопрос «Нужно ли программисту знать математику?». На самом деле ответ будет примерно таким же. Представим, что вам придется погрузиться в алгоритмы не только на собеседовании. Например, появится задача существенно модифицировать библиотеку или фреймворк под нужды компании, взяв сам алгоритм только за основу. Имея за плечами даже базовое (со времен школы или студенчества) воспоминание о различных областях математики, вы справитесь с задачей гораздо быстрее.

Но я отвлекся, вернемся к алгоритмам. На Хабре есть много статей, где авторы и комментаторы с переменным успехом пытаются прийти к единому мнению. В недавнем посте автор, которому алгоритмы понадобились всего 3 раза (sic!) за 20+ лет карьеры в IT, делает лаконичный вывод: «Программист должен уметь массив обойти какой, дерево, может быть связанный список». И я с ним полностью согласен. Хотя, на мой взгляд, алгоритмы Дейкстры или Беллмана‑Форда, тоже неплохо было бы понимать, но я коснусь более простых задач, которые стоит знать на любом, даже junior уровне.

Пример первый: https://leetcode.com/problems/sort‑list. Для его решения не требуется знание высшей математики. С его помощью можно проверить, умеет ли человек работать со связным списком и указателями (если язык их поддерживает), имеет ли общее представление о сортировках.

Второй пример чуть специфичнее: https://leetcode.com/problems/find-if-path-exists-in-graph. Тут уже нужно обосновать, почему обходим в ширину или в глубину. Тем не менее, это всё ещё базовые манипуляции со структурой данных, то есть никаких алгоритмов Джонсона.

Эти задачи проверяют умение программиста работать со структурами данных, понимать их устройство и обоснованность того или иного подхода. Более сложные алгоритмы должны быть «заточены» под проект и то, с чем реально можно столкнуться в работе.

Вместо итога могу сказать, что учеба в университете и куча математики позволили мне быстрее понимать и анализировать проблемы, иметь потенциальный набор решений, а также знать, куда копать. QuickSelect, о котором упоминал выше, мне все же пришлось еще раз перечитать, но я уже понимал, где искать.

Если вас заинтересовали алгоритмы, но университетский курс уже забылся,  либо его не было вовсе, то так получилось, что я стал соавтором асинхронного онлайн‑курса «Алгоритмы и структуры данных» от VK Education. Когда мы с моим коллегой Ильей Почуевым и методистами из команды образования его разрабатывали, нам хотелось собрать все те вопросы и пробелы, с которыми встречаются в университете, и попытаться помочь решить их в понятном и современном формате. Мы создали курс, который ориентирован на практику и ведет слушателя к пониманию базовых концепций и развитию навыков решения типовых задач.

Курс «Алгоритмы и структуры данных» состоит из 4 модулей:  

К каждой из тем нужно будет выполнить от одного до трех домашних заданий, чтобы проверить себя на понимание пройденного материала. Также предусмотрены Q&A‑сессии, где более подробно разбираются задачи, подходы к их решению и другие вопросы. Курс бесплатный и не требует прохождения вступительных испытаний. Подать заявку можно в любой момент. Ну и плюс асинхронных курсов в том, что их можно совмещать с работой или учебой в университете. Слушатели сами выбирают темп обучения.

Дальше можно углубить полученные знания, чтобы, например, ответить для себя на вопросы «Почему оно работает именно так? Какую доказательную базу имеет под собой решение?». Но это уже в ваших руках — в рамках обучения в вузе или на наших образовательных курсах с более углубленной программой.

Закончить хочу поговоркой: «Хороша ложка к обеду». Правда лучше брать подходящую ложку и, как минимум, знать, где ее можно отыскать.

© Habrahabr.ru