În acest articol, vom afla de ce fiecare programator ar trebui să învețe structuri de date și algoritmi cu ajutorul unor exemple.
Acest articol este destinat celor care tocmai au început să învețe algoritmi și s-au întrebat cât de impactant va fi să-și sporească abilitățile de carieră / programare. Este, de asemenea, pentru cei care se întreabă de ce companii mari precum Google, Facebook și Amazon angajează programatori care sunt extrem de buni în optimizarea algoritmilor.
Ce sunt algoritmii?
În mod informal, un algoritm nu este altceva decât o mențiune a pașilor pentru rezolvarea unei probleme. Ele sunt în esență o soluție.
De exemplu, un algoritm pentru a rezolva problema factorialelor ar putea arăta cam așa:
Problemă: Găsiți factorialul lui n
Inițializați faptul = 1 Pentru fiecare valoare v din intervalul 1 la n: Înmulțiți faptul cu v fapt conține factorialul lui n
Aici, algoritmul este scris în engleză. Dacă ar fi scris într-un limbaj de programare, l-am numi în schimb cod . Iată un cod pentru găsirea factorialului unui număr în C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Programarea se referă la structuri de date și algoritmi. Structurile de date sunt utilizate pentru a păstra date, în timp ce algoritmii sunt utilizați pentru a rezolva problema folosind acele date.
Structurile și algoritmii de date (DSA) trec prin soluții la problemele standard în detaliu și vă oferă o perspectivă asupra eficienței utilizării fiecăruia dintre ele. De asemenea, vă învață știința evaluării eficienței unui algoritm. Acest lucru vă permite să alegeți cea mai bună dintre diferitele opțiuni.
Utilizarea structurilor de date și a algoritmilor pentru a vă face codul scalabil
Timpul este prețios.
Să presupunem că Alice și Bob încearcă să rezolve o problemă simplă de a găsi suma primelor 10 11 numere naturale. În timp ce Bob scria algoritmul, Alice l-a implementat dovedind că este la fel de simplu ca și criticarea lui Donald Trump.
Algoritm (de Bob)
Inițializați suma = 0 pentru fiecare număr natural n din intervalul 1-1011 (inclusiv): adăugați n la suma sumă este răspunsul dvs.
Cod (de Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice și Bob se simt euforici despre ei înșiși că ar putea construi ceva al lor în aproape un timp. Să ne strecurăm în spațiul lor de lucru și să le ascultăm conversația.
Alice: Să rulăm acest cod și să aflăm suma. Bob: Am rulat acest cod cu câteva minute în urmă, dar încă nu arată rezultatul. Ce e în neregulă cu ea?
Ups! Ceva a mers prost! Un computer este cea mai deterministă mașină. Revenirea și încercarea de a rula din nou nu va ajuta. Deci, să analizăm ce nu este în regulă cu acest cod simplu.
Două dintre cele mai valoroase resurse pentru un program de calculator sunt timpul și memoria .
Timpul necesar computerului pentru a rula codul este:
Timpul de rulare a codului = numărul de instrucțiuni * timpul de executare a fiecărei instrucțiuni
Numărul de instrucțiuni depinde de codul pe care l-ați utilizat, iar timpul necesar pentru executarea fiecărui cod depinde de mașină și compilator.
În acest caz, numărul total de instrucțiuni executate (să zicem x) sunt , care estex = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Să presupunem că un computer poate executa instrucțiuni într-o secundă (poate varia în funcție de configurația mașinii). Timpul necesar pentru a rula deasupra codului estey = 108
Timpul necesar pentru executarea codului = x / y (mai mare de 16 minute)
Este posibil să optimizăm algoritmul, astfel încât Alice și Bob să nu fie nevoiți să aștepte 16 minute de fiecare dată când rulează acest cod?
Sunt sigur că ați ghicit deja metoda potrivită. Suma primelor N numere naturale este dată de formula:
Suma = N * (N + 1) / 2
Conversia acestuia în cod va arăta cam așa:
int sum (int N) (returnează N * (N + 1) / 2;)
Acest cod se execută într-o singură instrucțiune și realizează sarcina indiferent de valoare. Să fie mai mare decât numărul total de atomi din univers. Va găsi rezultatul în cel mai scurt timp.
Timpul necesar pentru a rezolva problema, în acest caz, este 1/y(care este de 10 nanosecunde). Apropo, reacția de fuziune a unei bombe de hidrogen durează 40-50 ns, ceea ce înseamnă că programul dvs. se va finaliza cu succes chiar dacă cineva aruncă o bombă de hidrogen pe computerul dvs. în același timp când ați rulat codul. :)
Notă: computerele iau câteva instrucțiuni (nu 1) pentru a calcula înmulțirea și împărțirea. Am spus 1 doar pentru simplitate.
Mai multe despre scalabilitate
Scalabilitatea este scala plus capacitatea, ceea ce înseamnă calitatea unui algoritm / sistem pentru a rezolva problema dimensiunilor mai mari.
Luați în considerare problema înființării unei clase de 50 de elevi. Una dintre cele mai simple soluții este să rezervați o cameră, să obțineți o tablă, câteva crete, iar problema este rezolvată.
Dar dacă dimensiunea problemei crește? Ce se întâmplă dacă numărul studenților ar crește la 200?
Soluția este încă valabilă, dar are nevoie de mai multe resurse. În acest caz, probabil veți avea nevoie de o cameră mult mai mare (probabil un teatru), un ecran de proiector și un pix digital.
Ce se întâmplă dacă numărul studenților ar crește la 1000?
Soluția eșuează sau folosește o mulțime de resurse atunci când dimensiunea problemei crește. Aceasta înseamnă că soluția dvs. nu a fost scalabilă.
Ce este atunci o soluție scalabilă?
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.
Dacă nu cunoașteți bine algoritmii, nu veți putea identifica dacă puteți optimiza codul pe care îl scrieți chiar acum. Vă așteptați să le cunoașteți din timp și să le aplicați ori de câte ori este posibil și critic.
Am vorbit în mod specific despre scalabilitatea algoritmilor. Un sistem software constă din mulți astfel de algoritmi. Optimizarea oricăruia dintre ele duce la un sistem mai bun.
Cu toate acestea, este important să rețineți că aceasta nu este singura modalitate de a face un sistem scalabil. De exemplu, o tehnică cunoscută sub numele de calcul distribuit permite părților independente ale unui program să ruleze împreună pe mai multe mașini, făcându-l și mai scalabil.
