Какие алгоритмы должен знать уважающий себя программист?

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

Павел Емельянов, главный архитектор Virtuozzo

Сейчас в … «ненаучном» программировании алгоритмы не так важны. Хорошая алгоритмическая подготовка и смекалка пригодится в специфических областях, например в Big Data или компьютерном моделировании физических, социологических и других процессов реального мира. Даже игровая индустрия уже пережила тот период, когда как воздух требовались новые классные алгоритмы, на «стандартных» в большинстве случаев вполне можно жить.

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

Сергей Зефиров, программист с широким опытом работы, энтузиаст и евангелист языка Haskell

Он должен уметь выводить алгоритмы, а не знать их. Ровно как и математик должен уметь выводить доказательства.

На каких алгоритмах стоит потренироваться в выводе:

• сортировки – от пузырька, до параллельной кеш-независимой сортировки;
• динамическое программирование;
• алгоритмы сжатия данных – кодирование Хаффмана, арифметическое кодирование, сжатие подпоследовательностей;
• символические вычисления – как организовать;
• как сделать статическую структуру динамической – как сделать быструю (O(logN)) вставку в упорядоченный массив.

Материалы по перечисленным темам:

• Наша статья, посвященная пяти основным алгоритмам сортировки.
• Введение в динамическое программирование для начинающих.
• Книга, посвященная методам сжатия данных. Несколько тем, рассмотренных в книге: кодирование источников данных без памяти (канонический алгоритм Хаффмана, арифметическое сжатие, векторное квантование), словарные методы сжатия данных, методы контекстного моделирования и другие.
• Введение в структуры данных для новичков: динамический массив.

Роман Юферев, руководитель направления ИТ-менеджмента и мониторинга в компании VIAcode

Сортировка «пузырьком». Шутка. Алгоритмы – это то, что нам нужно для обработки данных, а сейчас весь мир сталкивается с совершенно новыми задачами при обработке данных и новыми возможностями, поэтому собрание сочинений Кнута на полке уже не является показателем вашей крутости. В то же время, это не значит, что преподаватели в вузе учат вас какой-то «фигне». Повторюсь – изучением алгоритмов и работой над учебными задачами вы тренируете, «разминаете» свои мозги, готовите их к реальной работе, поэтому не брезгуйте материалом, который вам дают в вузе, но и не рассчитывайте особо на его практическое применение в реальной профессиональной жизни.

Где можно «потренировать» мозги:

• Codeforces.
• Сборник задач для практики от СppStudio.
• Задачи Типичного Программиста.
• Russian AI Cup.

Еще больше сайтов с задачками вы можете найти в нашей статье «28 сайтов, на которых можно порешать задачи по программированию».

Василий Кобзарь, преподаватель GeekBrains, специализируется на администрировании Linux

Уважающий себя программист должен понимать абсурдность данного вопроса.

Антон Пискунов, основатель и генеральный директор BeastGaming

Сортировку пузырьком. Если серьезно, то всё ищется в Гугле, а специфичные алгоритмы вы всё равно успеете забыть до того, как они вам понадобятся.

Джозеф Браун, профессор Университета Иннополис

В любом случае, каждая программа оперирует входящими и исходящими данными. И они редко бывают чистыми на входе: необходимо удалить промежутки, или найти недостающие значения, или исправить некорректные. Поэтому необходимо обрабатывать данные и сортировать их, чтобы затем использовать более продвинутые алгоритмы.

Я не могу сказать, какие из алгоритмов более важные. Думаю, предпочтительнее знать несколько алгоритмов из каждого класса. Сортировка пузырьком хорошо работает, когда, к примеру, у вас есть 4 элемента в массиве, которые нужно отсортировать для генетического алгоритма. Но следует помнить, что использование быстрой сортировки не всегда лучший выбор.

Андрей Ситник, веб-разработчик в Evil Martians

Алгоритмы не важны. Вы можете найти их в Гугле за несколько минут. Уважающий себя программист должен уметь правильно ставить строки, понимать задачи клиентов, мудро выбирать между краткосрочными и долгосрочными целями, всегда изучать что-то новое и не боятся сложных задач. Важны умения и личные качества – чистая теория перестала быть важной после создания Гугла.

Александр Чистяков, главный инженер в Git in Sky

Алгоритмы сортировки и поиска, очевидно. Наша жизнь – это сортировка и поиск.

Александр Рожнов, Team Lead в компании Undev

• Сортировка пузырьком;
• разворачивание однонаправленного списка;
• алгоритмы работы с бинарными деревьями;
• алгоритмы работы с хеш-таблицами;
• поиск описания работы интересующего алгоритма за o(n) в Интернете.

Материалы для изучения упомянутых Александром тем:

• Алгоритмы поиска пути в графе.
• Алгоритм двоичного (бинарного) дерева поиска.
• Введение в Хеш-таблицы.
• 8 сервисов для визуализации алгоритмов.
• Введение в анализ сложности алгоритмов.

Всеволод Шмыров, разработчик в команде API Яндекс.Карт

Сортировки, деревья.

Павел Егоров, заместитель руководителя управления разработки СКБ Контур

Что такое хорошая алгоритмическая подготовка?

Да, хорошая алгоритмическая подготовка важна для программиста. И нет, хорошая — это вовсе не заучивание алгоритмов из списка «Самых Важных Алгоритмов, Которые Должен Знать Каждый». На мой взгляд хорошая алгоритмическая подготовка должна стремиться дать программисту следующие три умения.

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

Очевидно, для этого недостаточно просто знать алгоритмы. Нужно уметь “видеть их”, распознавать возможности их применения.

Во-вторых, алгоритмическая подготовка должна прививать привычку анализировать эффективность каждого вашего решения. Не пропускать в критических местах квадратичные или экспоненциальные алгоритмы, и не закладывать в архитектуру программы идеи, которые потом невозможно будет реализовать достаточно эффективно.

В-третьих, алгоритмическая подготовка должна помогать умело пользоваться готовыми инструментами. Базы данных — это сплошные структуры данных и алгоритмы. Причем на концептуальном уровне довольно простые и понятные — деревья поиска, хэштаблицы, SS-Table, …

Например, зная, что индекс в БД — это просто дерево поиска, несложно понять, какие запросы могут быть выполнены быстро, а какие обречены на full-scan.
Зная, как на каких алгоритмах работает полнотекстовый поиск в Lucene, можно предсказать, какие запросы к Elastic будут давать релевантные ответы, а какие — нет, и даже как это можно доработать.

Если подводить итог:

• Кроме самих алгоритмов — учитесь их распознавать в задачах реального мира.
• Прививайте себе привычку анализировать эффективность кода, который вы пишите.
• Изучайте алгоритмы под капотом у инструментов, которыми вы пользуетесь — это пригодится при их эксплуатации.

Несколько статей, которые помогут вам получить хорошую алгоритмическую подготовку:

• Алгоритмы интеллектуального анализа данных.
• Материалы по продвинутым алгоритмам и структурам данных.
• Курс по алгоритмам от Стэнфордского университета.
• Основы компьютерных наук от университета Райса.

Напоминаем, что вы можете задать свой вопрос или присоединиться к числу экспертов.