Šiame straipsnyje sužinosime, kodėl kiekvienas programuotojas, naudodamasis pavyzdžiais, turėtų išmokti duomenų struktūras ir algoritmus.
Šis straipsnis skirtas tiems, kurie ką tik pradėjo mokytis algoritmų ir domėjosi, kaip bus naudinga sustiprinti savo karjeros / programavimo įgūdžius. Tai taip pat tiems, kurie stebisi, kodėl tokios didelės kompanijos kaip „Google“, „Facebook“ ir „Amazon“ samdo programuotojus, kurie puikiai moka optimizuoti algoritmus.
Kas yra algoritmai?
Neoficialiai, algoritmas yra ne kas kita kaip problemos sprendimo žingsnių paminėjimas. Iš esmės jie yra sprendimas.
Pvz., Algoritmas, leidžiantis išspręsti faktorių problemą, gali atrodyti maždaug taip:
Problema: raskite n faktorialą
Inicijuoti faktą = 1 Kiekvienai reikšmei v diapazone nuo 1 iki n: Padauginkite faktą iš v fakto, kuriame yra n faktorialas
Čia algoritmas parašytas anglų kalba. Jei tai būtų parašyta programavimo kalba, mes ją pavadintume kodu . Čia yra kodas faktoriaus skaičiui rasti C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Programavimas yra susijęs su duomenų struktūromis ir algoritmais. Duomenų struktūros naudojamos duomenims laikyti, o algoritmai naudojami problemai išspręsti naudojant tuos duomenis.
Duomenų struktūros ir algoritmai (DSA) išsamiai išnagrinėja standartinių problemų sprendimus ir suteikia jums supratimą, kaip efektyviai naudoti kiekvieną iš jų. Taip pat mokoma algoritmo efektyvumo vertinimo mokslo. Tai leidžia jums pasirinkti geriausią iš įvairių pasirinkimų.
Duomenų struktūrų ir algoritmų naudojimas, kad jūsų kodas būtų keičiamas
Laikas yra brangus.
Tarkime, Alisa ir Bobas bando išspręsti paprastą problemą - surasti pirmųjų 10 11 natūralių skaičių sumą. Kol Bobas rašė algoritmą, Alisa jį įgyvendino įrodydama, kad tai yra taip paprasta, kaip kritikuoti Donaldą Trumpą.
Algoritmas (Bobas)
Inicializuokite sumą = 0 kiekvienam natūraliam skaičiui n diapazone nuo 1 iki 1011 (imtinai): pridėkite n prie sumos sumos - jūsų atsakymas
Kodas (sukūrė Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alisa ir Bobas jaučiasi euforiškai nusiteikę, kad beveik per trumpą laiką galėtų sukurti ką nors savo. Pažvelkime į jų darbo sritį ir paklausykime jų pokalbio.
Alisa: Paleiskime šį kodą ir sužinokime sumą. Bobas: Aš paleidau šį kodą keletą minučių atgal, bet jis vis dar nerodo išvesties. Kas čia blogo?
Oi! Kažkas negerai! Kompiuteris yra labiausiai lemianti mašina. Grįžimas ir bandymas jį paleisti dar kartą nepadės. Taigi išanalizuokime, kas yra blogai su šiuo paprastu kodu.
Du vertingiausi kompiuterinės programos ištekliai yra laikas ir atmintis .
Laikas, kurį kompiuteris užima kodui paleisti, yra:
Laikas vykdyti kodą = instrukcijų skaičius * laikas kiekvienai instrukcijai įvykdyti
Instrukcijų skaičius priklauso nuo jūsų naudojamo kodo, o kiekvieno kodo vykdymo laikas priklauso nuo jūsų mašinos ir kompiliatoriaus.
Šiuo atveju yra visas įvykdytų nurodymų (sakykime x) skaičius , kuris yrax = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Tarkime, kad kompiuteris gali vykdyti instrukcijas per vieną sekundę (tai gali skirtis priklausomai nuo mašinos konfigūracijos). Laikas, per kurį reikia paleisti virš kodo, yray = 108
Laikas, per kurį reikia paleisti kodą = x / y (daugiau nei 16 minučių)
Ar įmanoma optimizuoti algoritmą, kad Alisai ir Bobui nereikėtų laukti 16 minučių kiekvieną kartą paleidus šį kodą?
Esu tikras, kad jūs jau atspėjote teisingą metodą. Pirmųjų N natūraliųjų skaičių suma apskaičiuojama pagal formulę:
Suma = N * (N + 1) / 2
Konvertuojant jį į kodą atrodys maždaug taip:
int suma (int N) (grąža N * (N + 1) / 2;)
Šis kodas vykdomas tik viena instrukcija ir gauna užduotį, kad ir kokia būtų jos vertė. Tegul jis bus didesnis už bendrą visatos atomų skaičių. Tai greitai suras rezultatą.
Šiuo atveju problemai išspręsti reikia laiko 1/y(tai yra 10 nanosekundžių). Beje, vandenilio bombos sintezės reakcija trunka 40–50 ns, o tai reiškia, kad jūsų programa bus sėkmingai užbaigta, net jei kažkas tuo metu, kai paleisite kodą, į jūsų kompiuterį išmes vandenilio bombą. :)
Pastaba: Norėdami apskaičiuoti dauginimą ir padalijimą, kompiuteriai naudojasi keliomis instrukcijomis (ne 1). Aš sakiau 1 vien dėl paprastumo.
Daugiau apie mastelį
Mastelis yra mastelis plius sugebėjimas, o tai reiškia algoritmo / sistemos kokybę spręsti didesnio dydžio problemą.
Apsvarstykite 50 studentų klasės įrengimo problemą. Vienas paprasčiausių sprendimų - užsisakyti kambarį, gauti lentą, keletą kreidų ir problema išspręsta.
Bet kas, jei problemos dydis padidės? O jei studentų skaičius padidėtų iki 200?
Sprendimas vis dar galioja, tačiau jam reikia daugiau išteklių. Tokiu atveju jums tikriausiai reikės kur kas didesnio kambario (tikriausiai teatro), projektoriaus ekrano ir skaitmeninio rašiklio.
O jei studentų skaičius padidėtų iki 1000?
Padidėjus problemos dydžiui, sprendimas nepavyksta arba naudoja daug išteklių. Tai reiškia, kad jūsų sprendimas nebuvo keičiamas.
Koks tada yra keičiamo dydžio sprendimas?
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.
Jei gerai nežinote algoritmų, negalėsite nustatyti, ar galite optimizuoti dabar rašomą kodą. Tikimasi, kad žinosite juos iš anksto ir taikysite visur, kur įmanoma ir kritiška.
Mes konkrečiai kalbėjome apie algoritmų mastelį. Programinės įrangos sistemą sudaro daugybė tokių algoritmų. Bet kurio iš jų optimizavimas sukuria geresnę sistemą.
Tačiau svarbu pažymėti, kad tai nėra vienintelis būdas padaryti sistemą keičiamą. Pavyzdžiui, technika, vadinama paskirstytuoju skaičiavimu, leidžia nepriklausomoms programos dalims veikti kartu su keliomis mašinomis, todėl ji tampa dar labiau keičiama.
