AI-United » Allgemein » Top-Algorithmen und Datenstrukturen, die Sie wirklich kennen müssen

Top-Algorithmen und Datenstrukturen, die Sie wirklich kennen müssen

Wenn Sie Software-Ingenieur werden möchten, aber nicht wissen, wo Sie anfangen sollen, sparen Sie sich die Suche: Das sind die TOP Algorithmen und Datenstrukturen.

Sobald Sie sich mit den Grundzügen dieser Programmiersäulen vertraut gemacht haben, werden Sie sie überall sehen. Und je mehr Algorithmen und Datenstrukturen Sie lernen, desto mehr dienen sie als Treibstoff für Ihre Karriere als Software-Ingenieur.

Damit Sie anfangen können, lassen Sie uns zunächst einen tiefen Einblick in Search und Sort / Suchen und Sortieren werfen, zwei Klassen von Algorithmen, ohne die Sie nicht leben können. Dann lassen Sie uns  einen kurzen Überblick über den Rest der Landschaft machen, wozu Bäume, Grafiken, dynamische Programmierung und jede Menge weiteres gehörten.

Suchen

Grob gesagt gibt es zwei Kategorien von Suchalgorithmen, die Sie kennen müssen: lineare und binäre.

Lineare Suche

Die linearen und binären Algorithmen werden als solche bezeichnet, um zu beschreiben, wie lange (zeitliche Komplexität) eine Suche dauert, basierend auf der Größe der Eingabe, die durchsucht wird.

Wenn Sie zum Beispiel bei linearen Suchalgorithmen 100 Elemente suchen, müssen Sie im schlimmsten Fall  jedes Element in der Eingabe prüfen, bevor Sie auf den gewünschten Wert gestoßen sind. Es wird als linear bezeichnet, da die Suchdauer mit der Anzahl der Elemente in der Suche genau korreliert (100 Elemente / Eingabe = 100 Prüfungen / Komplexität).

Kurz gesagt, linear = einfach (der Algorithmus ist nicht schlau). Zum Beispiel: Stellen Sie sich vor, Sie versuchen, Ihren Freund in einer Reihe von Personen zu finden, die in keiner bestimmten Reihenfolge stehen. Sie wissen bereits, wie er aussieht, also müssen Sie einfach nacheinander jede Person einzeln betrachten, bis Sie ihn erkennen oder nicht erkennen. Das ist es. Sie folgen dabei dem linearen Suchalgorithmus.

Binäre Suche

Die binäre Suche erhält ihren Namen, weil das Wort „binär“ „von oder in Bezug auf 2 Dinge“ bedeutet, und der Algorithmus arbeitet, indem er die Eingabe in zwei Teile aufteilt, bis das gesuchte Element gefunden wird. Eine Hälfte enthält den Suchbegriff und die andere Hälfte nicht. Der Vorgang dauert, bis die Stelle, an der die Eingabe aufgeteilt wird, dem gesuchten Element gleich wird. Die binäre Suche ist im Grunde nur ein äußerst disziplinierter Ansatz für den Ausscheidungsprozess. Es ist schneller als die lineare Suche, funktioniert jedoch nur mit geordneten Sequenzen.

Ein Beispiel soll dies klarer machen. Angenommen, Sie versuchen, Ihren Freund (der 5’5 ‚’ groß ist) in einer Reihe von Personen zu finden, die nach Höhe von links nach rechts angeordnet wurden, von kleinstem zu höchsten. Es ist eine wirklich lange Reihe, und Sie haben keine Zeit, von einem zu dem anderen durch die ganze Reihe zu gehen, indem Sie die Höhe aller mit der von Ihrem Freund vergleichen. Was können Sie tun?

Geben Sie die binäre Suche ein. Sie wählen die Person ganz in der Mitte der Linie aus und messen deren Höhe. Die ist  5’7 “ groß. Sie wissen also sofort, dass diese Person neben allen anderen zu Ihrer Rechten nicht Ihr Freund ist. Jetzt, da Sie Ihr Problem halbiert haben, richten Sie Ihre Aufmerksamkeit auf den Rest der Reihe und wählen die mittlere Person erneut aus. Die ist 5’4 ‚ groß‘. Sie können also diese Person und jeden zu Ihrer Linken ausschließen, um das Problem erneut zu halbieren. Und so weiter. Nach nur fünf oder sechs dieser Splits sind Sie in einem Bruchteil der Zeit, bei Ihrem Freund angelangt. Sie haben dabei den binären Suchalgorithmus befolgt.

Sortierung

Die Anordnung von Listen der Elemente, die sonst als Sortierung bezeichnet wird, ist einer der häufigsten Programmieraufgaben, die Sie als Entwickler ausführen werden. Hier betrachten wir zwei der nützlichsten Sortieralgorithmen: MergeSort und QuickSort.

MergeSort

Nehmen wir an, Sie stoßen nicht auf die geordnete  Reihe von Personen im obigen Beispiel, sondern Sie müssen eine geordnete Reihe von Personen aus einer ungeordneten Gruppe erstellen. Sie haben nicht viel Zeit, also entwickeln Sie eine Strategie, um die Dinge zu beschleunigen.

Zuerst haben Sie die Gruppe von Leuten, die alle zusammen sind, in zwei Teile geteilt. Dann haben Sie jede der beiden Gruppen wieder in zwei Gruppen aufgeteilt und so weiter, bis Sie sich ganz mit Einzelpersonen befassen. Sie beginnen dann, die Personen zu paaren, und die Größere der beiden in jedem Paar steht rechts von der anderen. Bald ist jeder in diesen links-rechts angeordneten Paaren organisiert.

Als Nächstes beginnen Sie, die geordneten Paare in geordnete Vierergruppen zusammenzuführen, dann die geordneten Vierergruppen in geordnete Achtergruppen zusammenzuführen; und so weiter. Schließlich stellen Sie fest, dass Sie eine vollständige, nach der Höhe geordnete Reihe von Personen haben, genau wie die, die Sie zuvor gesehen haben. Ohne es zu wissen, sind Sie dem MergeSort-Algorithmus gefolgt.

QuickSort

QuickSort ist ein bisschen zu komplex, um sich leicht mit anderen Menschen ein Bild zu machen, also kommen wir dem Code etwas näher. Um zu beginnen, stellen Sie sich vor, Sie haben eine ungeordnete Liste oder ein Array von acht Zahlen, die Sie anordnen möchten.

4      2      13        6      15        12        7 9

Sie könnten MergeSort verwenden, aber Sie hörten, dass QuickSort im Allgemeinen schneller ist, also entscheiden Sie sich für einen Versuch. Als ersten Schritt wählen Sie in der Liste eine Nummer aus, die als Pivot bezeichnet wird. Die Wahl der richtigen Pivotnummer macht den Unterschied in der Schnelligkeit Ihrer QuickSort-Ausführung und es gibt vorgefertigte Formeln für die Auswahl guter Pivots. Aber für den Moment, lassen Sie es einfach bleiben und nehmen wir einfach die letzte Zahl im Array für unsere Pivotnummer: 9.

4    2 13   6 15 12    7 9

Damit der nächste Schritt leichter zu befolgen ist, erstellen wir ein Trennzeichen am Anfang des Arrays und stellen es mit dem Doppelkreuz-Zeichen dar.

#    4 2    13 6 15    12 7 9

Wenn Sie sich von links nach rechts durch unser Array bewegen, ist es unser Ziel, eine beliebige Zahl kleiner als das Pivot (9) links vom Trennzeichen und eine beliebige Zahl größer als (oder gleich) das Pivot rechts vom Trennzeichen zu setzen. Wir beginnen mit der ersten Zahl in unserem Array: 4. Um sie nach links vom Trennzeichen zu verschieben, verschieben wir das Trennzeichen einfach ein Element nach oben:

