U ovom ćemo članku naučiti zašto bi svaki programer uz primjere trebao naučiti strukture podataka i algoritme.
Ovaj je članak namijenjen onima koji su tek počeli učiti algoritme i pitali se koliko će impresivno biti poboljšanje njihove karijere / vještine programiranja. Također je za one koji se pitaju zašto velike tvrtke poput Googlea, Facebooka i Amazona zapošljavaju programere koji su izuzetno dobri u optimizaciji algoritama.
Što su algoritmi?
Neformalno, algoritam nije ništa drugo nego spominjanje koraka za rješavanje problema. Oni su u biti rješenje.
Na primjer, algoritam za rješavanje problema s činjenicama može izgledati otprilike ovako:
Problem: Pronađite faktorijel n
Inicijalizirajte činjenicu = 1 Za svaku vrijednost v u rasponu od 1 do n: Pomnožite činjenicu s v činjenica sadrži faktor od n
Ovdje je algoritam napisan na engleskom jeziku. Da je napisan na programskom jeziku, umjesto toga bismo ga pozvali u kod . Ovdje je kod za pronalaženje faktorijela broja u C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Programiranje se odnosi na strukture podataka i algoritme. Strukture podataka koriste se za držanje podataka, dok se algoritmi koriste za rješavanje problema pomoću tih podataka.
Strukture podataka i algoritmi (DSA) detaljno prolaze kroz rješenja za standardne probleme i daju vam uvid u to koliko je učinkovito koristiti svaki od njih. Također vas podučava znanosti procjenjivanja učinkovitosti algoritma. To vam omogućuje odabir najboljeg od različitih izbora.
Korištenje struktura podataka i algoritama kako bi vaš kod bio skalabilan
Vrijeme je dragocjeno.
Pretpostavimo da Alice i Bob pokušavaju riješiti jednostavan problem pronalaska zbroja prvih 10 11 prirodnih brojeva. Dok je Bob pisao algoritam, Alice ga je implementirala dokazujući da je jednostavan poput kritiziranja Donalda Trumpa.
Algoritam (Bob)
Inicijalizirajte zbroj = 0 za svaki prirodni broj n u rasponu od 1 do 1011 (uključujući): dodajte n zbroju zbroja vaš je odgovor
Šifra (Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice i Bob osjećaju euforiju od sebe da bi mogli gotovo nešto izgraditi u skoro trenu. Zavucimo se u njihov radni prostor i poslušajte njihov razgovor.
Alice: Pokrenimo ovaj kod i saznajmo zbroj. Bob: Pokrenuo sam ovaj kod nekoliko minuta unatrag, ali još uvijek ne prikazuje izlaz. Što ne valja s tim?
Ups! Nešto je pošlo po zlu! Računalo je najodređeniji stroj. Povratak i pokušaj ponovnog pokretanja neće pomoći. Pa analizirajmo što nije u redu s ovim jednostavnim kodom.
Dva najvrjednija resursa za računalni program su vrijeme i memorija .
Vrijeme koje računalu treba za pokretanje koda je:
Vrijeme za pokretanje koda = broj uputa * vrijeme za izvršavanje svake naredbe
Broj uputa ovisi o kodu koji ste koristili, a vrijeme potrebno za izvršavanje svakog koda ovisi o vašem stroju i kompajleru.
U ovom je slučaju ukupan broj izvršenih uputa (recimo x) , što jestx = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Pretpostavimo da računalo može izvršiti upute u jednoj sekundi (može varirati ovisno o konfiguraciji stroja). Vrijeme potrebno za pokretanje iznad koda jey = 108
Vrijeme potrebno za pokretanje koda = x / y (duže od 16 minuta)
Je li moguće optimizirati algoritam tako da Alice i Bob ne moraju čekati 16 minuta svaki put kad pokrenu ovaj kod?
Siguran sam da ste već pogodili pravu metodu. Zbroj prvih N prirodnih brojeva daje se formulom:
Zbroj = N * (N + 1) / 2
Pretvaranje u kôd izgledat će otprilike ovako:
int zbroj (int N) (povrat N * (N + 1) / 2;)
Ovaj se kôd izvršava u samo jednoj uputi i izvršava zadatak bez obzira na vrijednost. Neka bude veći od ukupnog broja atoma u svemiru. Rezultat će pronaći za tren.
U ovom slučaju potrebno je vrijeme za rješavanje problema 1/y(što je 10 nanosekundi). Inače, reakcija fuzije vodikove bombe traje 40-50 ns, što znači da će se vaš program uspješno dovršiti čak i ako netko baci vodikovu bombu na vaše računalo u isto vrijeme kada ste pokrenuli svoj kôd. :)
Napomena: Računala uzimaju nekoliko uputa (ne 1) za izračunavanje množenja i dijeljenja. Rekao sam 1 samo radi jednostavnosti.
Više o skalabilnosti
Skalabilnost je skala plus sposobnost, što znači kvalitetu algoritma / sustava za rješavanje problema veće veličine.
Razmotrite problem postavljanja učionice od 50 učenika. Jedno od najjednostavnijih rješenja je rezervirati sobu, nabaviti ploču, nekoliko kreda i problem je riješen.
Ali što ako se veličina problema poveća? Što ako se broj učenika poveća na 200?
Rješenje još uvijek vrijedi, ali treba više resursa. U ovom će vam slučaju vjerojatno trebati puno veća soba (vjerojatno kazalište), platno projektora i digitalna olovka.
Što ako se broj učenika poveća na 1000?
Rješenje ne uspijeva ili koristi puno resursa kad se veličina problema poveća. To znači da vaše rješenje nije bilo prilagodljivo.
Što je onda skalabilno rješenje?
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.
Ako algoritme ne poznajete dobro, nećete moći prepoznati možete li optimizirati kod koji trenutno pišete. Očekuje se da ih znate unaprijed i primjenjujete gdje god je to moguće i kritično.
Konkretno smo razgovarali o skalabilnosti algoritama. Softverski sustav sastoji se od mnogih takvih algoritama. Optimizacija bilo kojeg od njih dovodi do boljeg sustava.
Međutim, važno je napomenuti da ovo nije jedini način da se sustav učini skalabilnim. Na primjer, tehnika poznata kao distribuirano računanje omogućuje neovisne dijelove programa da se izvode na više strojeva zajedno što ga čini još skalabilnijim.
