V tomto článku sa dozvieme, prečo by sa mal každý programátor pomocou príkladov naučiť dátové štruktúry a algoritmy.
Tento článok je určený pre tých, ktorí sa práve začali učiť algoritmy, a zaujímalo ich, aké bude mať vplyv na zlepšenie ich kariérnych / programovacích schopností. Je to tiež pre tých, ktorí sa čudujú, prečo si veľké spoločnosti ako Google, Facebook a Amazon najímajú programátorov, ktorí sú mimoriadne dobrí v optimalizácii algoritmov.
Čo sú to algoritmy?
Algoritmus neformálne nie je nič iné ako zmienka o krokoch na vyriešenie problému. Sú v podstate riešením.
Napríklad algoritmus na riešenie problému faktoriálov môže vyzerať asi takto:
Problém: Nájdite faktoriál čísla n
Inicializácia faktu = 1 Pre každú hodnotu v v rozsahu od 1 do n: Vynásobte fakt v v faktom obsahuje faktoriál n
Algoritmus je tu napísaný v angličtine. Keby bol napísaný v programovacom jazyku, nazvali by sme ho namiesto toho kódom . Tu je kód na vyhľadanie faktoriálu čísla v C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Programovanie je všetko o dátových štruktúrach a algoritmoch. Na uchovanie údajov sa používajú dátové štruktúry, zatiaľ čo na riešenie problému s týmito údajmi sa používajú algoritmy.
Dátové štruktúry a algoritmy (DSA) podrobne prechádzajú riešeniami štandardných problémov a poskytujú vám prehľad o tom, aké efektívne je ich použitie. Tiež vás naučí vedu o hodnotení efektívnosti algoritmu. Takto si môžete vybrať to najlepšie z rôznych možností.
Používanie dátových štruktúr a algoritmov na zabezpečenie škálovateľnosti vášho kódu
Čas je drahý.
Predpokladajme, že Alice a Bob sa snažia vyriešiť jednoduchý problém, ktorým je nájdenie súčtu prvých 10 11 prirodzených čísel. Zatiaľ čo Bob písal algoritmus, Alice ho implementovala, aby dokázala, že je rovnako jednoduchá ako kritika Donalda Trumpa.
Algoritmus (Bob)
Inicializujte súčet = 0 pre každé prirodzené číslo n v rozsahu 1 až 1011 (vrátane): vašou odpoveďou je súčet n k súčtu.
Kód (od Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice a Bob zo seba cítia eufóriu, že by mohli postaviť niečo svoje vlastné takmer za chvíľu. Poďme vkradnúť do ich pracovného priestoru a vypočujme si ich rozhovor.
Alice: Spustime tento kód a zistíme sumu. Bob: Spustil som tento kód pred niekoľkými minútami, ale stále nezobrazuje výstup. Čo je s tým?
Och! Niečo sa pokazilo! Počítač je najviac deterministický stroj. Návrat späť a pokus o ďalšie spustenie nepomôže. Poďme si teda zanalyzovať, čo je na tomto jednoduchom kóde zlé.
Dva z najcennejších zdrojov pre počítačový program sú čas a pamäť .
Čas potrebný na spustenie kódu počítačom je:
Čas na spustenie kódu = počet pokynov * čas na vykonanie každej inštrukcie
Počet pokynov závisí od použitého kódu a čas potrebný na vykonanie každého kódu závisí od vášho stroja a kompilátora.
V tomto prípade je celkový počet vykonaných pokynov (povedzme x) , čo jex = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Predpokladajme, že počítač dokáže vykonať pokyny za jednu sekundu (môže sa to líšiť v závislosti od konfigurácie stroja). Čas potrebný na spustenie vyššie uvedeného kódu jey = 108
Čas potrebný na spustenie kódu = x / y (viac ako 16 minút)
Je možné optimalizovať algoritmus tak, aby Alice a Bob nemuseli čakať 16 minút pri každom spustení tohto kódu?
Som si istý, že ste už uhádli správnu metódu. Súčet prvých N prirodzených čísel je daný vzorcom:
Súčet = N * (N + 1) / 2
Jeho prevedenie do kódu bude vyzerať asi takto:
int suma (int N) (návrat N * (N + 1) / 2;)
Tento kód sa vykoná iba v jednej inštrukcii a vykoná úlohu bez ohľadu na to, aká je hodnota. Nech je väčší ako celkový počet atómov vo vesmíre. Výsledok nájde rýchlo.
Čas potrebný na vyriešenie problému je v tomto prípade 1/y(čo je 10 nanosekúnd). Mimochodom, fúzna reakcia vodíkovej bomby trvá 40 - 50 ns, čo znamená, že váš program sa úspešne dokončí, aj keď niekto hodí vodíkovú bombu do vášho počítača súčasne s spustením kódu. :)
Poznámka: Počítače počítajú násobenie a delenie pomocou niekoľkých pokynov (nie 1). 1 som uviedol len pre jednoduchosť.
Viac informácií o škálovateľnosti
Škálovateľnosť je škála plus schopnosť, čo znamená kvalitu algoritmu / systému na zvládnutie problému väčších rozmerov.
Zvážte problém zriadenia učebne pre 50 študentov. Jedným z najjednoduchších riešení je rezervácia izby, získanie tabule, niekoľko kriedy a problém je vyriešený.
Čo však v prípade, že sa veľkosť problému zväčší? Čo keby sa počet študentov zvýšil na 200?
Riešenie stále platí, ale vyžaduje viac zdrojov. V takom prípade budete pravdepodobne potrebovať oveľa väčšiu miestnosť (pravdepodobne divadlo), plátno projektora a digitálne pero.
Čo keby sa počet študentov zvýšil na 1 000?
Riešenie zlyhá alebo využíva veľa zdrojov, keď sa veľkosť problému zväčší. To znamená, že vaše riešenie nebolo škálovateľné.
Čo je potom škálovateľné riešenie?
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.
Ak nepoznáte dobre algoritmy, nebudete schopní zistiť, či môžete optimalizovať kód, ktorý práve píšete. Očakáva sa od nich, že ich vopred poznáte a uplatníte ich všade, kde je to možné a kritické.
Konkrétne sme hovorili o škálovateľnosti algoritmov. Softvérový systém pozostáva z mnohých takýchto algoritmov. Optimalizácia ktoréhokoľvek z nich vedie k lepšiemu systému.
Je však dôležité poznamenať, že to nie je jediný spôsob, ako urobiť systém škálovateľným. Napríklad technika známa ako distribuované výpočty umožňuje nezávislým častiam programu bežať na viacerých počítačoch spoločne, čo ho robí ešte viac škálovateľným.