4    # 2    13 6 15    12 7 9

Mit der nächsten Zahl machen wir dasselbe: 2.

4    2 #    13 6 15    12 7 9

Dann aber kommen wir zu 13, die größer ist als die Pivotnummer  9 und bereits auf der rechten Seite des Trennzeichens ist. Also lassen wir sie in Ruhe. Als nächstes kommen wir zu 6, die nach links vom Trennzeichen gehen muss. Zuerst tauschen wir sie mit 13, um sie in Position zu bringen:

4    2 #    6 13 15    12 7 9

Dann verschieben wir das Trennzeichen weiter:

4    2 6    # 13 15    12 7 9

Als nächstes ist es 15, die sich bereits rechts vom Trennzeichen befindet, also lassen wir sie in Ruhe. Dann haben wir 12. Gleiches. Aber 7, unsere letzte Zahl vor dem Erreichen des Pivots, benötigt die gleiche Art von Bewegung wie 6. Also tauschen wir 7 gegen 13, um sie in Position zu bringen:

4    2 6    # 7 15    12 13 9

Dann verschieben wir das Trennzeichen erneut, bis es passiert hat:

4    2 6    7 # 15    12 13 9

Schließlich kommen wir zu unserer Pivotnummer: 9. Nach der gleichen Logik, die wir oben haben, tauschen wir 15 gegen 9, um die Pivotnummer dort zu erhalten, wo sie sein muss:

4    2 6    7 # 9    12 13 15

Da alle Zahlen links von 9 jetzt kleiner als 9 sind und alle Zahlen rechts von 9 größer als 9 sind, ist unser erster QuickSort-Zyklus abgeschlossen. Als Nächstes behandeln wir jeden Satz von vier Zahlen auf beiden Seiten des Trennzeichens als neues Array, auf das QuickSort angewendet werden soll. Wir werden Ihnen die Details ersparen, aber in der nächsten Runde erhalten Sie vier Zahlenpaare, auf die Sie unsere letzte QuickSort-Runde problemlos anwenden können. Das Endergebnis ist die folgende geordnete Liste, deren Erstellung weniger Zeit in Anspruch nahm als mit dem einfacheren MergeSort:

2    4 6    7 9 12    13 15

Sortieralgorithmen – Spickzettel

Dies sind die gebräuchlichsten Sortieralgorithmen mit einigen Empfehlungen für den Einsatz. Verinnerlichen Sie diese! Sie werden überall verwendet!

Heap sort: Wenn Sie keine stabile Sortierung benötigen und mehr Wert auf die Worst-Case-Leistung legen als auf die durchschnittliche Leistung. Es ist garantiert, dass es O (N log N) ist und O (1) zusätzlichen Speicherplatz verwendet, was bedeutet, dass der Heap- oder Stack-Speicherplatz bei sehr großen Eingaben nicht unerwartet ausgeht.

Introsort: Dies ist eine schnelle Sortierung, die nach einer bestimmten Rekursionstiefe zu einer Heap-Sortierung wechselt, um den ungünstigsten Fall der schnellen Sortierung O(N²) zu umgehen. Es ist fast immer besser als eine einfache, schnelle Sortierung, da Sie den Durchschnittsfall einer schnellen Sortierung mit garantierter O (N log N) -Leistung erhalten. Wahrscheinlich ist der einzige Grund, eine Heap-Sortierung stattdessen zu verwenden, in Systemen mit stark eingeschränktem Speicher, in denen der Stapelspeicherplatz O (log N) praktisch von Bedeutung ist.

Insertion sort: Wenn N garantiert klein ist, auch als Basisfall für eine schnelle Sortierung oder Zusammenführungssortierung. Obwohl dies O (N²) ist, hat es eine sehr kleine Konstante und ist eine stabile Sorte.

