В этой статье мы узнаем, почему каждый программист должен изучать структуры данных и алгоритмы с помощью примеров.
Эта статья предназначена для тех, кто только начал изучать алгоритмы и задается вопросом, насколько это будет эффективно для повышения их навыков в карьере / программировании. Это также для тех, кто задается вопросом, почему такие крупные компании, как Google, Facebook и Amazon, нанимают программистов, которые исключительно хороши в оптимизации алгоритмов.
Что такое алгоритмы?
Неформально алгоритм - это не что иное, как упоминание шагов для решения проблемы. По сути, это решение.
Например, алгоритм решения проблемы факториалов может выглядеть примерно так:
Задача: найти факториал числа n
Инициализировать факт = 1 Для каждого значения v в диапазоне от 1 до n: умножить факт на v факт содержит факториал n.
Здесь алгоритм написан на английском языке. Если бы он был написан на языке программирования, мы бы вместо этого назвали его кодом . Вот код для нахождения факториала числа в C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Программирование - это все о структурах данных и алгоритмах. Структуры данных используются для хранения данных, а алгоритмы используются для решения проблемы с использованием этих данных.
Структуры данных и алгоритмы (DSA) подробно рассматривают решения стандартных проблем и дают представление о том, насколько эффективно использовать каждую из них. Он также учит вас науке об оценке эффективности алгоритма. Это позволяет вам выбирать лучшее из множества вариантов.
Использование структур данных и алгоритмов для масштабируемости вашего кода
Время дорого.
Предположим, Алиса и Боб пытаются решить простую задачу - найти сумму первых 10 11 натуральных чисел. Пока Боб писал алгоритм, Алиса реализовала его, доказав, что это так же просто, как критика Дональда Трампа.
Алгоритм (Боб)
Инициализируйте сумму = 0 для каждого натурального числа n в диапазоне от 1 до 1011 (включительно): добавьте n к сумме суммы - ваш ответ
Код (от Алисы)
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) (вернуть N * (N + 1) / 2;)
Этот код выполняется всего за одну инструкцию и выполняет задачу независимо от значения. Пусть оно будет больше, чем общее количество атомов во Вселенной. Результат найдется в кратчайшие сроки.
Время, необходимое для решения проблемы, в этом случае составляет 1/y(что составляет 10 наносекунд). Между прочим, реакция синтеза водородной бомбы занимает 40-50 нс, а это означает, что ваша программа будет успешно завершена, даже если кто-то бросит водородную бомбу на ваш компьютер в то же время, когда вы запускаете свой код. :)
Примечание. Компьютерам требуется несколько инструкций (а не 1) для вычисления умножения и деления. Я сказал «1» просто для простоты.
Подробнее о масштабируемости
Масштабируемость - это масштаб плюс способность, что означает качество алгоритма / системы для решения проблемы большего размера.
Рассмотрим проблему создания класса на 50 учеников. Одно из самых простых решений - забронировать комнату, достать доску, несколько мелков, и проблема решена.
Но что, если размер проблемы увеличится? Что, если количество учеников увеличится до 200?
Решение по-прежнему актуально, но требует дополнительных ресурсов. В этом случае вам, вероятно, понадобится гораздо большая комната (возможно, театр), экран для проектора и цифровая ручка.
Что, если количество студентов увеличится до 1000?
Решение не работает или требует много ресурсов, когда размер проблемы увеличивается. Это означает, что ваше решение не масштабировалось.
Что же тогда является масштабируемым решением?
Consider a site like Khanacademy, millions of students can see videos, read answers at the same time and no more resources are required. So, the solution can solve the problems of larger size under resource crunch.
If you see our first solution to find the sum of first N natural numbers, it wasn't scalable. It's because it required linear growth in time with the linear growth in the size of the problem. Such algorithms are also known as linearly scalable algorithms.
Our second solution was very scalable and didn't require the use of any more time to solve a problem of larger size. These are known as constant-time algorithms.
Memory is expensive
Memory is not always available in abundance. While dealing with code/system which requires you to store or produce a lot of data, it is critical for your algorithm to save the usage of memory wherever possible. For example: While storing data about people, you can save memory by storing only their age not the date of birth. You can always calculate it on the fly using their age and current date.
Examples of an Algorithm's Efficiency
Here are some examples of what learning algorithms and data structures enable you to do:
Example 1: Age Group Problem
Problems like finding the people of a certain age group can easily be solved with a little modified version of the binary search algorithm (assuming that the data is sorted).
The naive algorithm which goes through all the persons one by one, and checks if it falls in the given age group is linearly scalable. Whereas, binary search claims itself to be a logarithmically scalable algorithm. This means that if the size of the problem is squared, the time taken to solve it is only doubled.
Suppose, it takes 1 second to find all the people at a certain age for a group of 1000. Then for a group of 1 million people,
- the binary search algorithm will take only 2 seconds to solve the problem
- the naive algorithm might take 1 million seconds, which is around 12 days
The same binary search algorithm is used to find the square root of a number.
Example 2: Rubik's Cube Problem
Imagine you are writing a program to find the solution of a Rubik's cube.
This cute looking puzzle has annoyingly 43,252,003,274,489,856,000 positions, and these are just positions! Imagine the number of paths one can take to reach the wrong positions.
Fortunately, the way to solve this problem can be represented by the graph data structure. There is a graph algorithm known as Dijkstra's algorithm which allows you to solve this problem in linear time. Yes, you heard it right. It means that it allows you to reach the solved position in a minimum number of states.
Example 3: DNA Problem
DNA is a molecule that carries genetic information. They are made up of smaller units which are represented by Roman characters A, C, T, and G.
Imagine yourself working in the field of bioinformatics. You are assigned the work of finding out the occurrence of a particular pattern in a DNA strand.
It is a famous problem in computer science academia. And, the simplest algorithm takes the time proportional to
(number of character in DNA strand) * (number of characters in pattern)
A typical DNA strand has millions of such units. Eh! worry not. KMP algorithm can get this done in time which is proportional to
(number of character in DNA strand) + (number of characters in pattern)
The * operator replaced by + makes a lot of change.
Considering that the pattern was of 100 characters, your algorithm is now 100 times faster. If your pattern was of 1000 characters, the KMP algorithm would be almost 1000 times faster. That is, if you were able to find the occurrence of pattern in 1 second, it will now take you just 1 ms. We can also put this in another way. Instead of matching 1 strand, you can match 1000 strands of similar length at the same time.
And there are infinite such stories…
Final Words
Generally, software development involves learning new technologies on a daily basis. You get to learn most of these technologies while using them in one of your projects. However, it is not the case with algorithms.
Если вы плохо знаете алгоритмы, вы не сможете определить, можете ли вы оптимизировать код, который пишете прямо сейчас. Ожидается, что вы будете знать их заранее и применять их везде, где это возможно и критично.
Мы специально говорили о масштабируемости алгоритмов. Программная система состоит из множества таких алгоритмов. Оптимизация любого из них приводит к лучшей системе.
Однако важно отметить, что это не единственный способ сделать систему масштабируемой. Например, метод, известный как распределенные вычисления, позволяет независимым частям программы запускаться на нескольких машинах вместе, что делает ее еще более масштабируемой.
