Ebben a cikkben megtudhatjuk, miért kell minden programozónak példák segítségével megtanulnia az adatszerkezeteket és az algoritmusokat.
Ez a cikk azoknak szól, akik most kezdték el tanulni az algoritmusokat, és azon gondolkodtak, hogy milyen hatással lesz karrierjük / programozási képességeik fejlesztése. Azoknak is kíváncsi, hogy vajon miért vesznek fel olyan nagyvállalatok, mint a Google, a Facebook és az Amazon programozók, akik kivételesen jól tudják optimalizálni az algoritmusokat.
Mik azok az algoritmusok?
Informálisan az algoritmus nem más, mint a probléma megoldásának lépéseinek megemlítése. Lényegében megoldást jelentenek.
Például a tényezők problémájának megoldására szolgáló algoritmus a következőképpen nézhet ki:
Probléma: Keresse meg az n tényezőjét
Inicializálja a tényt = 1 Minden v értékre az 1-től n-ig terjedő tartományban: Szorozzuk meg a tényt v tényvel, amely az n tényezőjét tartalmazza
Itt az algoritmus angolul íródott. Ha programozási nyelven íródott, akkor inkább kódolásnak hívtuk. Itt van egy kód a szám faktoriális számának megkereséséhez a C ++ nyelven.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
A programozás az adatstruktúrákról és az algoritmusokról szól. Az adatszerkezetek az adatok tárolására szolgálnak, míg algoritmusok a probléma megoldására az adatok felhasználásával.
Az adatstruktúrák és algoritmusok (DSA) részletesen áttekintik a szokásos problémák megoldásait, és betekintést nyújtanak abba, hogy mennyire hatékony mindegyiket használni. Azt is megtanítja az algoritmus hatékonyságának értékelésére. Ez lehetővé teszi, hogy a legkülönbözőbb lehetőségek közül választhat.
Adatszerkezetek és algoritmusok használata a kód méretezhetővé tételéhez
Az idő drága.
Tegyük fel, hogy Alice és Bob egyszerű problémát próbálnak megoldani az első 10 11 természetes szám összegének megtalálásában . Amíg Bob írta az algoritmust, Alice végrehajtotta azt, bizonyítva, hogy ez olyan egyszerű, mint Donald Trump kritizálása.
Algoritmus (Bob)
Inicializálja az összeget = 0 minden n természetes számra az 1–1011 tartományban (beleértve): adjon n-t az összegösszeghez a válasza
Kód (Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice és Bob eufóriában érzik magukat azzal kapcsolatban, hogy szinte pillanatok alatt felépíthetnek valamit. Bújjunk be a munkaterületükbe, és hallgassuk meg a beszélgetésüket.
Alice: Futtassuk ezt a kódot, és derítsük ki az összeget. Bob: Néhány perccel ezelőtt futtattam ezt a kódot, de még mindig nem jelenik meg a kimenet. Mi a baj ezzel?
Hoppá! Valami rosszul sült el! A számítógép a legmeghatározóbb gép. A visszalépés és az újbóli futtatás nem segít. Tehát elemezzük, mi a baj ezzel az egyszerű kóddal.
A számítógépes programok két legértékesebb erőforrása az idő és a memória .
A számítógép futtatásához szükséges idő a kód futtatásához:
A kód futtatásának ideje = az utasítások száma * az egyes utasítások végrehajtásának ideje
Az utasítások száma a használt kódtól függ, az egyes kódok végrehajtásához szükséges idő pedig a géptől és a fordítótól függ.
Ebben az esetben a végrehajtott utasítások teljes száma (tegyük fel x) , amix = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Tegyük fel, hogy a számítógép egy másodperc alatt képes végrehajtani az utasításokat (a gép konfigurációjától függően változhat). A kód feletti futtatáshoz szükséges idő:y = 108
A kód futtatásához szükséges idő = x / y (több mint 16 perc)
Optimalizálható az algoritmus úgy, hogy Alice-nek és Bobnak ne kelljen 16 percet várnia minden alkalommal, amikor futtatja ezt a kódot?
Biztos vagyok benne, hogy már kitalálta a helyes módszert. Az első N természetes szám összegét a képlet adja meg:
Összeg = N * (N + 1) / 2
Ha kóddá konvertálod, a következőképpen néz ki:
int összeg (int N) (visszatérés N * (N + 1) / 2;)
Ez a kód csak egy utasításban hajtja végre, és elvégzi a feladatot, függetlenül az értékétől. Legyen nagyobb, mint az univerzum összes atomja. Pillanatok alatt megtalálja az eredményt.
A probléma megoldásának ideje ebben az esetben 1/y(ami 10 nanoszekundum). Egyébként a hidrogénbomba fúziós reakciója 40-50 ns-t vesz igénybe, ami azt jelenti, hogy a programod akkor is sikeresen teljesül, ha valaki a hidrogénbombát dobja a számítógépedre, miközben futtattad a kódodat. :)
Megjegyzés: A számítógépek néhány (nem 1) utasítást alkalmaznak a szorzás és osztás kiszámításához. Csak az egyszerűség kedvéért mondtam 1-et.
További információ a méretezhetőségről
A skálázhatóság a skála plusz képesség, ami azt jelenti, hogy egy algoritmus / rendszer képes kezelni a nagyobb méretű problémát.
Fontolja meg az 50 tanulóból álló osztályterem kialakításának problémáját. Az egyik legegyszerűbb megoldás szobafoglalás, tábla, néhány kréta beszerzése, és a probléma megoldódott.
De mi van akkor, ha a probléma mérete növekszik? Mi lenne, ha a hallgatók száma 200-ra nőne?
A megoldás még mindig érvényes, de több erőforrásra van szüksége. Ebben az esetben valószínűleg sokkal nagyobb helyiségre (valószínűleg színházra), projektor képernyőre és digitális tollra lesz szüksége.
Mi lenne, ha a hallgatók száma 1000-re nőne?
A megoldás meghiúsul, vagy sok erőforrást használ, amikor a probléma nagysága megnő. Ez azt jelenti, hogy a megoldása nem volt méretezhető.
Mi akkor a méretezhető megoldás?
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.
Ha nem ismeri jól az algoritmusokat, akkor nem tudja azonosítani, hogy optimalizálhatja-e a most írt kódot. Várhatóan előre megismeri őket, és alkalmazza őket, ahol csak lehetséges és kritikus.
Konkrétan az algoritmusok skálázhatóságáról beszéltünk. A szoftverrendszer sok ilyen algoritmusból áll. Bármelyikük optimalizálása jobb rendszerhez vezet.
Fontos azonban megjegyezni, hogy nem csak így lehet a rendszert méretezhetővé tenni. Például az elosztott számítástechnikának nevezett technika lehetővé teszi a program független részeinek több gépen történő futtatását, így még skálázhatóbbá válik.
