V tem članku bomo izvedeli, zakaj se mora vsak programer s pomočjo primerov naučiti podatkovnih struktur in algoritmov.
Ta članek je namenjen tistim, ki so se šele začeli učiti algoritme in se spraševali, kako učinkovit bo njihov razvoj kariere / programiranja. Namenjen je tudi tistim, ki se sprašujejo, zakaj velika podjetja, kot so Google, Facebook in Amazon, najemajo programerje, ki izjemno dobro optimizirajo algoritme.
Kaj so algoritmi?
Neformalno algoritem ni nič drugega kot omemba korakov za rešitev problema. V bistvu so rešitev.
Na primer, algoritem za reševanje problema s faktorji lahko izgleda nekako takole:
Težava: Poiščite faktorije n
Inicializiraj dejstvo = 1 Za vsako vrednost v v območju od 1 do n: Pomnoži dejstvo z v Dejstvo vsebuje faktorijel n
Tu je algoritem napisan v angleščini. Če bi bila napisana v programskem jeziku, bi jo namesto tega poklicali v kodo . Tu je koda za iskanje faktorja števila v jeziku C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Programiranje se nanaša na podatkovne strukture in algoritme. Podatkovne strukture se uporabljajo za hrambo podatkov, algoritmi pa za reševanje problema z uporabo teh podatkov.
Podatkovne strukture in algoritmi (DSA) podrobno preberejo rešitve standardnih problemov in vam dajo vpogled v to, kako učinkovita je uporaba vsakega od njih. Prav tako vas nauči znanosti o ocenjevanju učinkovitosti algoritma. To vam omogoča, da izberete najboljšo izbiro.
Uporaba podatkovnih struktur in algoritmov za povečanje vaše kode
Čas je dragocen.
Recimo, da Alice in Bob poskušata rešiti preprost problem iskanja vsote prvih 10 11 naravnih števil. Medtem ko je Bob pisal algoritem, ga je Alice implementirala in dokazala, da je tako preprost kot kritiziranje Donalda Trumpa.
Algoritem (avtor Bob)
Inicializirajte vsoto = 0 za vsako naravno število n v obsegu od 1 do 1011 (vključno): dodajte n vsoti vsote je vaš odgovor
Koda (Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice in Bob se počutita evforično, da bi lahko skoraj v kratkem zgradili nekaj svojega. Potuhnimo v njihov delovni prostor in prisluhnimo njihovemu pogovoru.
Alice: Zaženimo to kodo in ugotovimo vsoto. Bob: To kodo sem zagnal nekaj minut nazaj, vendar še vedno ne prikazuje rezultatov. Kaj je narobe s tem?
Ups! Nekaj je šlo narobe! Računalnik je najbolj determiniran stroj. Če se vrnete nazaj in poskusite znova zagnati, ne bo pomagalo. Torej, analizirajmo, kaj je narobe s to preprosto kodo.
Dva najbolj dragocena vira za računalniški program sta čas in pomnilnik .
Čas, ki ga računalnik potrebuje za zagon kode, je:
Čas za zagon kode = število navodil * čas za izvedbo vsakega ukaza
Število navodil je odvisno od kode, ki ste jo uporabili, in čas, potreben za izvedbo posamezne kode, je odvisen od vaše naprave in prevajalnika.
V tem primeru je skupno število izvršenih navodil (recimo x) , kar jex = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Predpostavimo, da lahko računalnik izvede navodila v eni sekundi (odvisno od konfiguracije računalnika). Čas, potreben za zagon nad kodo, jey = 108
Čas, potreben za zagon kode = x / y (več kot 16 minut)
Ali je mogoče algoritem optimizirati tako, da Alice in Bobu ni treba čakati 16 minut vsakič, ko zaženeta to kodo?
Prepričan sem, da ste že uganili pravi način. Vsota prvih N naravnih števil je podana s formulo:
Vsota = N * (N + 1) / 2
Pretvorba v kodo bo videti nekako takole:
int vsota (int N) (vrne N * (N + 1) / 2;)
Ta koda se izvede v samo enem navodilu in opravi nalogo, ne glede na vrednost. Naj bo večje od skupnega števila atomov v vesolju. Rezultat bo našel v kratkem.
V tem primeru je čas za rešitev težave 1/y(to je 10 nanosekund). Mimogrede, fuzijska reakcija vodikove bombe traja 40-50 ns, kar pomeni, da se bo vaš program uspešno zaključil, tudi če nekdo vrže vodikovo bombo v vaš računalnik hkrati, ko ste zagnali kodo. :)
Opomba: Računalniki za izračun množenja in deljenja upoštevajo nekaj navodil (ne 1). Rekel sem 1 samo zaradi poenostavitve.
Več o razširljivosti
Prilagodljivost je lestvica plus sposobnost, kar pomeni kakovost algoritma / sistema za reševanje večjih težav.
Razmislite o problemu postavitve učilnice za 50 učencev. Ena najpreprostejših rešitev je rezervirati sobo, dobiti tablo, nekaj krede in težava je rešena.
Kaj pa, če se velikost težave poveča? Kaj pa, če bi se število študentov povečalo na 200?
Rešitev še vedno drži, vendar potrebuje več sredstev. V tem primeru boste verjetno potrebovali veliko večjo sobo (verjetno gledališče), projekcijsko platno in digitalno pisalo.
Kaj pa, če bi se število študentov povečalo na 1000?
Rešitev ne uspe ali porabi veliko sredstev, ko se velikost težave poveča. To pomeni, da vaša rešitev ni bila razširljiva.
Kaj je torej razširljiva rešitev?
Razmislite o spletnem mestu, kot je Khanacademy, milijoni študentov si lahko hkrati ogledajo videoposnetke, preberejo odgovore in ne potrebujejo več virov. Torej lahko rešitev reši probleme večje velikosti zaradi stiskanja virov.
Če vidite našo prvo rešitev za iskanje vsote prvih N naravnih števil, ni bila prilagodljiva. To je zato, ker je zahtevala linearno rast v času z linearno rastjo velikosti problema. Takšni algoritmi so znani tudi kot linearno razširljivi algoritmi.
Naša druga rešitev je bila zelo razširljiva in ni zahtevala več časa za rešitev problema večje velikosti. Ti so znani kot algoritmi s konstantnim časom.
Pomnilnik je drag
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.
Če algoritmov ne poznate dobro, ne boste mogli ugotoviti, ali lahko trenutno optimizirate kodo, ki jo pišete. Pričakuje se, da jih poznate vnaprej in jih uporabljate, kjer je to mogoče in kritično.
Izrecno smo govorili o razširljivosti algoritmov. Programski sistem je sestavljen iz številnih takih algoritmov. Optimizacija katerega koli izmed njih vodi do boljšega sistema.
Vendar je pomembno opozoriti, da to ni edini način, da naredimo sistem prilagodljiv. Na primer, tehnika, znana kot porazdeljeno računalništvo, omogoča, da se neodvisni deli programa izvajajo na več strojih skupaj, zaradi česar je še bolj razširljiv.
