In diesem Artikel erfahren wir anhand von Beispielen, warum jeder Programmierer Datenstrukturen und Algorithmen lernen sollte.
Dieser Artikel richtet sich an diejenigen, die gerade mit dem Erlernen von Algorithmen begonnen haben und sich gefragt haben, wie effektiv es sein wird, ihre Karriere- / Programmierkenntnisse zu verbessern. Es ist auch für diejenigen gedacht, die sich fragen, warum große Unternehmen wie Google, Facebook und Amazon Programmierer einstellen, die Algorithmen außerordentlich gut optimieren können.
Was sind Algorithmen?
Informell ist ein Algorithmus nichts anderes als eine Erwähnung von Schritten zur Lösung eines Problems. Sie sind im Wesentlichen eine Lösung.
Ein Algorithmus zur Lösung des Problems der Fakultäten könnte beispielsweise folgendermaßen aussehen:
Problem: Finden Sie die Fakultät von n
Fakt initialisieren = 1 Für jeden Wert v im Bereich 1 bis n: Multiplizieren Sie den Fakt mit v Fakt enthält die Fakultät von n
Hier ist der Algorithmus in Englisch geschrieben. Wenn es in einer Programmiersprache geschrieben wäre, würden wir es stattdessen als Code bezeichnen . Hier ist ein Code zum Ermitteln der Fakultät einer Zahl in C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Bei der Programmierung dreht sich alles um Datenstrukturen und Algorithmen. Datenstrukturen werden verwendet, um Daten zu speichern, während Algorithmen verwendet werden, um das Problem unter Verwendung dieser Daten zu lösen.
Datenstrukturen und Algorithmen (DSA) gehen Lösungen für Standardprobleme im Detail durch und geben Ihnen einen Einblick, wie effizient es ist, jedes einzelne von ihnen zu verwenden. Außerdem lernen Sie die Wissenschaft der Bewertung der Effizienz eines Algorithmus. Auf diese Weise können Sie das Beste aus verschiedenen Optionen auswählen.
Verwendung von Datenstrukturen und Algorithmen, um Ihren Code skalierbar zu machen
Zeit ist kostbar.
Angenommen, Alice und Bob versuchen, ein einfaches Problem zu lösen, bei dem die Summe der ersten 10 11 natürlichen Zahlen ermittelt wird. Während Bob den Algorithmus schrieb, implementierte Alice ihn und bewies, dass es so einfach ist, Donald Trump zu kritisieren.
Algorithmus (von Bob)
Initialisiere sum = 0 für jede natürliche Zahl n im Bereich von 1 bis 1011 (einschließlich): Addiere n zur Summensumme ist deine Antwort
Code (von Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice und Bob fühlen sich euphorisch, dass sie in kürzester Zeit etwas Eigenes bauen könnten. Lassen Sie uns in ihren Arbeitsbereich schleichen und ihre Unterhaltung anhören.
Alice: Lass uns diesen Code ausführen und die Summe herausfinden. Bob: Ich habe diesen Code vor ein paar Minuten ausgeführt, aber er zeigt immer noch nicht die Ausgabe. Was stimmt damit nicht?
Ups! Irgendwas lief schief! Ein Computer ist die deterministischste Maschine. Zurückgehen und versuchen, es erneut auszuführen, wird nicht helfen. Analysieren wir also, was mit diesem einfachen Code nicht stimmt.
Zwei der wertvollsten Ressourcen für ein Computerprogramm sind Zeit und Speicher .
Der Computer benötigt Zeit, um Code auszuführen:
Zeit zum Ausführen von Code = Anzahl der Anweisungen * Zeit zum Ausführen jeder Anweisung
Die Anzahl der Anweisungen hängt von dem von Ihnen verwendeten Code ab, und die Zeit, die zum Ausführen der einzelnen Codes benötigt wird, hängt von Ihrem Computer und Compiler ab.
In diesem Fall ausgeführt die Gesamtzahl der Anweisungen (sagen wir mal x) , das ist ,x = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Nehmen wir an, dass ein Computer Anweisungen in einer Sekunde ausführen kann (dies kann je nach Maschinenkonfiguration variieren). Die Zeit, die zum Ausführen des obigen Codes benötigt wird, beträgty = 108
Zeitaufwand für die Ausführung von Code = x / y (länger als 16 Minuten)
Ist es möglich, den Algorithmus so zu optimieren, dass Alice und Bob nicht jedes Mal, wenn sie diesen Code ausführen, 16 Minuten warten müssen?
Ich bin sicher, dass Sie bereits die richtige Methode erraten haben. Die Summe der ersten N natürlichen Zahlen ergibt sich aus der Formel:
Summe = N * (N + 1) / 2
Das Konvertieren in Code sieht ungefähr so aus:
int sum (int N) (Rückgabe N * (N + 1) / 2;)
Dieser Code wird in nur einer Anweisung ausgeführt und erledigt die Aufgabe unabhängig vom Wert. Sei es größer als die Gesamtzahl der Atome im Universum. Das Ergebnis wird in kürzester Zeit gefunden.
Die zur Lösung des Problems benötigte Zeit beträgt in diesem Fall 1/y(dh 10 Nanosekunden). Übrigens dauert die Fusionsreaktion einer Wasserstoffbombe 40-50 ns, was bedeutet, dass Ihr Programm erfolgreich abgeschlossen wird, selbst wenn jemand gleichzeitig mit der Ausführung Ihres Codes eine Wasserstoffbombe auf Ihren Computer wirft. :) :)
Hinweis: Computer benötigen einige Anweisungen (nicht 1), um die Multiplikation und Division zu berechnen. Ich habe 1 nur der Einfachheit halber gesagt.
Mehr zur Skalierbarkeit
Skalierbarkeit ist Skalierung plus Fähigkeit, was die Qualität eines Algorithmus / Systems bedeutet, um das Problem der größeren Größe zu bewältigen.
Betrachten Sie das Problem der Einrichtung eines Klassenzimmers mit 50 Schülern. Eine der einfachsten Lösungen besteht darin, ein Zimmer zu buchen, eine Tafel und ein paar Kreiden zu besorgen, und das Problem ist gelöst.
Aber was ist, wenn das Problem größer wird? Was wäre, wenn die Zahl der Schüler auf 200 steigen würde?
Die Lösung hält noch, benötigt aber mehr Ressourcen. In diesem Fall benötigen Sie wahrscheinlich einen viel größeren Raum (wahrscheinlich ein Theater), eine Projektionswand und einen digitalen Stift.
Was ist, wenn die Anzahl der Schüler auf 1000 steigt?
Die Lösung schlägt fehl oder verbraucht viele Ressourcen, wenn das Problem größer wird. Dies bedeutet, dass Ihre Lösung nicht skalierbar war.
Was ist dann eine skalierbare Lösung?
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.
Wenn Sie die Algorithmen nicht gut kennen, können Sie nicht feststellen, ob Sie den Code, den Sie gerade schreiben, optimieren können. Von Ihnen wird erwartet, dass Sie sie im Voraus kennen und wo immer möglich und kritisch anwenden.
Wir haben speziell über die Skalierbarkeit von Algorithmen gesprochen. Ein Softwaresystem besteht aus vielen solchen Algorithmen. Die Optimierung eines dieser Systeme führt zu einem besseren System.
Es ist jedoch wichtig zu beachten, dass dies nicht die einzige Möglichkeit ist, ein System skalierbar zu machen. Beispielsweise ermöglicht eine als verteiltes Rechnen bekannte Technik, dass unabhängige Teile eines Programms auf mehreren Computern zusammen ausgeführt werden, wodurch es noch skalierbarer wird.
