Was sind die Gründe, um verschiedene Algorithmen / Datenstrukturen zu lernen, die dem gleichen Zweck dienen?

91

Ich habe mich über diese Frage gewundert, seit ich Student war. Es ist eine allgemeine Frage, aber ich werde sie im Folgenden anhand von Beispielen erläutern.

Ich habe viele Algorithmen gesehen - zum Beispiel für Probleme mit maximalem Durchfluss kenne ich 3 Algorithmen, die das Problem lösen können: Ford-Fulkerson, Edmonds-Karp & Dinic, wobei Dinic die beste Komplexität aufweist.

Für Datenstrukturen - zum Beispiel Heaps - gibt es Binärheaps, Binomialheaps und Fibonacci-Heaps, wobei Fibonacci-Heaps die beste Gesamtkomplexität aufweisen.

Was mich verwirrt, ist: Gibt es Gründe, warum wir sie alle kennen müssen? Warum nicht einfach lernen und sich mit der besten Komplexität vertraut machen?

Ich weiß, dass es das Beste ist, wenn wir sie alle kennen. Ich möchte nur wissen, ob es "zutreffendere" Gründe gibt. Einige Probleme / Algorithmen können nur mit A , nicht aber mit B usw. gelöst werden .

shole
quelle
17
Wie ich immer sage: diese sind (meistens) keine "Besten". Sobald Sie explizit definieren, was Sie mit "besser" meinen, wird die Antwort offensichtlich.
Raphael
2
Dies ist eine gute Frage, aber sie spricht für eine Lücke in Ihrer Ausbildung, die Sie möglicherweise korrigieren möchten. Das ist praktische Erfahrung, wenn Sie diese Algorithmen während Ihrer Ausbildung nicht geschrieben haben, können Sie sie jetzt schreiben. Ich vermute, die Antwort auf diese Frage wäre schnell offensichtlich geworden, als Sie versuchten, eine Verwendung für sie zu finden.
Sam
@Sam Aus meiner Erfahrung dachte ich, dass Vorlesungen oder Lehrbücher informativ sind, viele Algorithmen, die Analyse usw. vorstellen, aber nicht viele praktische Fälle oder Beispielszenarien, die A übertrifft Genre der Algorithmen von A bis Z und einige Hausaufgabenprobleme, aber für mich können sie alle nur von A oder nur von Z usw. gelöst werden, daher die gestellte Frage.
Shole
5
Wenn Sie darauf bestehen, das akademische Interesse außer Acht zu lassen, ist es der beste praktische Grund, weniger als optimale Algorithmen zu lernen, sie als solche zu erkennen und sie zu optimieren, indem Sie sie zu den optimalen umgestalten. Sie können einen Pfeil und Bogen nicht zu einer Waffe aufrüsten, wenn Sie nicht wissen, wofür Pfeil und Bogen überhaupt gut sind.
candied_orange
1
Wir haben tatsächlich eine StackExchange-Site vorgeschlagen, um speziell bei CS-Bildungsfragen wie dieser zu helfen. Kommen Sie und unterstützen Sie uns hier: area51.stackexchange.com/proposals/92460/…
vk2015

Antworten:

121

Irgendwann wartet ein Lehrbuch mit dem Arbeitstitel Datenstrukturen, Algorithmen und Kompromisse auf Sie . Nahezu jeder Algorithmus oder jede Datenstruktur, die Sie wahrscheinlich im Grundstudium lernen, verfügt über einige Funktionen, die es für einige Anwendungen besser machen als für andere.

Nehmen wir als Beispiel das Sortieren, da jeder mit den Standardsortieralgorithmen vertraut ist.

Zunächst einmal ist Komplexität nicht das einzige Problem. In der Praxis spielen konstante Faktoren eine Rolle, weshalb (sagen wir) die schnelle Sortierung in der Regel häufiger verwendet wird als die Heap-Sortierung, obwohl die schnelle Sortierung im schlimmsten Fall eine schreckliche Komplexität aufweist.

O(nLogn)

In anderen Fällen können Ideen aus einem Algorithmus oder einer Datenstruktur auf ein spezielles Problem angewendet werden. Die Blasensortierung scheint auf echter Hardware immer langsamer zu sein als die Einfügungssortierung, aber die Idee, einen Blasendurchlauf durchzuführen, ist manchmal genau das, was Sie brauchen.

Betrachten Sie beispielsweise eine Art 3D-Visualisierung oder ein Videospiel auf einer modernen Grafikkarte, bei der Sie Objekte aus Leistungsgründen in der Reihenfolge von der nächsten zur Kamera bis zur entferntesten zur Kamera zeichnen möchten Wenn Sie die genaue Bestellung nicht erhalten, kümmert sich die Hardware darum. Wenn Sie sich in der 3D-Umgebung bewegen, ändert sich die relative Reihenfolge der Objekte zwischen den Bildern nicht wesentlich. Daher kann es sinnvoll sein, für jedes Bild einen Bubble-Pass durchzuführen. (Die Source-Engine von Valve bewirkt dies für Partikeleffekte.)

