Sellest artiklist saame teada, miks peaks iga programmeerija näidete abil õppima andmestruktuure ja algoritme.
See artikkel on mõeldud neile, kes on just alustanud algoritmide õppimist ja mõtlesid, kui mõjus on nende karjääri / programmeerimisoskuste suurendamine. See on mõeldud ka neile, kes imestavad, miks suured ettevõtted, nagu Google, Facebook ja Amazon, palgavad programmeerijaid, kes on algoritmide optimeerimisel erakordselt head.
Mis on algoritmid?
Mitteametlikult pole algoritm muud kui probleemi lahendamise sammude mainimine. Need on sisuliselt lahendus.
Näiteks faktoriaalide probleemi lahendamise algoritm võib välja näha umbes selline:
Probleem: leidke n faktorial
Initsialiseeri fakt = 1 Iga väärtuse v puhul vahemikus 1 kuni n: korrutage fakt v-ga faktori n väärtus
Siin on algoritm kirjutatud inglise keeles. Kui see oleks kirjutatud programmeerimiskeeles, kutsuksime selle hoopis koodiks . Siin on kood arvu faktori leidmiseks C ++ -s.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Programmeerimine on seotud andmestruktuuride ja algoritmidega. Andmestruktuure kasutatakse andmete hoidmiseks, samas kui algoritme kasutatakse probleemi lahendamiseks nende andmete abil.
Andmestruktuurid ja algoritmid (DSA) vaatavad üksikasjalikult läbi standardprobleemide lahendused ja annavad ülevaate, kui tõhus on nende kõigi kasutamine. Samuti õpetab see teile algoritmi efektiivsuse hindamise teadust. See võimaldab teil valida erinevatest valikutest parima.
Andmekonstruktsioonide ja algoritmide kasutamine koodi skaleeritavaks muutmiseks
Aeg on kallis.
Oletame, et Alice ja Bob üritavad lahendada lihtsa ülesande leida esimese 10 11 loodusarvu summa . Samal ajal kui Bob algoritmi kirjutas, viis Alice selle kasutusele, tõestades, et see on sama lihtne kui Donald Trumpi kritiseerimine.
Algoritm (autor Bob)
Initsialiseerige summa = 0 iga loodusliku arvu n jaoks vahemikus 1 kuni 1011 (kaasa arvatud): lisage summa summale summa
Kood (autor Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice ja Bob tunnevad end eufoorias, et nad saaksid peaaegu oma aja jooksul midagi oma ehitada. Hiilime nende tööruumi ja kuulame nende vestlust.
Alice: Käivitame selle koodi ja saame teada summa. Bob: Jooksin seda koodi mõni minut tagasi, kuid see ei näita ikkagi väljundit. Mis sel viga on?
Oops! Midagi läks valesti! Arvuti on kõige deterministlikum masin. Tagasi minemine ja uuesti proovimine ei aita. Nii et analüüsime, mis sellel lihtsal koodil viga on.
Kaks arvutiprogrammi kõige väärtuslikumat ressurssi on aeg ja mälu .
Aeg, mis arvuti kulutab koodi käivitamiseks, on:
Koodi käivitamise aeg = käskude arv * aeg iga käsu täitmiseks
Juhiste arv sõltub teie kasutatavast koodist ning iga koodi täitmiseks kuluv aeg sõltub teie masinast ja kompilaatorist.
Sellisel juhul on täidetud käskude koguarv (oletame, et x) , mis onx = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Oletame, et arvuti suudab käske täita ühe sekundiga (see võib varieeruda sõltuvalt masina konfiguratsioonist). Koodi ületamiseks kuluv aeg ony = 108
Koodi käivitamiseks kuluv aeg = x / y (üle 16 min)
Kas on võimalik algoritmi optimeerida nii, et Alice ja Bob ei peaks iga kord selle koodi käivitamisel 16 minutit ootama?
Olen kindel, et aimasite juba õiget meetodit. Esimese N loodusliku arvu summa antakse valemiga:
Summa = N * (N + 1) / 2
Selle koodiks teisendamine näeb välja umbes selline:
int summa (int N) (tagastus N * (N + 1) / 2;)
See kood täidetakse ainult ühe käsu abil ja see saab ülesande tehtud olenemata väärtusest. Olgu see suurem kui aatomite koguarv universumis. See leiab tulemuse hetkega.
Antud juhul kulub probleemi lahendamiseks aega 1/y(see on 10 nanosekundit). Muide, vesinikupommi termotuumasünteesi reaktsioon võtab 40-50 ns, mis tähendab, et teie programm saab edukalt lõpule viidud isegi siis, kui keegi viskab teie arvutisse vesinikupommi samal ajal, kui teie kood käitus. :)
Märkus . Korrutamise ja jagamise arvutamiseks peavad arvutid kasutama mõnda juhist (mitte 1). Olen öelnud 1 lihtsalt lihtsuse huvides.
Lisateavet mastaapsuse kohta
Skaalautuvus on skaala pluss võime, mis tähendab algoritmi / süsteemi kvaliteeti suurema suurusega probleemi lahendamiseks.
Mõelge 50 õpilasega klassiruumi sisseseadmise probleemile. Üks lihtsamaid lahendusi on ruumi broneerimine, tahvli, mõne kriidi hankimine ja probleem on lahendatud.
Aga mis siis, kui probleemi suurus suureneb? Mis oleks, kui õpilaste arv kasvaks 200-ni?
Lahendus on endiselt olemas, kuid see vajab rohkem ressursse. Sellisel juhul vajate tõenäoliselt palju suuremat ruumi (tõenäoliselt teatrit), projektoriekraani ja digitaalset pastakat.
Mis oleks, kui õpilaste arv kasvaks 1000-ni?
Lahendus ebaõnnestub või kasutab probleemi suuruse suurenemisel palju ressursse. See tähendab, et teie lahendus ei olnud skaleeritav.
Mis on siis skaleeritav lahendus?
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.
Kui te ei tunne algoritme hästi, ei saa te tuvastada, kas saate praegu kirjutatavat koodi optimeerida. Eeldatakse, et tunnete neid ette ja rakendate neid kõikjal, kus see on võimalik ja kriitiline.
Rääkisime konkreetselt algoritmide mastaapsusest. Tarkvarasüsteem koosneb paljudest sellistest algoritmidest. Mõne neist optimeerimine viib parema süsteemini.
Siiski on oluline märkida, et see pole ainus viis süsteemi skaleeritavaks muuta. Näiteks võimaldab hajutatud arvutusena tuntud tehnika programmi iseseisvatel osadel koos mitme masinaga käivitada, muutes selle veelgi skaleeritavaks.
