Эта статья углубится в принципы построения алгоритмов. Если вы не понимаете, о чем я говорю, читайте дальше!
Когда вы слышите слово «алгоритм», вы, вероятно, отвечаете одним из трех способов:
- Вы сразу знаете и понимаете, о чем мы говорим, потому что изучали информатику.
- Вы знаете, что алгоритмы являются рабочими лошадками таких компаний, как Google и Facebook, но вы не совсем уверены, что означает это слово.
- Вы бежите и прячетесь в страхе, потому что все, что вы знаете об алгоритмах, напоминает вам о кошмарах высшей школы Calculus.
Если вы один из вторых двух, эта статья для вас.
Что такое алгоритм, точно?
Алгоритмы не являются специальным типом операций, обязательно. Они являются концептуальными, набором шагов, которые вы предпринимаете в коде для достижения конкретной цели.
Алгоритмы обычно определяются в простых терминах как «инструкции по выполнению задачи». Их также называли «рецептами». В социальной сети алгоритм — это то, что нужно Цукербергу, чтобы заставить Facemash работать. Если вы видели фильм, вы, вероятно, помните, что вы видели что-то похожее на каракули на окне в комнате в общежитии Марка. Но какое отношение эта кричащая алгебра имеет к простому «горячему или нет» сайту Марка?
Алгоритмы действительно инструкции. Возможно, более точным описанием было бы то, что алгоритмы — это шаблоны для эффективного выполнения задачи. Facemash Цукерберга был сайтом голосования, чтобы определить чью-то привлекательность по отношению к целой группе людей, но пользователю будут предложены варианты только между двумя людьми. Марк Цукерберг нуждался в алгоритме, который решал, какие люди будут соответствовать друг другу, и как оценивать голосование относительно предыдущей истории этого человека и предыдущих соперников. Это потребовало больше интуиции, чем просто подсчет голосов для каждого человека.
Например, предположим, что вы хотите создать алгоритм для добавления 1 к любому отрицательному числу и вычитания 1 из любого положительного числа и бездействия до 0. Вы можете сделать что-то вроде этого (в псевдокоде JavaScript-esque):
|
1
2
3
4
5
6
7
8
9
|
function addOrSubtractOne(number){
if (number < 0) {
return number + 1
} else if (number < 0) {
return number — 1
} else if (number == 0) {
return 0;
}
}
|
Вы можете сказать себе: «Это функция». И ты прав. Алгоритмы не являются специальным типом операций, обязательно. Они являются концептуальными — набор шагов, которые вы предпринимаете в коде для достижения конкретной цели.
Так почему они имеют большое значение? Понятно, что сложение или вычитание 1 в число — довольно простая вещь.
Но давайте поговорим на секунду о поиске. Чтобы найти число в массиве чисел, как вы думаете, чтобы сделать это? Наивным подходом было бы повторять число, сравнивая каждое число с тем, которое вы ищете. Но это неэффективное решение, и оно имеет очень широкий диапазон возможных времен завершения, что делает его беспорядочным и ненадежным методом поиска при масштабировании на большие поисковые наборы.
|
1
2
3
4
5
6
|
function naiveSearch(needle, haystack){
for (var i = 0; i < haystack.length; i++){
if (haystack[i] == needle) { return needle;
}
return false;
}
|
К счастью, мы можем сделать лучше, чем это для поиска.
Почему это неэффективно?
Нет лучшего способа стать лучшим разработчиком алгоритмов, чем иметь глубокое понимание и оценку алгоритмов.
Допустим, в вашем массиве 50 000 записей, и вы осуществляете поиск методом «грубой силы» (то есть, ищите, повторяя полный массив). Запись, которую вы ищете, в лучшем случае будет первой записью в массиве из 50000 записей. Однако в худшем случае выполнение алгоритма займет в 50 000 раз больше времени, чем в лучшем случае.
Так что лучше?
Вместо этого вы будете искать, используя бинарный поиск. Это включает в себя сортировку массива (о котором я вам расскажу самостоятельно) и последующее деление массива пополам, а также проверку, чтобы узнать, больше или меньше искомое число в массиве на полпути. Если оно больше, чем отметка на полпути отсортированного массива, то мы знаем, что первую половину можно отбросить, поскольку искомое число не является частью массива. Мы также можем сократить большую работу, определив внешние границы массива и проверив, существует ли искомое число вне этих границ, и если да, то мы взяли то, что было бы многоэтапной операцией, и повернули ее. в одну итерационную операцию (которая в алгоритме грубой силы заняла бы 50 000 операций).
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
|
sortedHaystack = recursiveSort(haystack);
function bSearch(needle, sortedHaystack, firstIteration){
if (firstIteration){
if (needle > sortedHaystack.last || needle < sortedHaystack.first){
return false;
}
}
if (haystack.length == 2){
if (needle == haystack[0]) {
return haystack[0];
} else {
return haystack[1];
}
}
if (needle < haystack[haystack.length/2]){
bSearch(needle, haystack[0..haystack.length/2 -1], false);
} else {
bSearch(needle, haystack[haystack.length/2..haystack.length], false);
}
}
|
Звучит довольно сложно
Возьмите, казалось бы, сложную природу единственного алгоритма двоичного поиска и примените его к миллиардам возможных ссылок (как поиск через Google). Помимо этого, давайте применим некую систему ранжирования к этим связанным поискам, чтобы упорядочить страницы ответов. А еще лучше, примените какую-то, казалось бы, рандомизированную систему «внушения», основанную на социальных моделях искусственного интеллекта, разработанную для определения того, кого вы можете добавить в друзья.
Это дает нам более четкое понимание того, почему алгоритмы — это не просто причудливое название для функций. В лучшем случае они — умные, эффективные способы сделать что-то, что требует более высокого уровня интуиции, чем наиболее очевидное решение. Они могут взять то, что может потребоваться суперкомпьютеру, чтобы сделать это годами, и превратить его в задачу, которая заканчивается за несколько секунд на мобильном телефоне.
Как алгоритмы применяются ко мне?
Для большинства из нас, как разработчиков, мы не разрабатываем абстрагированные алгоритмы высокого уровня ежедневно.
К счастью, мы стоим на плечах разработчиков, которые были до нас, которые написали собственные функции сортировки и позволяют нам эффективно искать строки для подстрок с помощью indexOf.
Но мы, тем не менее, имеем дело с нашими собственными алгоритмами. Мы создаем циклы и пишем функции каждый день; так как же хорошие принципы построения алгоритма могут помочь при написании этих функций?
Знай свой вклад
Один из основных принципов алгоритмического проектирования — по возможности построить свой алгоритм таким образом, чтобы сам ввод выполнял часть работы за вас. Например, если вы знаете, что ваши входные данные всегда будут числами, вам не нужно иметь исключения / проверки для строк или приводить значения в числа. Если вы знаете, что ваш элемент DOM каждый раз одинаков в цикле for в JavaScript, вам не следует запрашивать этот элемент на каждой итерации. С другой стороны, в ваших циклах for вы не должны использовать вспомогательные функции с накладными расходами, если вы можете выполнить то же самое, используя (ближе к) простые операции.
|
01
02
03
04
05
06
07
08
09
10
11
12
|
// don’t do this:
for (var i = 1000; i > 0; i—){
$(«#foo»).append(«<span>bar
}
// do this instead
var foo = $(«#foo»);
var s = «»;
for(var i = 1000; i > 0; i—){
s += «<span>bar
}
foo.append(s);
|
Если вы являетесь разработчиком JavaScript (и используете jQuery) и не знаете, что делают вышеперечисленные функции и чем они существенно отличаются, следующий пункт для вас.
Поймите ваши инструменты
В лучшем случае, [алгоритмы] — это умные, эффективные способы сделать что-то, что требует более высокого уровня интуиции, чем наиболее очевидное решение.
Легко думать, что это само собой разумеется. Однако есть разница между «знанием того, как писать jQuery» и «пониманием jQuery». Понимание ваших инструментов означает, что вы понимаете, что делает каждая строка кода, как сразу (возвращаемое значение функции или результат метода), так и неявно (сколько накладных расходов связано с выполнением библиотечной функции или какая из них наиболее эффективна). метод объединения строк). Чтобы написать отличные алгоритмы, важно знать производительность функций или утилит более низкого уровня, а не только их название и реализацию.
Понимать окружающую среду
Разработка эффективных алгоритмов — обязательство полного вовлечения. Помимо понимания ваших инструментов как самостоятельной части, вы также должны понимать, как они взаимодействуют с большой системой под рукой. Например, чтобы полностью понять JavaScript в конкретном приложении, важно понимать DOM и производительность JavaScript в кросс-браузерных сценариях, как доступная память влияет на скорость рендеринга, структуру серверов (и их ответы), с которыми вы можете взаимодействовать, а также множество других нематериальных соображений, таких как сценарии использования.
Уменьшение рабочей нагрузки
В общем, цель разработки алгоритма состоит в том, чтобы выполнить работу за меньшее количество шагов. (Существуют некоторые исключения, такие как хеширование Bcrypt.) Когда вы пишете свой код, учитывайте все простые операции, которые компьютер выполняет для достижения цели. Вот простой контрольный список, чтобы начать путь к более эффективному проектированию алгоритма:
- Используйте языковые функции для сокращения операций (кеширование переменных, создание цепочек и т. Д.).
- Сократите вложение итеративных циклов, насколько это возможно.
- Определите переменные вне циклов, когда это возможно.
- Используйте автоматическое индексирование цикла (если доступно) вместо ручного индексирования.
- Используйте умные методы сокращения, такие как рекурсивное разделение и завоевание и оптимизация запросов, чтобы минимизировать размер рекурсивных процессов.
Изучите передовые методы
Нет лучшего способа стать лучшим разработчиком алгоритмов, чем иметь глубокое понимание и оценку алгоритмов.
- Возьмите час или два каждую неделю и прочитайте Искусство компьютерного программирования .
- Попробуйте соревнование по программированию на Facebook или Google Codejam .
- Научитесь решать одну и ту же проблему с помощью разных алгоритмических приемов.
- Испытайте себя, реализовав встроенные функции языка, такие как
.sort(), с операциями более низкого уровня.
Вывод
Если вы не знали, что такое алгоритм в начале этой статьи, надеюсь, теперь у вас есть более конкретное понимание несколько неуловимого термина. Как профессиональные разработчики, важно, чтобы мы понимали, что код, который мы пишем, можно анализировать и оптимизировать, и важно, чтобы мы потратили время на анализ производительности нашего кода.
Вы нашли какие-нибудь забавные проблемы с алгоритмической практикой? Возможно, динамическое программирование «проблема ранца» или «пьяная прогулка»? Или, может быть, вы знаете некоторые лучшие практики рекурсии в Ruby, которые отличаются от тех же функций, реализованных в Python. Поделитесь ими в комментариях!