Как выучить алгоритм
Как выучить алгоритм
Если вы хотите стать лучше в программировании, вам нужно лучше разбираться в алгоритмах. В некотором смысле это утверждение тавтологично. Цитируя пионера компьютерных наук Никлауса Вирта, алгоритмы + структуры данных = программы. Но помимо алгоритмов, которые вы пишете сами, стоит также изучать известные алгоритмы, например, те, которые преподаются на вводных курсах информатики. Некоторые разработчики программного обеспечения возражают против этой идеи. Они говорят, что их язык или фреймворк уже предоставляет все стандартные алгоритмы, или что они могут легко найти их в Интернете. Зачем им изучать, как они реализованы? Конечно, верно, что профессиональные инженеры-программисты не должны заново реализовывать стандартные алгоритмы для того, чтобы использовать их в своем продукте. Но смысл их изучения не в этом. Причина, по которой они являются частью образования по CS, заключается в том, что они содержат полезные идеи. Вот один из примеров: В современных языках программирования вам не нужно беспокоиться о том, как найти конец строки. Язык скрывает этот аспект реализации строк. Но изучая алгоритмы работы со строками в языке C, вы узнаете об идее дозорного значения. Это полезно для понимания того, как узлы листьев представлены в дереве. И теперь у вас есть пара примеров концепции, которую вы можете использовать в других ситуациях, когда вам нужно указать конец участка данных.
Что значит знать алгоритм?
Если вы хотите узнать, знает ли кто-то столицу Франции, вы можете просто спросить его об этом. А если вы хотите узнать, способен ли он возглавить команду из десяти разработчиков, работающих над системой управления контентом? Это может занять несколько бесед в течение дня, и вы все равно не будете знать наверняка. Выяснить, “знает” ли кто-то алгоритм, не так просто, как в примере с Парижем, но проще, чем в примере с руководителем группы разработчиков. Один из вариантов – попросить их объяснить вам алгоритм. Это начало, но не совсем достаточное, если предположить, что цель этого упражнения – найти хорошего программиста. Поэтому до или после того, как они объяснят, как работает алгоритм, вы также должны попросить их реализовать его на реальном языке программирования.
Если вы объясняете и реализуете проблему программирования на техническом собеседовании, цель состоит в том, чтобы интервьюер поверил, что вы знаете, о чем говорите, и был убежден, что ваша программа будет работать. Но если вы работаете дома над улучшением навыков программирования, не всегда есть кто-то рядом, кто может вас оценить. Поэтому альтернативным тестом является следующий: может ли ваша реализация пройти ряд тестов на корректность и производительность. Конечно, именно так работают конкурсы по программированию. Онлайн-судье все равно, знаете ли вы, почему ваша реализация работает, лишь бы тесты прошли. Для компаний, использующих конкурсы при приеме на работу, это может стать проблемой. Что, если их кандидат попросит друга прислать решение? Но если вы используете конкурс для собственного образования, это не проблема. Вы просто должны быть достаточно дисциплинированы, чтобы понять, когда пора посмотреть на чужой код, а когда следует продолжать бороться со своим собственным.
Процесс обучения
Итак, ваша цель – реализовать алгоритм с нуля на реальном языке программирования, не обращаясь ни к каким справочным материалам. Каков наилучший способ достичь того момента, когда вы сможете это сделать? Если бы изучение алгоритмов было похоже на изучение мировых столиц, то непрограммист мог бы просто запомнить реализацию. Затем, подобно средневековому писцу, они могли бы начертать точную копию алгоритма. Очевидно, что это была бы глупая идея. Но что если программист выучит алгоритм, многократно реализуя его. Это немного лучше, поскольку программист имеет некоторое представление о реализации и не просто запоминает символы. На самом деле, это обычный способ обучения для программистов. Если вы знаете, как записать запись в базу данных в системе, над которой вы работаете, то, скорее всего, это не потому, что вы прилагали сознательные усилия, чтобы запомнить этот процесс. Вы просто делали это достаточное количество раз, чтобы больше не искать синтаксис.
Хотя вы можете выучить алгоритм, многократно реализуя его, это не очень эффективный вариант. И, что более важно, он упускает суть: цель изучения стандартных алгоритмов состоит не в том, чтобы уметь повторять их по требованию, а в том, чтобы усвоить заложенные в них алгоритмические идеи. Я собираюсь предложить процесс, который сочетает в себе знание идей, лежащих в основе алгоритма, и знание того, как его реализовать. Шаг реализации гарантирует, что вы знаете практические детали алгоритма, а шаг идеи поможет вам применить полученные знания к своим собственным алгоритмам.
Пример процесса: Quicksort
В книге “Как решить задачу программирования” объясняется процесс решения конкурентных задач программирования. В этом сценарии у вас есть проблема, и вам нужно придумать программу, которая реализует ее решение. В сценарии обучения алгоритмам вы начинаете и с проблемы, и с реализации, и ваша цель – усвоить решение. Вот процесс, как это сделать.
Шаг 1: Выберите алгоритм
Хороший алгоритм для изучения – это тот, который содержит идеи, которые пригодятся вам в дальнейшей работе. Стоит повторить, что вы изучаете этот алгоритм не для того, чтобы дословно воспроизвести его в программном проекте. Для этого почти всегда есть стандартные библиотеки, которые лучше подходят для этой цели. Вместо этого вы ищете идеи.
Для этого примера я собираюсь использовать Quicksort, один из самых известных алгоритмов. У него довольно короткая реализация, но он все же достаточно сложен, чтобы в нем можно было почерпнуть несколько интересных идей.
Шаг 2: Найдите объяснение алгоритма, которое также содержит эталонную реализацию
Поскольку процесс изучения алгоритмов зависит от того, как понять, почему алгоритм работает, и как его реализовать, лучше всего начать с ресурса, который объединяет эти два понятия. К счастью, такой ресурс легко найти для стандартных алгоритмов. Я собираюсь использовать Java-реализацию алгоритма Седжвика, которая имеет соответствующую страницу с объяснениями.
Шаг 3: Прочитайте объяснение алгоритма и запишите идеи реализации.
Вот что
- Выберите первый элемент массива в качестве элемента разделения
- Просканируйте слева элемент, который больше или равен элементу разделения
- Просканируйте справа в поисках элемента, который меньше или равен элементу раздела
- Обменяйтесь двумя найденными элементами, что поместит их в нужные разделы.
- Когда индексы сканирования пересекаются, обменяйте элемент разделения с крайней правой записью левого раздела.
- Шаг 4: Нарисуйте собственные диаграммы алгоритма
- Диаграммы, объясняющие, как работают стандартные алгоритмы, легко найти, и они могут быть полезны для понимания алгоритмов. Существует даже видеообъяснение для QuickSort. Но так же, как полезно перефразировать словесное описание алгоритма, вы лучше усвоите его, если создадите собственные диаграммы, иллюстрирующие алгоритм так, чтобы он имел для вас смысл. Например, ваша диаграмма может выглядеть примерно так, как вы описали алгоритм:
- Шаг 5: Напишите собственную эталонную реализацию алгоритма
- Код эталонной реализации, который вы найдете, может оказаться не совсем тем кодом, который вы хотите изучить. Он может быть написан не на предпочитаемом вами языке, он может обрабатывать специальные случаи, которые вас не интересуют, или он может быть просто написан в стиле, который вам не нравится. Даже если на первый взгляд реализация кажется приемлемой, нелишним будет прочитать ее, чтобы ознакомиться с ней. Если вы вносите какие-либо изменения, убедитесь, что вы не затрагиваете ничего критически важного в алгоритме. Вы можете уменьшить вероятность случайной поломки, протестировав алгоритм до и после внесения изменений и сравнив результаты.
- Для QuickSort.java я внес несколько изменений в код:
Удалите шаг перетасовки. Перемешивание – это способ избежать наихудшей производительности в реальной реализации, но это не основная часть алгоритма.
Убрать сравнения и подсчет обменов, так как это делает код чище. Они также не являются частью алгоритма и включены в пример только из педагогических соображений.
Модифицируйте тестовый клиент, чтобы он работал как UVa OJ: читал тестовый ввод из stdin и записывал результаты в stdout. Это хороший способ проверить, что ваш алгоритм работает: подобно онлайн судье, вы можете сравнить известные хорошие результаты с вашими фактическими результатами.
Измените тип сортируемых данных с double на int. Это не влияет на алгоритм, но целочисленные данные более понятны человеку, чем вещественные числа от 0 до 1, которые используются в оригинальной реализации.
Моя модифицированная версия находится в QuickSort.java на GitHub.
- Шаг 6: Напишите псевдокод для вашей эталонной реализации
- Теперь у вас есть реализация, которую вы свели к основному ядру алгоритма, который вы пытаетесь изучить. Но это все еще настоящая программа, а значит, она содержит детали реализации, предписанные вашим компилятором. Если вы попытаетесь выучить ее сразу, вам придется изучать эти детали реализации одновременно с изучением концептуальных шагов алгоритма. Попытка изучить два разных уровня абстракции одновременно делает процесс обучения менее эффективным. Чтобы избежать этой проблемы, вы можете использовать псевдокод. Поскольку псевдокод не нужно разбирать компилятором, вы можете корректировать его синтаксические правила как угодно. Это позволяет вам выразить алгоритм на постепенно снижающихся уровнях абстракции, пока вы в конечном итоге не достигнете исходного кода, с которого начинали. Изучая каждый уровень абстракции, вы создаете ментальную основу, которая облегчает изучение следующего уровня. Вот как это может работать с QuickSort.java:
- Псевдокод уровня 1
- Это должно быть достаточно легко запомнить.
Псевдокод Уровень 2
Теперь у нас есть стратегия высокого уровня, но мы еще не рассмотрели самую сложную часть – процесс разбиения.
Псевдокод Уровень 3
На этом этапе мы можем прекратить добавлять уровни псевдокода, поскольку у нас почти столько же деталей, сколько и в реальной реализации. Возможно, сейчас самое время вернуться к диаграммам, которые вы нарисовали на шаге 4, и решить, хотите ли вы добавить еще какие-либо детали на основе псевдокода.
Шаг 7: Реализация алгоритма с нуля
Теперь, когда вы изучили алгоритм на нескольких уровнях абстракции, пришло время проверить, сможете ли вы реализовать его самостоятельно. Цель – проверить, понимаете ли вы его на том уровне детализации, который необходим для объяснения компилятору. Если у вас возникли проблемы с реализацией части алгоритма, это может быть признаком того, что вам нужно подтянуть какую-то часть алгоритма или аспект вашего языка программирования. Когда вы сможете реализовать свой алгоритм за разумное время с небольшой помощью компилятора, пора переходить к другому алгоритму. К этому моменту вы будете понимать его лучше, чем большинство программистов.
Изучение проницательности
Изучение известного алгоритма на таком уровне детализации похоже на изучение сонета Шекспира или одного из доказательств Евклида. Вы разбираете результат многолетних исследований и видите, что заставляет его работать. Хотя изучения чужих алгоритмов недостаточно для того, чтобы научиться придумывать свои собственные, оно показывает, как выглядит хороший алгоритм. Для студента, изучающего практические аспекты программирования, этот подход имеет ту же цель, что и стратегия Кэла Ньюпорта по одержимости доказательствами для студентов теоретической информатики: “познать суть”. Хотя язык программирования можно использовать для решения задачи бесконечно многими способами, есть несколько закономерностей, которые постоянно проявляются. Изучив стандартные алгоритмы до такой степени, что вы сможете воспроизвести их с нуля, вы сможете усвоить эти закономерности и использовать их в своей работе.