У овом чланку ћемо научити зашто сваки програмер треба да научи структуре података и алгоритме уз помоћ примера.
Овај чланак је за оне који су тек започели учење алгоритама и питали се колико ће импресивно бити побољшање њихове каријере / вештине програмирања. Такође је за оне који се питају зашто велике компаније попут Гоогле-а, Фацебоок-а и Амазон-а ангажују програмере који изузетно добро оптимизују алгоритме.
Шта су алгоритми?
Неформално, алгоритам није ништа друго до помињање корака за решавање проблема. Они су у суштини решење.
На пример, алгоритам за решавање проблема са чињеницама може изгледати отприлике овако:
Проблем: Пронађите факторијел н
Иницијализовати чињеницу = 1 За сваку вредност в у опсегу 1 до н: Помножите чињеницу са в Чињеница садржи фактор од н
Овде је алгоритам написан на енглеском језику. Да је написан на програмском језику, ми бисмо га уместо тога позвали у код . Ево кода за проналажење факторијела броја у Ц ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Програмирање се односи на структуре података и алгоритме. Структуре података користе се за држање података, док се алгоритми користе за решавање проблема помоћу тих података.
Структуре података и алгоритми (ДСА) детаљно пролазе кроз решења за стандардне проблеме и дају вам увид у то колико је ефикасно користити сваки од њих. Такође вас учи науци процене ефикасности алгоритма. Ово вам омогућава да изаберете најбољи од различитих избора.
Употреба структура података и алгоритама како би ваш код био скалабилан
Време је драгоцено.
Претпоставимо да Алице и Боб покушавају да реше једноставан задатак проналажења збира првих 10 11 природних бројева. Док је Боб писао алгоритам, Алице га је применила доказујући да је једноставан као и критиковање Доналда Трампа.
Алгоритам (аутор Боб)
Иницијализовати збир = 0 за сваки природни број н у опсегу од 1 до 1011 (укључујући): додајте н у збир сума је ваш одговор
Код (од Алице)
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
Време потребно за покретање кода = к / и (дуже од 16 минута)
Да ли је могуће оптимизирати алгоритам тако да Алице и Боб не морају чекати 16 минута сваки пут кад покрену овај код?
Сигуран сам да сте већ погодили праву методу. Збир првих Н природних бројева дат је формулом:
Збир = Н * (Н + 1) / 2
Претварање у код изгледаће отприлике овако:
инт сума (инт Н) (повратак Н * (Н + 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.
Ако алгоритме не познајете добро, нећете моћи да утврдите да ли можете тренутно да оптимизујете код који пишете. Очекује се да их знате унапред и примените где год је то могуће и критично.
Конкретно смо разговарали о скалабилности алгоритама. Софтверски систем се састоји од многих таквих алгоритама. Оптимизација било ког од њих води ка бољем систему.
Међутим, важно је напоменути да ово није једини начин да се систем учини скалабилним. На пример, техника позната као дистрибуирано рачунање омогућава независним деловима програма да се изводе на више машина заједно што га чини још скалабилнијим.
