Šajā rakstā mēs uzzināsim, kāpēc katram programmētājam ar piemēru palīdzību būtu jāapgūst datu struktūras un algoritmi.
Šis raksts ir paredzēts tiem, kuri tikko ir sākuši mācīties algoritmus un domāja, cik ietekmīgi būs uzlabot viņu karjeras / programmēšanas prasmes. Tas ir domāts arī tiem, kas brīnās, kāpēc tādas lielas kompānijas kā Google, Facebook un Amazon algo programmētājus, kuri ārkārtīgi labi prot optimizēt algoritmus.
Kas ir algoritmi?
Neoficiāli algoritms ir nekas cits kā problēmas risināšanas soļu pieminēšana. Būtībā tie ir risinājums.
Piemēram, algoritms faktoriālu problēmas risināšanai varētu izskatīties šādi:
Problēma: atrodiet n faktoriālo
Inicializējiet faktu = 1 Katrai vērtībai v diapazonā no 1 līdz n: Faktu reiziniet ar v faktu, kurā ir n faktoriāls
Šeit algoritms ir rakstīts angļu valodā. Ja tas būtu uzrakstīts programmēšanas valodā, mēs to vietā sauktu par kodu . Šeit ir kods skaitļa faktoriāla atrašanai C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Programmēšana ir saistīta ar datu struktūrām un algoritmiem. Datu struktūras tiek izmantotas datu glabāšanai, savukārt algoritmi tiek izmantoti problēmas risināšanai, izmantojot šos datus.
Datu struktūras un algoritmi (DSA) detalizēti izskata standarta problēmu risinājumus un sniedz ieskatu par to, cik efektīvi ir izmantot katru no tiem. Tas arī māca jums zinātni par algoritma efektivitātes novērtēšanu. Tas ļauj jums izvēlēties labāko no dažādām iespējām.
Datu struktūru un algoritmu izmantošana koda mērogošanai
Laiks ir dārgs.
Pieņemsim, ka Alise un Bobs mēģina atrisināt vienkāršu problēmu - atrast pirmo 10 11 dabisko skaitļu summu. Kamēr Bobs rakstīja algoritmu, Alise to ieviesa, pierādot, ka tas ir tikpat vienkārši kā Donalda Trampa kritizēšana.
Algoritms (autors Bobs)
Inicializējiet summu = 0 katram dabiskajam skaitlim n diapazonā no 1 līdz 1011 (ieskaitot): pievienojiet n summas summai, kas ir jūsu atbilde
Kods (autore Alise)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alise un Bobs izjūt eiforiju par sevi, ka gandrīz visu laiku varētu uzcelt kaut ko savu. Ielīdīsim viņu darba telpā un uzklausīsim viņu sarunu.
Alise: Palaidīsim šo kodu un uzzināsim summu. Bobs: Es palaistu šo kodu dažas minūtes atpakaļ, bet tas joprojām nerāda rezultātu. Kas tam vainas?
Hmm! Kaut kas nogāja greizi! Dators ir visvairāk determinējošā mašīna. Atgriešanās un mēģinājumi to palaist vēlreiz nepalīdzēs. Tāpēc analizēsim, kas ir nepareizs ar šo vienkāršo kodu.
Divi no vērtīgākajiem datorprogrammas resursiem ir laiks un atmiņa .
Laiks, ko dators prasa koda izpildei, ir:
Laiks izpildīt kodu = instrukciju skaits * laiks katras instrukcijas izpildei
Norādījumu skaits ir atkarīgs no izmantotā koda, un katra koda izpildes laiks ir atkarīgs no jūsu mašīnas un kompilatora.
Šajā gadījumā izpildīto instrukciju kopējais skaits (pieņemsim, ka x) ir , kas irx = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Pieņemsim, ka dators var izpildīt instrukcijas vienā sekundē (tas var atšķirties atkarībā no iekārtas konfigurācijas). Laiks, kas vajadzīgs, lai palaistu virs koda, iry = 108
Laiks, kas vajadzīgs koda izpildei = x / y (vairāk nekā 16 minūtes)
Vai ir iespējams optimizēt algoritmu tā, lai Alisei un Bobam nebūtu jāgaida 16 minūtes katru reizi, kad viņi palaiž šo kodu?
Esmu pārliecināts, ka jūs jau uzminējāt pareizo metodi. Pirmo N dabisko skaitļu summa tiek aprēķināta pēc formulas:
Summa = N * (N + 1) / 2
Konvertēšana kodā izskatīsies apmēram šādi:
int summa (int N) (atgriešanās N * (N + 1) / 2;)
Šis kods tiek izpildīts tikai vienā instrukcijā, un uzdevums tiek veikts neatkarīgi no tā, kāda ir vērtība. Ļaujiet tam būt lielākam par kopējo atomu skaitu Visumā. Tas ātri atradīs rezultātu.
Šajā gadījumā problēmas risināšanai nepieciešams laiks 1/y(kas ir 10 nanosekundes). Starp citu, ūdeņraža bumbas kodolsintēzes reakcija prasa 40-50 ns, kas nozīmē, ka jūsu programma tiks veiksmīgi pabeigta pat tad, ja kāds jūsu datorā vienlaikus iemetīs ūdeņraža bumbu tajā pašā laikā, kad palaidāt kodu. :)
Piezīme: Datori veic dažas instrukcijas (nevis 1), lai aprēķinātu reizināšanu un dalīšanu. Esmu teicis 1 tikai vienkāršības labad.
Vairāk par mērogojamību
Mērogojamība ir skala plus spēja, kas nozīmē algoritma / sistēmas kvalitāti, lai tiktu galā ar lielāku izmēru.
Apsveriet 50 skolēnu klases izveidošanas problēmu. Viens no vienkāršākajiem risinājumiem ir rezervēt istabu, iegūt tāfeli, dažus krītus, un problēma ir atrisināta.
Bet ko tad, ja problēmas lielums palielinās? Ko darīt, ja studentu skaits palielinās līdz 200?
Risinājums joprojām ir spēkā, taču tam nepieciešami vairāk resursu. Šajā gadījumā jums, iespējams, būs nepieciešama daudz lielāka istaba (iespējams, teātris), projektora ekrāns un digitālā pildspalva.
Ko darīt, ja studentu skaits palielinās līdz 1000?
Ja problēmas lielums palielinās, risinājums neizdodas vai izmanto daudz resursu. Tas nozīmē, ka jūsu risinājums nebija mērogojams.
Kas tad ir mērogojams risinājums?
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.
Ja jūs labi nezināt algoritmus, nevarēsiet noteikt, vai varat optimizēt kodu, kuru rakstāt tieši tagad. Paredzams, ka jūs tos iepriekš zināt un pielietosit, kur vien iespējams un kritiski.
Mēs īpaši runājām par algoritmu mērogojamību. Programmatūras sistēma sastāv no daudziem šādiem algoritmiem. Jebkura no tiem optimizēšana nodrošina labāku sistēmu.
Tomēr ir svarīgi atzīmēt, ka tas nav vienīgais veids, kā padarīt sistēmu mērogojamu. Piemēram, tehnika, kas pazīstama kā sadalītā skaitļošana, ļauj neatkarīgām programmas daļām darboties vairākās mašīnās, padarot to vēl mērogojamāku.
