О важности алгоритмов и структур данных (АСД) написаны гигабайты текста, и вроде бы аргументы приводятся весомые

О важности алгоритмов и структур данных (АСД) написаны гигабайты текста, и вроде бы аргументы приводятся весомые... Однако все они разбиваются о железобетонное возражение "десятки лет пишу код, и ни разу они не пригодились" — и очень часто это действительно так.

(Готовил этот пост для группы начинающих программистов, но потом решил тут выложить.)

Поэтому, когда призываю к изучению АСД, на самом деле конечно имею в виду следующее:

Вам нужно уметь очень уверено решать самые разные программистские "проблемы" (рабочие задачи, тикеты, issues...). Пресловутый универсальный problem solving.

Но надо ли запоминать именно АСД до такой степени, чтобы "от зубов отскакивало" — чтобы вы умели реализовывать многие популярные алгоритмы фломастером на доске по памяти?

Ну вот такие скиллы на практике действительно не нужны — однако они очень "востребованы" на собеседованиях (много раз говорил, что для успешного прохождения интервью нужны сильно другое множество навыков, нежели непосредственно для работы).

И что ещё более важно, АСД — великолепная практика для начинающих программистов, которым надо развиваться через решение задач растущей сложности, и тут удаётся сразу трёх зайцев поймать:

— задачки достаточно сложные порешать, попрактиковаться в уровне сложности, который постоянно будет на работе,

— изучить тему АСД для будущих собеседований,

— главное, получить хотя бы минимальное представление, как совместить два предыдущих пункта в одно целое.

=

Вот что имею в виду.

Допустим, есть большое множество точек в пространстве.

Выбирается произвольная точка, и тимлид оформляет тикет: "напишите функцию, которая должна быстро формировать список из N наиболее близких точек по отношению к заданной".

Теперь у вас может быть несколько ответов на этот вопрос.

1. Опустить руки, не понимая, а с чего вообще начать и как к этому подступиться, и заплакать.

2. Тупо посчитать расстояния между каждой точкой множества и заданной, затем отсортировать список этих расстояний по возрастанию, и взять первые N точек.

3. Правильнее всего конечно, надо просто понять, что эта проблема на 99.9% уже была решена в computer science, с чем вы уже частично познакомились, изучая базовые АСД, и теперь просто найти её "название" (в данном случае это т.н. задача поиска ближайшего соседа/k ближайших соседей).

4. Далее вы гуглите тему более подробно, изучаете конкретные версии решений (на уровне википедии вполне достаточно), и выбираете наиболее подходящий алгоритм под ваш случай. Cкорее всего вы найдёте десятки разных алгоритмов для решения подобной проблемы.

5. Ищете стандартные библиотеки или какой-то эталонный код (можно и самому закодировать, но лучше не надо), и также, возможно, находите сравнительный анализ библиотек, реализующих алгоритмы поиска ближайших соседей.

6. Не исключено, что из материала с таким анализом вы доберётесь до HNSW (Hierarchical Navigable Small World graphs) — этот алгоритм считается сегодня самым быстрым практическим алгоритмом для множеств из нескольких тысяч точек.

Что и подводит нас к основному моменту этого поста:

Гораздо важнее уметь распознавать проблему на мета-уровне, чем запоминать конкретный алгоритм, который её решает некоторым стандартным образом.

Ещё и потому, что "лучший" алгоритм для решения некоторой популярной проблемы сегодня не обязательно тот же, что и вчера — алгоритмы постоянно развиваются, HNSW был придуман относительно недавно.

Но такой навык мета-распознавания, конечно, будет работать на хорошем базовом фундаменте, когда вы имеете какое-то практическое представление об основных АСД.

=

Вот второй пример.

Хорошее учебное задание — найти подстроку в другой строке (вроде бы совсем просто, однако и миддлы иногда допускают мелкие ошибки).

Однако если строки большие, а вызывается такая функция часто, становится очень актуальным наиболее быстрый алгоритм.

И скорее всего, вы понятия не имеете, как сделать его очень быстрым.

Начинающие обычно просто пишут два вложенных цикла, которые перебирают строки символ за символом.

Возможно, если вы изучали информатику в университете, то узнали, что "самым быстрым" алгоритмом поиска подстроки считается Бойер-Мур.

Штош.

Не бывает самого быстрого алгоритма.

Возможно, если бы вы поисследовали тему подетальнее, то добрались бы до Турбо-Бойер-Мура :) Или до Apostolico-Giancarlo. Оба этих алгоритма имеют превосходные показатели и О-большого и о-маленького по сравнению с классическим алгоритмом Бойера-Мура.

И никто из ваших великолепных друзей-программистов даже не знает, что эти алгоритмы существуют!

Вот почему изучение АСД "на мета-уровне" так важно. Если вы знаете, как эта проблема называется в общем случае, то вы можете найти не только известные алгоритмические решения, но даже гораздо менее известные, но более современные и быстрые алгоритмы, которые еще не вошли в стандартную университетскую программу.

=

В целом, стратегически, тоже важно понимать, что 99,9% проблем даже в Programming in Large достаточно давно были изучены, и были предложены хорошие решения как минимум в академической области, и прежде чем бросаться выдумывать велосипед, всегда лучше поискать что-то похожее готовое. Только конечно надо чётко различать исследовательский подход с тупой копипастой с stackoverflow.

=

И (для лучших из лучших программистов) вполне возможно, что вы глубоко изучите соответствующую тему и придумаете новый превосходный алгоритм, до которого еще никто не додумался.

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

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

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

А научная литература, по определению — это то, что вы не можете знать "на память", и это то, что вы не можете написать фломастером во время собеседования.

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

Источник: vk.com

Комментарии: