У цій статті ми дізнаємось, чому кожен програміст повинен вивчати структури даних та алгоритми за допомогою прикладів.
Ця стаття призначена для тих, хто тільки почав вивчати алгоритми та думав, наскільки впливовим буде підвищення їхньої кар’єри / навичок програмування. Це також для тих, хто задається питанням, чому такі великі компанії, як 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 = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Припустимо, що комп’ютер може виконувати інструкції за одну секунду (це може змінюватися залежно від конфігурації машини). Час, необхідний для запуску вище коду, становитьy = 108
Час, необхідний для запуску коду = x / y (більше 16 хвилин)
Чи можна оптимізувати алгоритм, щоб Аліса та Боб не мусили чекати 16 хвилин кожного разу, коли запускають цей код?
Я впевнений, що ви вже вгадали правильний метод. Сума перших N натуральних чисел дається за формулою:
Сума = N * (N + 1) / 2
Перетворення його в код буде виглядати приблизно так:
int сума (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.
Якщо ви погано знаєте алгоритми, ви не зможете визначити, чи зможете ви оптимізувати код, який пишете зараз. Ви повинні знати їх заздалегідь і застосовувати, де це можливо і критично.
Ми спеціально говорили про масштабованість алгоритмів. Програмна система складається з багатьох таких алгоритмів. Оптимізація будь-якого з них призводить до вдосконалення системи.
Однак важливо зазначити, що це не єдиний спосіб зробити систему масштабованою. Наприклад, техніка, відома як розподілені обчислення, дозволяє незалежним частинам програми запускатись на декількох машинах разом, що робить її ще більш масштабованою.
