I denne artikel lærer vi, hvorfor hver programmør skal lære datastrukturer og algoritmer ved hjælp af eksempler.
Denne artikel er for dem, der lige er begyndt at lære algoritmer og spekulerede på, hvor effektiv det vil være at øge deres karriere / programmeringsevner. Det er også for dem, der spekulerer på, hvorfor store virksomheder som Google, Facebook og Amazon ansætter programmører, der er usædvanligt gode til at optimere algoritmer.
Hvad er algoritmer?
Uformelt er en algoritme kun en omtale af trin til løsning af et problem. De er i det væsentlige en løsning.
For eksempel kan en algoritme til at løse problemet med faktorier se sådan ud:
Problem: Find faktoren for n
Initialiser fakta = 1 For hver værdi v i området 1 til n: Multiplicer fakta med v faktum indeholder faktoren for n
Her er algoritmen skrevet på engelsk. Hvis det blev skrevet på et programmeringssprog, ville vi kalde det til kode i stedet. Her er en kode til at finde en faktor i C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Programmering handler om datastrukturer og algoritmer. Datastrukturer bruges til at indeholde data, mens algoritmer bruges til at løse problemet ved hjælp af disse data.
Datastrukturer og algoritmer (DSA) gennemgår detaljerede løsninger på standardproblemer og giver dig et indblik i, hvor effektivt det er at bruge hver enkelt af dem. Det lærer dig også videnskaben om at evaluere effektiviteten af en algoritme. Dette giver dig mulighed for at vælge det bedste af forskellige valg.
Brug af datastrukturer og algoritmer for at gøre din kode skalerbar
Tid er dyrebar.
Antag, Alice og Bob prøver at løse et simpelt problem med at finde summen af de første 10 11 naturlige tal. Mens Bob skrev algoritmen, implementerede Alice den, hvilket beviste, at det er så simpelt som at kritisere Donald Trump.
Algoritme (af Bob)
Initialiser summen = 0 for hvert naturlige tal n i området 1 til 1011 (inklusive): tilføj n til summen er dit svar
Kode (af Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice og Bob føler sig euforiske over sig selv, at de kunne bygge noget af deres egne på næsten ingen tid. Lad os snige sig ind i deres arbejdsområde og lytte til deres samtale.
Alice: Lad os køre denne kode og finde ud af summen. Bob: Jeg kørte denne kode et par minutter tilbage, men den viser stadig ikke output. Hvad er der galt med det?
Ups! Noget gik galt! En computer er den mest deterministiske maskine. At gå tilbage og prøve at køre det igen hjælper ikke. Så lad os analysere, hvad der er galt med denne enkle kode.
To af de mest værdifulde ressourcer til et computerprogram er tid og hukommelse .
Den tid, det tager af computeren at køre kode, er:
Tid til at køre kode = antal instruktioner * tid til at udføre hver instruktion
Antallet af instruktioner afhænger af den kode, du har brugt, og den tid det tager at udføre hver kode afhænger af din maskine og kompilator.
I dette tilfælde er det samlede antal udførte instruktioner (lad os sige x) , hvilket erx = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Lad os antage, at en computer kan udføre instruktioner på et sekund (det kan variere afhængigt af maskinens konfiguration). Det tager tid at køre over kodeny = 108
Det tager tid at køre kode = x / y (mere end 16 minutter)
Er det muligt at optimere algoritmen, så Alice og Bob ikke behøver at vente i 16 minutter, hver gang de kører denne kode?
Jeg er sikker på, at du allerede har gættet den rigtige metode. Summen af de første N naturlige tal er givet ved formlen:
Sum = N * (N + 1) / 2
Konvertering til kode vil se sådan ud:
int sum (int N) (return N * (N + 1) / 2;)
Denne kode udføres i kun en instruktion og får opgaven udført, uanset hvilken værdi der er. Lad det være større end det samlede antal atomer i universet. Det finder resultatet på ingen tid.
Den tid, det tager at løse problemet, er i dette tilfælde 1/y(hvilket er 10 nanosekunder). Forresten tager fusionsreaktionen af en brintbombe 40-50 ns, hvilket betyder, at dit program fuldføres med succes, selvom nogen kaster en brintbombe på din computer, samtidig med at du kørte din kode. :)
Bemærk: Computere tager et par instruktioner (ikke 1) for at beregne multiplikation og division. Jeg har sagt 1 bare for enkelhedens skyld.
Mere om skalerbarhed
Skalerbarhed er skala plus evne, hvilket betyder kvaliteten af en algoritme / system til at håndtere problemet med større størrelse.
Overvej problemet med at oprette et klasseværelse med 50 studerende. En af de enkleste løsninger er at booke et rum, få et tavle, et par kridt, og problemet er løst.
Men hvad nu hvis problemets størrelse øges? Hvad hvis antallet af studerende steg til 200?
Løsningen holder stadig, men den har brug for flere ressourcer. I dette tilfælde har du sandsynligvis brug for et meget større rum (sandsynligvis et teater), en projektorskærm og en digital pen.
Hvad hvis antallet af studerende steg til 1000?
Løsningen mislykkes eller bruger mange ressourcer, når problemets størrelse øges. Dette betyder, at din løsning ikke var skalerbar.
Hvad er en skalerbar løsning 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.
Hvis du ikke kender algoritmer godt, kan du ikke identificere, om du kan optimere den kode, du skriver lige nu. Det forventes, at du kender dem på forhånd og anvender dem, hvor det er muligt og kritisk.
Vi talte specifikt om skalerbarheden af algoritmer. Et softwaresystem består af mange sådanne algoritmer. Optimering af en af dem fører til et bedre system.
Det er dog vigtigt at bemærke, at dette ikke er den eneste måde at gøre et system skalerbart på. For eksempel tillader en teknik kendt som distribueret databehandling uafhængige dele af et program at køre til flere maskiner sammen, hvilket gør det endnu mere skalerbart.