Es gibt Persistenz, Parallelität, Cache-Lokalität, Skalierbarkeit auf einem Cluster / einer Cloud und eine Vielzahl anderer möglicher Gründe, warum eine Datenstruktur oder ein Algorithmus besser geeignet sein kann als ein anderer, selbst wenn Sie für die von Ihnen gewünschten Vorgänge dieselbe Komplexität in der Berechnung haben.

Dies bedeutet jedoch nicht, dass Sie sich für alle Fälle eine Reihe von Algorithmen und Datenstrukturen merken sollten. Der größte Teil des Kampfes besteht darin zu erkennen, dass es einen Kompromiss gibt, der ausgenutzt werden muss, und zu wissen, wo man suchen muss, wenn man denkt, dass etwas angemessen ist.

Pseudonym
quelle
7
Tolle Antwort mit tollen Beispielen! Wusste nicht, dass auch Bubble Pass seinen praktischen Nutzen in der realen Welt hat ...
shole
1
@shole Ich habe nicht viel Erfahrung im Spielegeschäft, aber all das ist in unterschiedlichem Maße wichtig. (Die Art von Algorithmen, Datenstrukturen und Mathematik, die Sie für Spiele benötigen, unterscheidet sich wahrscheinlich von denen, die für Datenbanken oder Bioinformatik erforderlich sind.) Wenn ich Sie wäre, würde ich hier anfangen zu schauen: handmadehero. org Vielleicht lohnt es sich auch, auf gamedev.stackexchange.com
Pseudonym
1
Cache-Effizienz ist ein großer Faktor, der stark unterforscht ist (Google "Memory Wall").
Raphael
6
Vorsicht, Quicksort ist im Durchschnitt viel schneller als Heapsort, aber Heapsort ist konsistenter (die Abweichung der Laufzeit ist geringer und der schlimmste Fall ist viel besser). Und Heapsort springt im Array herum, während Quicksorts lineare Scans von links und rechts einen großen Unterschied machen, sobald Cache / Paging ins Spiel kommt.
Vonbrand
1
@shole Für welche Art von Spieleentwicklung interessierst du dich? Es gibt mindestens zwei sehr unterschiedliche Unterfelder, 3D-Grafik und Gameplay (einschließlich KI). Ich habe nur Erfahrung mit Grafiken, aber ich kann sagen, dass Datenstrukturen und Mathematik in Grafiken und in geringerem Maße auch in Algorithmen extrem wichtig sind . Wenn Sie eine Engine verwenden, wird das meiste natürlich erledigt, aber Sie sollten immer noch die grundlegende Mathematik der 3D-Geometrie verstehen.
Gardenhead
51

Abgesehen von der Tatsache, dass es unzählige Kostenfaktoren (Laufzeit, Speichernutzung, Cache-Fehler, Verzweigungsfehler, Implementierungskomplexität, Durchführbarkeit der Überprüfung ...) für unzählige Maschinenmodelle (TM, RAM, PRAM, ...) gibt. Neben Abwägungen zwischen Durchschnitt und Worst-Case gibt es häufig auch funktionelle Unterschiede, die über den Rahmen der Grundlehrbuchspezifikation hinausgehen.

Einige Beispiele:

  • Mergesort ist stabil, Quicksort nicht.
  • Binäre Suchbäume geben Ihnen Iteration in der angegebenen Reihenfolge, Hashtabellen nicht.
  • Bellman-Ford kann mit negativen Flankengewichten umgehen, Dijkstra nicht.

Es sind auch didaktische Überlegungen anzustellen:

  • Wie einfach ist es, eine kompliziertere Lösung vor einer einfacheren zu verstehen? (AVL-Bäume (und ihre Analyse) ohne BSTs; Dinic ohne Ford-Fulkerson; ...)
  • Sehen Sie die gleichen Prinzipien und Muster, wenn Sie nur einer Lösung pro Problem ausgesetzt sind, im Vergleich zu vielen Lösungen?
  • Bietet die Exposition gegenüber nur einer Lösung pro Problem ausreichend Training (in Richtung Beherrschung)?
  • Sollten Sie wissen, in welcher Breite Lösungen gefunden wurden (um zu verhindern, dass Sie das Rad immer wieder neu erfinden¹)?
  • Wenn Sie nur einer Lösung pro Problem ausgesetzt sind, werden Sie dann andere Lösungen verstehen, die Sie in der Natur finden (z. B. in einer realen Programmbibliothek)?

  1. Dies ist etwas , das wir einen sehen viele von Programmierer - Typen , die eine reiche CS Toolbox nicht zur Verfügung stehen.
