I denne artikkelen vil vi lære hvorfor hver programmerer skal lære datastrukturer og algoritmer ved hjelp av eksempler.
Denne artikkelen er for de som nettopp har begynt å lære algoritmer og lurte på hvor innflytelsesrikt det vil være å øke deres karriere- / programmeringsevner. Det er også for de som lurer på hvorfor store selskaper som Google, Facebook og Amazon ansetter programmerere som er eksepsjonelt flinke til å optimalisere algoritmer.
Hva er algoritmer?
Uformelt er en algoritme bare en omtale av trinn for å løse et problem. De er egentlig en løsning.
For eksempel kan en algoritme for å løse problemet med fakultetene se slik ut:
Problem: Finn faktoren til n
Initialiser fakta = 1 For hver verdi v i området 1 til n: Multipliser fakta med faktum inneholder faktoren til n
Her er algoritmen skrevet på engelsk. Hvis det ble skrevet på et programmeringsspråk, ville vi kalt det til kode i stedet. Her er en kode for å finne 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 brukes til å holde data mens algoritmer brukes til å løse problemet ved hjelp av disse dataene.
Datastrukturer og algoritmer (DSA) går gjennom løsninger på standardproblemer i detalj og gir deg et innblikk i hvor effektivt det er å bruke hver enkelt av dem. Det lærer deg også vitenskapen om å evaluere effektiviteten til en algoritme. Dette lar deg velge det beste av forskjellige valg.
Bruk av datastrukturer og algoritmer for å gjøre koden din skalerbar
Tid er dyrebar.
Anta at Alice og Bob prøver å løse et enkelt problem med å finne summen av de første 10 11 naturlige tallene. Mens Bob skrev algoritmen, implementerte Alice den for å bevise at den er like enkel som å kritisere Donald Trump.
Algoritme (av Bob)
Initialiser summen = 0 for hvert naturlige tall n i området 1 til 1011 (inkludert): legg til summen er svaret ditt
Kode (av Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice og Bob føler seg euforiske av seg selv at de kan bygge noe eget på nesten ingen tid. La oss snike oss inn på arbeidsområdet og lytte til samtalen deres.
Alice: La oss kjøre denne koden og finne ut summen. Bob: Jeg kjørte denne koden for noen minutter tilbake, men den viser fremdeles ikke utdataene. Hva er galt med det?
Oops! Noe gikk galt! En datamaskin er den mest deterministiske maskinen. Å gå tilbake og prøve å kjøre den igjen hjelper ikke. Så la oss analysere hva som er galt med denne enkle koden.
To av de mest verdifulle ressursene for et dataprogram er tid og minne .
Tiden det tar for datamaskinen å kjøre kode er:
Tid til å kjøre kode = antall instruksjoner * tid til å utføre hver instruksjon
Antallet instruksjoner avhenger av koden du brukte, og tiden det tar å utføre hver kode, avhenger av maskinen din og kompilatoren.
I dette tilfellet er det totale antallet instruksjoner som er utført (la oss si x) , altsåx = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
La oss anta at en datamaskin kan utføre instruksjoner i løpet av ett sekund (det kan variere avhengig av maskinens konfigurasjon). Tiden det tar å løpe over koden ery = 108
Det tar tid å kjøre kode = x / y (mer enn 16 minutter)
Er det mulig å optimalisere algoritmen slik at Alice og Bob ikke trenger å vente i 16 minutter hver gang de kjører denne koden?
Jeg er sikker på at du allerede gjettet riktig metode. Summen av første N naturlige tall er gitt av formelen:
Sum = N * (N + 1) / 2
Konvertering til kode vil se ut slik:
int sum (int N) (return N * (N + 1) / 2;)
Denne koden utføres i bare en instruksjon og får oppgaven gjort uansett hvilken verdi det er. La det være større enn det totale antallet atomer i universet. Det vil finne resultatet på kort tid.
Tiden det tar å løse problemet, er i dette tilfellet 1/y(som er 10 nanosekunder). Forresten tar fusjonsreaksjonen til en hydrogenbombe 40-50 ns, noe som betyr at programmet ditt blir fullført, selv om noen kaster en hydrogenbombe på datamaskinen din samtidig som du kjørte koden. :)
Merk: Datamaskiner tar noen instruksjoner (ikke 1) for å beregne multiplikasjon og divisjon. Jeg har sagt 1 bare for enkelhets skyld.
Mer om skalerbarhet
Skalerbarhet er skala pluss evne, noe som betyr kvaliteten på en algoritme / system for å håndtere problemet med større størrelse.
Tenk på problemet med å sette opp et klasserom på 50 studenter. En av de enkleste løsningene er å bestille et rom, få en tavle, noen kritt, og problemet er løst.
Men hva om størrelsen på problemet øker? Hva om antall studenter økte til 200?
Løsningen holder fremdeles, men den trenger flere ressurser. I dette tilfellet trenger du sannsynligvis et mye større rom (sannsynligvis et teater), en projektorskjerm og en digital penn.
Hva om antall studenter økte til 1000?
Løsningen mislykkes eller bruker mye ressurser når størrelsen på problemet øker. Dette betyr at løsningen din ikke var skalerbar.
Hva er en skalerbar løsning da?
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 kjenner algoritmer godt, vil du ikke kunne identifisere om du kan optimalisere koden du skriver akkurat nå. Det forventes at du kjenner dem på forhånd og bruker dem der det er mulig og kritisk.
Vi snakket spesifikt om skalerbarhet av algoritmer. Et programvaresystem består av mange slike algoritmer. Optimalisering av en av dem fører til et bedre system.
Det er imidlertid viktig å merke seg at dette ikke er den eneste måten å gjøre et system skalerbart på. For eksempel tillater en teknikk kjent som distribuert databehandling uavhengige deler av et program å kjøre til flere maskiner sammen, noe som gjør det enda mer skalerbart.
