I den här artikeln lär vi oss varför varje programmerare bör lära sig datastrukturer och algoritmer med hjälp av exempel.
Den här artikeln är för dem som just har börjat lära sig algoritmer och undrat hur effektivt det kommer att vara att öka deras karriär / programmeringsförmåga. Det är också för dem som undrar varför stora företag som Google, Facebook och Amazon anställer programmerare som är exceptionellt bra på att optimera algoritmer.
Vad är algoritmer?
Informellt är en algoritm ingenting annat än att nämna steg för att lösa ett problem. De är i grunden en lösning.
Till exempel kan en algoritm för att lösa problemet med fakta se ut så här:
Problem: Hitta faktorn av n
Initiera fakta = 1 För varje värde v i intervallet 1 till n: Multiplicera fakta med v faktum innehåller faktorn för n
Här är algoritmen skriven på engelska. Om det skrevs på ett programmeringsspråk skulle vi istället kalla det till kod . Här är en kod för att hitta ett nummer i C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Programmering handlar om datastrukturer och algoritmer. Datastrukturer används för att hålla data medan algoritmer används för att lösa problemet med den informationen.
Datastrukturer och algoritmer (DSA) går igenom lösningar på standardproblem i detalj och ger dig en inblick i hur effektivt det är att använda var och en av dem. Det lär dig också vetenskapen om att utvärdera effektiviteten hos en algoritm. Detta gör att du kan välja det bästa av olika val.
Användning av datastrukturer och algoritmer för att göra din kod skalbar
Tid är dyrbar.
Antag att Alice och Bob försöker lösa ett enkelt problem med att hitta summan av de första 10 11 naturliga siffrorna. Medan Bob skrev algoritmen implementerade Alice den och bevisade att det är lika enkelt som att kritisera Donald Trump.
Algoritm (av Bob)
Initiera summan = 0 för varje naturligt tal n i intervallet 1 till 1011 (inklusive): lägg till n till summan är ditt svar
Kod (av Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice och Bob känner sig euforiska över att de nästan kan bygga något på egen hand. Låt oss smyga in på deras arbetsyta och lyssna på deras konversation.
Alice: Låt oss köra den här koden och ta reda på summan. Bob: Jag sprang den här koden för några minuter tillbaka men den visar fortfarande inte resultatet. Vad är fel med det?
Hoppsan! Något gick fel! En dator är den mest deterministiska maskinen. Att gå tillbaka och försöka köra igen hjälper inte. Så låt oss analysera vad som är fel med den här enkla koden.
Två av de mest värdefulla resurserna för ett datorprogram är tid och minne .
Tiden det tar för datorn att köra kod är:
Tid att köra kod = antal instruktioner * tid att utföra varje instruktion
Antalet instruktioner beror på koden du använde, och den tid det tar att köra varje kod beror på din maskin och kompilator.
I det här fallet är det totala antalet instruktioner som körs (låt oss säga x) , vilket ärx = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Låt oss anta att en dator kan utföra instruktioner på en sekund (det kan variera beroende på maskinens konfiguration). Tiden det tar att köra ovanför koden äry = 108
Det tar tid att köra kod = x / y (mer än 16 minuter)
Är det möjligt att optimera algoritmen så att Alice och Bob inte behöver vänta i 16 minuter varje gång de kör den här koden?
Jag är säker på att du redan gissat rätt metod. Summan av de första N-naturtalen ges med formeln:
Summa = N * (N + 1) / 2
Omvandling till kod kommer att se ut så här:
int summa (int N) (return N * (N + 1) / 2;)
Den här koden körs i bara en instruktion och gör uppgiften oavsett värdet. Låt det vara större än det totala antalet atomer i universum. Resultatet kommer på nolltid.
Tiden det tar att lösa problemet är i detta fall 1/y(vilket är 10 nanosekunder). Förresten tar fusionsreaktionen av en vätgasbom 40-50 ns, vilket innebär att ditt program kommer att slutföras framgångsrikt även om någon kastar en vätgasbomb på din dator samtidigt som du körde din kod. :)
Obs! Datorer tar några instruktioner (inte 1) för att beräkna multiplikation och division. Jag har sagt 1 bara för enkelhetens skull.
Mer om skalbarhet
Skalbarhet är skala plus förmåga, vilket betyder kvaliteten på en algoritm / system för att hantera problemet med större storlek.
Tänk på problemet med att skapa ett klassrum med 50 elever. En av de enklaste lösningarna är att boka ett rum, få en tavla, några kritor och problemet är löst.
Men vad händer om storleken på problemet ökar? Vad händer om antalet elever ökade till 200?
Lösningen kvarstår men den behöver mer resurser. I det här fallet behöver du förmodligen ett mycket större rum (förmodligen en teater), en projektorskärm och en digital penna.
Vad händer om antalet studenter ökade till 1000?
Lösningen misslyckas eller använder mycket resurser när storleken på problemet ökar. Det betyder att din lösning inte var skalbar.
Vad är en skalbar lösning då?
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.
Om du inte känner till algoritmer kan du inte identifiera om du kan optimera koden du skriver just nu. Du förväntas känna dem i förväg och tillämpa dem när det är möjligt och kritiskt.
Vi pratade specifikt om skalbarhet av algoritmer. Ett mjukvarusystem består av många sådana algoritmer. Optimering av någon av dem leder till ett bättre system.
Det är dock viktigt att notera att detta inte är det enda sättet att göra ett system skalbart. Till exempel tillåter en teknik som kallas distribuerad databehandling oberoende delar av ett program att köra till flera maskiner tillsammans vilket gör det ännu mer skalbart.
