Tässä artikkelissa opitaan, miksi jokaisen ohjelmoijan tulisi oppia tietorakenteet ja algoritmit esimerkkien avulla.
Tämä artikkeli on tarkoitettu niille, jotka ovat juuri aloittaneet algoritmien oppimisen ja miettineet kuinka vaikuttavaa on parantaa heidän uransa / ohjelmointitaitojaan. Se on tarkoitettu myös niille, jotka ihmettelevät, miksi suuryritykset, kuten Google, Facebook ja Amazon, palkkaavat ohjelmoijia, jotka ovat poikkeuksellisen hyviä algoritmien optimoinnissa.
Mitä algoritmit ovat?
Epävirallisesti algoritmi ei ole muuta kuin maininta ongelman ratkaisemiseksi tarvittavista vaiheista. Ne ovat pohjimmiltaan ratkaisu.
Esimerkiksi algoritmi faktorialien ongelman ratkaisemiseksi saattaa näyttää tältä:
Tehtävä: Etsi n : n kerroin
Alusta tosiasia = 1 Jokaiselle arvolle v alueella 1 - n: Kerro se v: llä tosiasia sisältää n: n faktorialin
Tässä algoritmi kirjoitetaan englanniksi. Jos se kirjoitettiin ohjelmointikielellä, kutsumme sitä koodaamaan . Tässä on koodi luvun faktorin löytämiseksi C ++: ssa.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Ohjelmoinnissa on kyse tietorakenteista ja algoritmeista. Tietorakenteita käytetään tietojen säilyttämiseen, kun taas algoritmeja käytetään ongelman ratkaisemiseen kyseisten tietojen avulla.
Tietorakenteet ja algoritmit (DSA) käyvät läpi ratkaisuja vakio-ongelmiin yksityiskohtaisesti ja antavat sinulle käsityksen siitä, kuinka tehokasta on käyttää kutakin niistä. Se opettaa myös tieteen algoritmin tehokkuuden arvioimisesta. Tämä antaa sinulle mahdollisuuden valita parhaat vaihtoehdot.
Tietorakenteiden ja algoritmien käyttö koodisi skaalattavaksi
Aika on arvokasta.
Oletetaan, että Alice ja Bob yrittävät ratkaista yksinkertaisen ongelman löytää ensimmäisten 10 11 luonnollisen luvun summa . Samalla kun Bob kirjoitti algoritmia, Alice toteutti sen osoittaakseen, että se on yhtä yksinkertaista kuin kritisoida Donald Trumpia.
Algoritmi (kirjoittanut Bob)
Alusta summa = 0 jokaiselle luonnolliselle luvulle n alueella 1 - 1011 (mukaan lukien): lisää n summa summaan on vastauksesi
Koodi (kirjoittanut Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice ja Bob tuntevat itsensä euforisiksi siitä, että he voisivat rakentaa jotain omaa melkein hetkessä. Hyppäämme heidän työtilaansa ja kuuntelemme heidän keskusteluaan.
Alice: Suoritetaan tämä koodi ja selvitetään summa. Bob: Juoksin tämän koodin muutama minuutti sitten, mutta se ei silti näytä lähtöä. Mikä siinä on vikana?
Hups! Jotain meni pieleen! Tietokone on deterministisin kone. Paluu ja yrittäminen suorittaa se uudelleen ei auta. Joten analysoidaan, mikä on tämän yksinkertaisen koodin vika.
Kaksi tietokoneohjelman arvokkainta resurssia ovat aika ja muisti .
Aika, jonka tietokone kuluttaa koodin suorittamiseen, on:
Aika suorittaa koodi = ohjeiden määrä * aika suorittaa jokaisen käskyn
Ohjeiden määrä riippuu käyttämästäsi koodista, ja kunkin koodin suorittamiseen kuluva aika riippuu koneestasi ja kääntäjästäsi.
Tässä tapauksessa suoritettujen käskyjen kokonaismäärä (sanotaan x) on , mikä onx = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Oletetaan, että tietokone pystyy suorittamaan ohjeet sekunnissa (se voi vaihdella koneen kokoonpanon mukaan). Koodin ylläoloaika ony = 108
Koodin suorittamiseen kulunut aika = x / y (yli 16 minuuttia)
Onko mahdollista optimoida algoritmi niin, että Alicen ja Bobin ei tarvitse odottaa 16 minuuttia joka kerta, kun he suorittavat tämän koodin?
Olen varma, että arvasit jo oikean menetelmän. Ensimmäisen N luonnollisen luvun summa saadaan kaavalla:
Summa = N * (N + 1) / 2
Muuntaminen koodiksi näyttää tältä:
int summa (int N) (paluu N * (N + 1) / 2;)
Tämä koodi suorittaa vain yhden käskyn ja saa tehtävän suoritetuksi riippumatta siitä, mikä arvo on. Olkoon sen suurempi kuin maailmankaikkeuden atomien kokonaismäärä. Se löytää tuloksen hetkessä.
Tässä tapauksessa ongelman ratkaisemiseen kuluva aika on 1/y(mikä on 10 nanosekuntia). Muuten, vetypommin fuusioreaktio kestää 40-50 ns, mikä tarkoittaa, että ohjelmasi suoritetaan loppuun onnistuneesti, vaikka joku heittäisi vetypommin tietokoneellesi samalla, kun suoritit koodisi. :)
Huomaa: Tietokoneet käyttävät muutamia ohjeita (ei 1) kerrotaan ja jaetaan. Olen sanonut 1 vain yksinkertaisuuden vuoksi.
Lisää skaalautuvuudesta
Skaalautuvuus on mittakaava plus kyky, mikä tarkoittaa algoritmin / järjestelmän laatua käsitellä suuremman koon ongelmaa.
Harkitse ongelmaa, joka koskee 50 oppilaan luokan perustamista. Yksi yksinkertaisimmista ratkaisuista on varata huone, hankkia liitutaulu, muutama liitu ja ongelma on ratkaistu.
Mutta entä jos ongelman koko kasvaa? Entä jos opiskelijoiden määrä kasvaa 200: een?
Ratkaisu on edelleen voimassa, mutta se vaatii enemmän resursseja. Tässä tapauksessa tarvitset todennäköisesti paljon suuremman huoneen (luultavasti teatterin), projektorin näytön ja digitaalisen kynän.
Entä jos opiskelijoiden määrä kasvaa 1000: een?
Ratkaisu epäonnistuu tai käyttää paljon resursseja, kun ongelman koko kasvaa. Tämä tarkoittaa, että ratkaisusi ei ollut skaalautuva.
Mikä on sitten skaalautuva ratkaisu?
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.
Jos et tiedä algoritmeja hyvin, et pysty tunnistamaan, pystytkö optimoimaan juuri kirjoittamasi koodin. Sinun odotetaan tuntevan ne etukäteen ja soveltavan niitä aina, kun se on mahdollista ja kriittistä.
Puhuimme erityisesti algoritmien skaalautuvuudesta. Ohjelmistojärjestelmä koostuu monista tällaisista algoritmeista. Jonkin niistä optimointi johtaa parempaan järjestelmään.
On kuitenkin tärkeää huomata, että tämä ei ole ainoa tapa tehdä järjestelmästä skaalautuva. Esimerkiksi hajautettuna laskennana tunnettu tekniikka sallii ohjelman itsenäisten osien suorittaa useita koneita yhdessä, mikä tekee siitä entistä skaalattavamman.
