Зачем изучать структуры данных и алгоритмы
В этой статье вы узнаете, почему каждый программист должен изучать структуры данных и алгоритмы.
Это руководство — для тех, кто только начал изучать алгоритмы и хочет узнать, насколько мощно это прокачает навыки программирования, или для тех, кто не понимает, зачем крупные компании вроде Google, Facebook и Amazon ищут программистов, которые умеют оптимизировать программы.
Что такое алгоритмы
Алгоритм — это последовательность действий для решения задачи. Грубо говоря, алгоритм — это и есть решение задачи.
Задача. Найти n-факториал
Инициализируем переменную fact = 1
Для каждого значения v в диапазоне от 1 до n:
Умножаем fact на v
Ответ: fact
Выше — алгоритм нахождения n-факториала, который записан на русском языке. Если этот же алгоритм записать на каком-нибудь языке программирования, он будет называться кодом.
Например, вот код для решения той же задачи на языке C++.
int factorial(int n) {
int fact = 1;
for (int v = 1; v <= n; v++) {
fact = fact * v;
}
return fact;
}Все программирование завязано на структурах данных и алгоритмах. Первые нужны для хранения данных, а вторые — для решения задач с помощью этих данных.
В серии статей о структурах данных и алгоритмах мы подробно поговорим о решении стандартных задач наиболее эффективным способом и научимся оценивать эту самую эффективность.
Структуры данных и алгоритмы для масштабируемости
Время и память — в приоритете
Представим такую ситуацию. Маша и Андрей пытаются решить простую задачу, им нужно найти сумму первых 1011 натуральных чисел. Пока Андрей прописывал алгоритм, Маша быстренько реализовала его.
Алгоритм Андрея
Инициализируем переменную sum = 0
Для каждого натурального числа n в промежутке от 1 до 1011 включительно:
Добавляем n к sum
Ответ: sum
Код Маши
int findSum() {
int sum = 0;
for (int v = 1; v <= 100000000000; v++) {
sum += v;
}
return sum;
}Андрей и Маша гордятся собой. Они смогли написать программу и почти не потратили на это времени. Вот, что они говорят друг другу:
Маша: Давай запустим код и узнаем сумму.
Андрей: Я запустил его уже пару минут назад, а ответа все нет и нет. Что не так с этим кодом?
Упс! Что-то пошло не так! Андрей снова пытается запустить программу, но ничего не получается. Давайте разберемся, что не так в этом простом коде.
Два самых ценных ресурса компьютерной программы — это время и память.
Время выполнения программы рассчитывается по этой формуле:
Время выполнения кода = количество инструкций * время на выполнение каждой инструкции
Количество инструкций зависит от длины кода, а время, необходимое для выполнения каждой инструкции, зависит от компьютера и компилятора.
В нашем случае общее количество выполненных инструкций (скажем, x) равно
x = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Предположим, что компьютер выполняет одну инструкции за одну секунду (этот показатель может варьироваться в зависимости от конфигурации «машины»). Тогда время, необходимое для выполнения кода Маши, y = 108.
Время, затраченное на выполнение кода = x / y — более 16 минут.
Можно ли оптимизировать алгоритм, чтобы Маше и Андрею не приходилось при каждом запуске ждать по 16 минут?
Скорее всего, вы уже догадались о более правильном подходе. Сумму n-первых натуральных чисел можно найти по этой формуле:
Сумма = N * (N + 1) / 2
Преобразуем эту формулу в код:
int sum(int N) {
return N * (N + 1) / 2;
}Теперь наш код состоит всего из одной инструкции и выполняет задачу одинаково быстро вне зависимости от значения N. Даже если N будет больше, чем общее количество атомов во Вселенной, компьютер посчитает сумму очень быстро.
Время, необходимое для решения задачи, в этом случае составляет 1/y, то есть 10 наносекунд. На секундочку, время реакции синтеза водородной бомбы составляет 40-50 наносекунд. Поэтому даже если кто-то бросит водородную бомбу на ваш компьютер, программы все равно успеет посчитать сумму n-первых чисел.
Примечание. На самом деле, в нашей оптимизированной программе больше одной инструкции. Каждое арифметическое действие — отдельная инструкция.
Подробнее о масштабируемости
Масштабируемость (scalability) — способность программы справляться с увеличением нагрузки.
Допустим, нам нужно создать класс на 50 ученик. Самое простое решение: арендовать комнату, достать доску, несколько мелков или маркеров — проблема решена.
А что если размеры увеличатся? Например, нам нужно будет усадить уже 200 учеников?
Решение все то же, но потребуются дополнительные ресурсы. Скорее всего, понадобится комната гораздо больше (возможно, придется арендовать театр), проектор и цифровая ручка.
А если нужно усадить 1000 учеников?
Прежнее решение в этом случае уже не сработает или, в лучшем случае, потребует очень много ресурсов. Размеры увеличились, и наше решение не справляется с увеличившейся нагрузкой — оно не масштабируемое.
Можно ли придумать масштабируемое решение этой проблемы?
Можно. Существует образовательный интернет-проект «Академия Хана», который позволяет миллиону учеников одновременно просматривать обучающие видео, читать статьи и так далее. Неважно, сколько людей одновременно учатся: 50 или 10000, дополнительных ресурсов не требуется. Такое решение умеет справляться с увеличением нагрузки — оно масштабируемое.
Вернемся к Маше и Андрею. Их программу по поиску суммы первых n-натуральных чисел нельзя масштабировать. Дело в том, что в их коде с линейным увеличением значения n линейно растет время выполнения программы. Такие алгоритмы называют алгоритмами с линейным масштабированием.
Память — дорогой ресурс
В реальных условиях у вас в распоряжении почти никогда не будет много памяти. Поэтому чем меньше памяти ваша программа тратит, тем лучше. Когда вы пишете код или систему, которая хранит большое количество данных, очень важно по возможности экономить расход памяти.
Например, вам нужно хранить данные о людях, в том числе — об их возрасте. Есть два подхода: можно хранить дату рождения, а можно — возраст. С точки зрения экономии памяти выгоднее хранить возраст. Если понадобится выяснить дату рождения, всегда можно быстро ее посчитать: для этого достаточно вычесть возраст из текущего года.
Примеры эффективности алгоритмов
Давайте рассмотрим несколько примеров того, как структуры данных и алгоритмы помогают в реальной жизни.
Задача 1. Возрастная группа
Задачу по поиску людей определенной возрастной группы можно легко решить с помощью немного измененного алгоритма двоичного поиска. Главное, чтобы данные были предварительно отсортированы.
Самый очевидный подход к решению этой задачи (его можно назвать «наивным») выглядит так: перебрать всех людей друг за другом и каждый раз проверять, попадает ли текущий человек в данную возрастную группу. У такого алгоритма линейная масштабируемость: время выполнения линейно увеличивается с ростом исследуемой группы. А у двоичного поиска — логарифмическая масштабируемость. Это значит, что если «размер» задачи возвести в квадрат, время, необходимое для ее решения, удвоится.
Допустим, для группы из 1.000 человек требуется 1 секунда, чтобы найти всех людей определенного возраста. Если в группе 1.000.000 человек,
- алгоритму двоичного поиска понадобится всего 2 секунды;
- «наивному» алгоритм понадобится 1 миллион секунд.
Тот же алгоритм двоичного поиска используется для нахождения квадратного корня числа.
Задача 2. Кубик Рубика
Представьте, что вы пишете программу, которая «решает» кубик Рубика.
У кубика 43 252 003 274 489 856 000 возможных позиций. Представьте себе, сколько путей можно пройти и, в итоге, все равно попасть в неправильную позицию.
К счастью, решить эту задачу можно с помощью такой структурой данных как графы. На них завязан алгоритм Дейкстры, он позволяет решить эту задачу за линейное время (не путать с линейной масштабируемостью).
Задача 3. ДНК
ДНК — это молекула, несущая генетическую информацию. В состав ДНК входят азотистые основания, которые обозначаются латинскими буквами: A (аденин), C (цитозин), T (тимин) и G (гуанин).
Представим, что вы работаете в сфере биоинформатики. Вам поручают выявить, есть ли в цепи ДНК заданный паттерн (шаблон).
Это достаточно известная задача в программировании, особенно в научных кругах. Самое простое решение займет время, пропорциональное количеству символов в цепи ДНК, умноженному на количество символов в шаблоне.
(количество символов в цепи ДНК) * (количество символов в шаблоне)
Обычно ДНК-цепь состоит из миллиона азотистых оснований. Но не волнуйтесь, алгоритм Кнута — Морриса — Пратта (КМП) поможет решить эту задачу за время, пропорциональное сумме количества символов в цепи ДНК и символов в шаблоне.
(количество символов в цепи ДНК) + (количество символов в шаблоне)
Мы заменили оператор * на оператор +. Так мы сократили затрачиваемое время.
Например, если шаблон состоит из 100 символов, решение с помощью алгоритма КМП будет работать в 100 раз быстрее. А если шаблон состоит из 1000 символов — почти в 1000 раз быстрее.
Это значит, что если раньше поиск шаблона в цепочке занимал 1 секунд, при использовании алгоритма КМП поиск будет занимать всего 1 миллисекунду.
Так зачем изучать алгоритмы?
Разработчик каждый день изучает новые технологии, такова специфика IT-сферы. Вы тоже постепенно будете их изучать, используя в своих проектах. Однако с алгоритмами дело обстоит иначе.
Если вы плохо знаете алгоритмы, вы не сможете определить, можно ли оптимизировать свой код. А от разработчика ожидают именно этого. Вы должны знать алгоритмы и применять их везде, где это нужно и возможно.
Мы специально поговорили о масштабируемости алгоритмов. Программа состоит из множества таких алгоритмов. Если оптимизировать хотя бы один из них, это уже приведет к улучшению всей системы.