Bubble sort, selection sort: Wenn Sie etwas schnell und schmutzig machen und aus irgendeinem Grund nicht einfach den Sortieralgorithmus der Standardbibliothek verwenden können. Der einzige Vorteil, den diese gegenüber Insertion sort haben, ist die etwas einfachere Implementierung.

Quick sort: Wenn Sie keine stabile Sortierung benötigen und die durchschnittliche Fallleistung / average case performance wichtiger ist als die Leistung im schlimmsten Fall / worst case performance. Eine schnelle Sortierung ist im Durchschnitt O (N log N), im schlechtesten Fall O (N²). Eine gute Implementierung verwendet O(log N)-Zusatzspeicher in Form von Stack-Speicherplatz für die Rekursion.

Merge sort: Wenn Sie eine stabile Sortierung O (N log N) benötigen, handelt es sich hierbei nur um Ihre einzige Option. Der einzige Nachteil ist, dass sie O (N)-Hilfsraum verwendet und eine etwas größere Konstante als eine schnelle Sortierung hat. Es gibt einige In-Place-Merge-Sortierungen, aber AFAIK sind alle entweder nicht stabil oder schlechter als O (N log N). Sogar die O (N log N)-Sorten haben eine so viel größere Konstante als der einfache alte Merge-Sort, dass sie mehr theoretische Kuriositäten haben als nützliche Algorithmen.

Non-comparison sorts: Unter einigen ziemlich begrenzten Bedingungen ist es möglich, die O (N log N) -Sperre zu durchbrechen und in O (N) zu sortieren! Hier sind einige Fälle, in denen sich ein Versuch lohnt:

Counting sort / Zählsortierung: Wenn Sie ganze Zahlen mit einem begrenzten Bereich sortieren.

Radix sort / Radix-Sortierung: Wenn log (N) deutlich größer als K ist, wo K die Anzahl der Radix-Ziffern ist.

Bucket sort / Bucket-Sortierung: Wenn Sie garantieren können, dass Ihre Eingabe ungefähr gleich verteilt ist.

Weitere notwendige Algorithmen und Datenstrukturen

Obwohl Search und Sort zwei der am vertrauenswürdigsten und meist genutzten Wege sind, die uns in die Welt der Algorithmen und Datenstrukturen einführen, ist der Überblick über die Landschaft nicht vollständig, ohne die folgenden Favoriten zu erwähnen:

Bäume

Sie sehen gerade viele Bäume in Ihrer Zeit, da sie eine der häufigsten Datenstrukturen sind. Sie sind auch eine der einfachsten Datenstrukturen für Abbild und Verständnis. Nahezu die gesamte Terminologie, die Bäume umgibt, stammt vom Begriff eines Stammbaums. Abhängig von der Position eines Knotens (d. h. eines Familienmitglieds) relativ zu anderen Knoten in der Baumstruktur wird der Knoten als Elternteil, Kind, Geschwister, Vorfahr, Nachkommen usw. bezeichnet.

Das Speichern von Objekten in Bäumen ermöglicht es uns, Objekte effizienter zu finden, wenn der Baum bestimmte Eigenschaften hat.

Grafiken

Wenn Sie technisch arbeiten wollen, ist ein Baum letztlich nur ein Sonderfall einer Grafik. Daher überrascht es nicht, dass Grafiken überall im täglichen Leben und in der Informatik zu finden sind. Insbesondere das Durchqueren von Grafiken ist eine große Sache, und es gibt zwei Algorithmen, die Sie schnell in den Griff bekommen sollten: Breadth First Search (BFS) und Depth First Search (DFS). Um zu verstehen, was diese beiden wesentlichen Algorithmen beinhalten, stellen Sie sich vor, Sie befinden sich an der Spitze eines Wolkenkratzers, der wie eine Pyramide geformt ist, und Sie müssen das gesamte Gebäude durchsuchen, um Ihren Freund zu finden. Dann stellen Sie fest, dass die Pyramide einer Grafik entspricht, in der jeder Raum ein Knoten ist.

Breadth First Search (BFS)