Raphael
quelle
4
+1 für das Einbinden von didaktischen Begründungen! In Verbindung mit einigen der Begründungen (insbesondere der zweiten und dritten) vermittelt das Entwickeln und Optimieren von Algorithmen und Datenstrukturen Entwicklungs- und Optimierungstechniken und ein Verständnis für Kompromisse (Lernen nicht nur "was", sondern auch "wie" und "warum"). ).
Paul A. Clayton
2
Eine weitere Überlegung ist, dass die Analyse der verschiedenen Alternativen Beispiele für nützliche Tools zur Analyse neuer Algorithmen für möglicherweise ungewöhnliche Einstellungen bietet.
Vonbrand
1
Guter Punkt, @vonbrand. Die Analyse der amortisierten Komplexität wurde erfunden, um das Verhalten von Spreizbäumen zu verstehen, aber Spreizbäume werden in der Praxis selten verwendet. Na ja, Bäume nicht so spreizen, wie sie veröffentlicht wurden. Der Windows NT-Kernel verwendet bekanntermaßen Splay-Bäume, um virtuelle Speicherzuordnungen zu implementieren, ordnet diese jedoch nicht bei jeder Suche neu an.
Pseudonym
1
@vonbrand Ja. Ich würde verstehen, wie sich jemand, der hauptsächlich an der Toolbox-Dimension einer Algorithmus-Klasse interessiert ist, über diesen Grund lustig macht.
Raphael
7

In der realen Welt arbeiten Sie wahrscheinlich irgendwann an Software, die von einem Team anderer Leute geschrieben wurde. Einige dieser Software wurde geschrieben, bevor Sie geboren wurden!

Um die verwendeten Algorithmen / Datenstrukturen zu verstehen, ist es sehr hilfreich, eine große Anzahl von Algorithmen / Datenstrukturen zu kennen, einschließlich Optionen, die nicht mehr als „Stand der Technik“ gelten.

Sie müssen auch an Algorithmen arbeiten, die nicht dem Standard entsprechen und nur in der Anwendung verwendet werden, an der Sie arbeiten. Wenn Sie diese Algorithmen verbessern müssen, werden Sie feststellen, dass Ihr Gehirn mit nützlichen Methoden zur Verbesserung von Algorithmen gefüllt ist, da Sie untersucht haben, wie andere Menschen Algorithmen verbessert haben.

Dies unterscheidet jemanden, der Informatik studiert hat, von jemandem, der gerade das Programmieren gelernt hat. In den meisten Arbeitsplätzen habe ich gearbeitet in hat es Zeit , als studierte Informatik mit mir ein Problem lösen könnte , dass ein „von Büchern gelernt“ Programmierer konnte nicht, aber 95% der Zeit fand ich , dass studierte Informatik mit gab mir keinen Vorteil über andere erfahrene Programmierer .

Ian Ringrose
quelle
es sei denn, 95% der Dinge, die Sie zu lösen versuchen, beziehen sich auf maschinelles Lernen. Ich kann nicht sehen, wie normale Programmierer überhaupt die richtige Chance haben können, eines der Probleme zu versuchen, mit denen echte ML-Probleme konfrontiert sind.
Pinocchio
3
Ziel: einen Job mit einer besseren Quote als 5% bekommen.
Raphael
Denken Sie daran, dass das Studium von CS eine großartige Möglichkeit war, Wissen über Algorithmen und Datenstrukturen zu sammeln. Codieren ist die beste Beschäftigung - für Codierer.
Greybeard
5

Viele Leute haben zu Recht erwähnt, dass es oft keinen besten Algorithmus gibt - es hängt von der Situation ab.

Es besteht auch die Möglichkeit, dass Sie eines Tages auf eine ungewohnte Situation stoßen. Je mehr Algorithmen Sie kennen, desto größer ist die Wahrscheinlichkeit, dass Sie einen kennen, der beinahe eine Lösung darstellt, die Sie als Basis verwenden können.

Kerl den Pub runter
quelle
5
Diese Antwort wiederholt nur Punkte von älteren.
Raphael
1

Viele großartige Antworten, nur etwas, von dem ich denke, dass es fehlt, obwohl Raffaels Antwort dies etwas erwähnt.

Die einfache Implementierung muss ebenfalls berücksichtigt werden.
Bei Sortieralgorithmen ist dies normalerweise kein Problem, da auf den meisten Plattformen / Sprachen bereits ein Algorithmus implementiert ist (und häufig besser ist als das, was Sie tun könnten), aber ungewöhnlichere Algorithmen sind möglicherweise nicht verfügbar.
Abhängig von Ihrem Problem benötigen Sie möglicherweise nicht den absolut besten Algorithmus, wenn die Implementierungszeit 1 Tag gegenüber 2 Wochen beträgt.

Leherenn
quelle