In dit artikel zullen we aan de hand van voorbeelden leren waarom elke programmeur datastructuren en algoritmen zou moeten leren.
Dit artikel is bedoeld voor degenen die net zijn begonnen met het leren van algoritmen en zich afvroegen hoe belangrijk het zal zijn om hun carrière- / programmeervaardigheden te verbeteren. Het is ook voor degenen die zich afvragen waarom grote bedrijven zoals Google, Facebook en Amazon programmeurs inhuren die uitzonderlijk goed zijn in het optimaliseren van algoritmen.
Wat zijn algoritmen?
Informeel is een algoritme niets anders dan een vermelding van stappen om een probleem op te lossen. Ze zijn in wezen een oplossing.
Een algoritme om het probleem van faculteiten op te lossen zou er bijvoorbeeld ongeveer zo uit kunnen zien:
Probleem: zoek de faculteit van n
Initialiseer feit = 1 Voor elke waarde v in bereik 1 tot n: Vermenigvuldig het feit met v feit bevat de faculteit van n
Hier is het algoritme in het Engels geschreven. Als het in een programmeertaal was geschreven, zouden we het in plaats daarvan naar code noemen . Hier is een code voor het vinden van de faculteit van een getal in C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Bij programmeren draait alles om datastructuren en algoritmen. Datastructuren worden gebruikt om gegevens vast te houden, terwijl algoritmen worden gebruikt om het probleem op te lossen met behulp van die gegevens.
Datastructuren en algoritmen (DSA) doorloopt tot in detail oplossingen voor standaardproblemen en geeft u inzicht in hoe efficiënt het is om elk van deze problemen te gebruiken. Het leert je ook de wetenschap van het evalueren van de efficiëntie van een algoritme. Hierdoor kunt u het beste kiezen uit verschillende keuzes.
Gebruik van gegevensstructuren en algoritmen om uw code schaalbaar te maken
Tijd is kostbaar.
Stel dat Alice en Bob proberen een eenvoudig probleem op te lossen door de som van de eerste 10 11 natuurlijke getallen te vinden. Terwijl Bob het algoritme aan het schrijven was, implementeerde Alice het om te bewijzen dat het net zo eenvoudig is als het bekritiseren van Donald Trump.
Algoritme (door Bob)
Initialiseer som = 0 voor elk natuurlijk getal n in het bereik van 1 tot 1011 (inclusief): voeg n toe aan som som is uw antwoord
Code (door Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice en Bob voelen zich euforisch van zichzelf dat ze in een mum van tijd iets van zichzelf kunnen bouwen. Laten we hun werkruimte binnensluipen en naar hun gesprek luisteren.
Alice: Laten we deze code uitvoeren en de som uitzoeken. Bob: Ik heb deze code een paar minuten geleden uitgevoerd, maar de uitvoer wordt nog steeds niet weergegeven. Wat is er mis mee?
Oeps! Er is iets misgegaan! Een computer is de meest deterministische machine. Teruggaan en het opnieuw proberen uit te voeren, zal niet helpen. Dus laten we analyseren wat er mis is met deze eenvoudige code.
Twee van de meest waardevolle bronnen voor een computerprogramma zijn tijd en geheugen .
De tijd die de computer nodig heeft om code uit te voeren is:
Tijd om code uit te voeren = aantal instructies * tijd om elke instructie uit te voeren
Het aantal instructies is afhankelijk van de code die u hebt gebruikt, en de tijd die nodig is om elke code uit te voeren, is afhankelijk van uw machine en compiler.
In dit geval is het totale aantal uitgevoerde instructies (laten we zeggen x) , dat wil zeggenx = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Laten we aannemen dat een computer instructies in één seconde kan uitvoeren (dit kan variëren afhankelijk van de machineconfiguratie). De tijd die nodig is om bovenstaande code uit te voeren isy = 108
Tijd die nodig is om code = x / y uit te voeren (langer dan 16 minuten)
Is het mogelijk om het algoritme te optimaliseren, zodat Alice en Bob niet elke keer 16 minuten hoeven te wachten als ze deze code uitvoeren?
Ik weet zeker dat je de juiste methode al hebt geraden. De som van de eerste N natuurlijke getallen wordt gegeven door de formule:
Som = N * (N + 1) / 2
Het omzetten in code ziet er ongeveer zo uit:
int sum (int N) (return N * (N + 1) / 2;)
Deze code wordt in slechts één instructie uitgevoerd en zorgt ervoor dat de taak wordt uitgevoerd, ongeacht de waarde. Laat het groter zijn dan het totale aantal atomen in het universum. Het zal het resultaat binnen de kortste keren vinden.
De tijd die nodig is om het probleem op te lossen, is in dit geval 1/y(wat 10 nanoseconden is). Trouwens, de fusiereactie van een waterstofbom duurt 40-50 ns, wat betekent dat je programma met succes wordt voltooid, zelfs als iemand een waterstofbom op je computer gooit terwijl je je code hebt uitgevoerd. :)
Opmerking: computers hebben een paar instructies nodig (niet 1) om vermenigvuldiging en deling te berekenen. Ik heb gezegd 1 voor de eenvoud.
Meer over schaalbaarheid
Schaalbaarheid is schaal plus mogelijkheid, wat de kwaliteit betekent van een algoritme / systeem om het probleem van grotere omvang aan te pakken.
Sta eens stil bij het probleem van het opzetten van een klaslokaal met 50 studenten. Een van de eenvoudigste oplossingen is om een kamer te boeken, een schoolbord en een paar krijtjes te krijgen en het probleem is opgelost.
Maar wat als de omvang van het probleem toeneemt? Wat als het aantal studenten oploopt tot 200?
De oplossing blijft bestaan, maar er zijn meer middelen voor nodig. In dit geval heb je waarschijnlijk een veel grotere kamer (waarschijnlijk een theater), een projectorscherm en een digitale pen nodig.
Wat als het aantal studenten oploopt tot 1000?
De oplossing mislukt of gebruikt veel bronnen wanneer de omvang van het probleem toeneemt. Dit betekent dat uw oplossing niet schaalbaar was.
Wat is dan een schaalbare oplossing?
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.
Als u de algoritmen niet goed kent, kunt u niet bepalen of u de code die u op dit moment schrijft, kunt optimaliseren. Er wordt van je verwacht dat je ze van tevoren kent en waar mogelijk en kritisch toepast.
We hadden het specifiek over de schaalbaarheid van algoritmen. Een softwaresysteem bestaat uit veel van dergelijke algoritmen. Het optimaliseren van een van hen leidt tot een beter systeem.
Het is echter belangrijk op te merken dat dit niet de enige manier is om een systeem schaalbaar te maken. Met een techniek die bekend staat als gedistribueerde computergebruik, kunnen onafhankelijke delen van een programma op meerdere machines tegelijk worden uitgevoerd, waardoor het nog schaalbaarder wordt.