Wenn Sie die Pyramide Stock für Stock überqueren, von der Spitzte der Pyramide angefangen, werden Sie ungefähr eine Breitensuche nach Ihrem Freund durchführen. Sehen Sie sich die folgende Visualisierung an, um eine bessere Intuition über diesen Typ der Suche und sein Verhalten zu entwickeln.

Depth First Search (DFS)

Anstatt Stockwerk für Stockwerk zu gehen, müssen Sie, wenn Sie mit dem Aufzug fahren und die nächstgelegenen Räume während des Durchquerens der Pyramide in vertikalen Ebenen überprüfen, eine Tiefensuche für Ihren Freund durchführen. Auch hier sollte die unten dargestellte Visualisierung helfen, dies etwas klarer zu machen.

Dynamische Programmierung (DP)

Wenn Sie mit einem enormen, schwergewichtigen Programmierproblem konfrontiert sind, das Sie sich nicht vorstellen können, es selbst zu lösen, kann Ihnen die dynamische Programmierung (DP) helfen. DP hilft Ihnen, das große Problem in kleine Unterprobleme zu verwandeln. Jedes Mal, wenn DP eines der Unterprobleme löst, speichert sie die Ergebnisse und fasst schließlich alle Ergebnisse zusammen, die sie gespeichert hat, um das große Problem zu lösen.

Hashing

In den letzten Jahren hat sich die Quelle , wo wir Daten finden, geändert. Während der primäre Ansatz früher die binäre Suche war, wird sie zunehmend zum Hash-Lookup. Obwohl wir Ihnen hier den Zeit-Komplexitäts-Vergleich ersparen, genügt es zu sagen, dass das Hashing beim Durchsuchen von Listen mit Millionen von Elementen oft viel schneller ist.

String pattern matching / String-Matching-Algorithmus

Wenn Sie von regulären Ausdrücken (alias Regex) gehört haben, haben Sie bereits von String-Matching-Algorithmus gehört. Die Idee hier ist, dass Sie nicht so sehr nach einem Objekt suchen, sondern nach einem Muster, das für viele Objekte gleich ist. Zum Beispiel, Sie suchen in einem Buch nach allen Sätzen, die mit einem Fragezeichen enden: Dies ist ein Job für String-Matching-Algorithmus.

Immer noch mehr…

Hier sind noch ein paar Algorithmen.


Datenstrukturen: Arrays
Verknüpfte Listen
Stacks
Warteschlangen


Algorithmen: Primalitätstest
Schnelle Fourier-Transformation
Binäre Potenzierung
Potenzierung durch Quadrieren

Der Weg zum Softwareerfolg wird durch Algorithmen hingelegt

Alles in allem sollten Sie davon ausgehen, dass Algorithmen und Datenstrukturen den Weg für Sie hinlegen (und vielleicht sogar bezahlen), wenn Sie Software-Ingenieur werden möchten. Für ein solides Fundament möchten Sie möglicherweise mit Search (linear und binär) und Sort (SortMerge und QuickSort) beginnen. Sobald Sie sich mit den Grundzügen dieser Programmiersäulen befasst haben, ist es an der Zeit, alles über Bäume, Grafik (BFS und DFS), dynamische Programmierung und String pattern matching zu lernen. Das eigentliche Ziel besteht jedoch darin, den Algorithmen und Datenstrukturen das Leben und den Atmen zu geben: Sie müssen schrittweise Lösungen für Probleme der realen Welt finden und komplexe Szenarien anhand einfacher Datenstrukturen darstellen. Wenn Sie das beherrschen können, wird die Programmierung sehr einfach für Sie  sein.

Sollten Sie Fragen zu Algorithmen und Datenstrukturen haben, so können Sie sich an das Team von AI-United.de wenden per Mail oder Q&A.

AI-United

2 Replies to “Top-Algorithmen und Datenstrukturen, die Sie wirklich kennen müssen”

Kommentar hinzufügen

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.