Ihr Lieblingsalgorithmus und die Lektion, die er Ihnen beigebracht hat [geschlossen]

StackOverflow https://stackoverflow.com/questions/26301

  •  09-06-2019
  •  | 
  •  

Frage

Welcher Algorithmus hat Ihnen am meisten etwas über das Programmieren oder eine bestimmte Sprachfunktion beigebracht?

Wir alle haben diese Momente erlebt, in denen wir plötzlich wussten, dass wir eine wichtige Lektion für die Zukunft gelernt haben, die darauf beruhte, endlich einen Algorithmus zu verstehen, der von einem Programmierer geschrieben wurde, der ein paar Stufen weiter oben auf der Evolutionsleiter stand.Wessen Ideen und Code hatten den magischen Touch auf Sie?

War es hilfreich?

Lösung

„Iterieren ist menschlich, rekursieren göttlich“ – zitiert 1989 am College.

P.S.Gepostet von Woodgnome, während er auf die Einladung zum Beitritt wartet

Andere Tipps

Allgemeine Algorithmen:

  • Quicksort (und seine Analyse der durchschnittlichen Komplexität) zeigt, dass die Randomisierung Ihrer Eingabe eine gute Sache sein kann!;
  • ausgeglichene Bäume (AVL-Bäume zum Beispiel), eine gute Möglichkeit, die Such-/Einfügungskosten auszugleichen;
  • Dijkstra Und Ford-Fulkerson Algorithmen für Graphen (ich mag die Tatsache, dass der zweite viele Anwendungen hat);
  • die LZ*-Familie von Komprimierungsalgorithmen (LZW zum Beispiel) klang die Datenkomprimierung für mich irgendwie magisch, bis ich sie entdeckte (vor langer Zeit :) );
  • Die FFT, allgegenwärtig (in so vielen anderen Algorithmen wiederverwendet);
  • Die Simplex Algorithmus, ebenfalls allgegenwärtig.

Numerisch bezogen:

  • Euklids Algorithmus zur Berechnung des ggT zweier Ganzzahlen:einer der ersten Algorithmen, einfach und elegant, leistungsstark, mit vielen Verallgemeinerungen;
  • schnelle Multiplikation ganzer Zahlen (Cooley-Tukey Zum Beispiel);
  • Newton-Iterationen zum Invertieren/Finden einer Wurzel, ein sehr leistungsfähiger Meta-Algorithmus.

Bezogen auf die Zahlentheorie:

  • Hauptversammlung-verwandte Algorithmen (Beispiele):führt zu sehr einfachen und eleganten Algorithmen zur Berechnung von Pi (und vielem mehr!), obwohl die Theorie ziemlich tiefgreifend ist (Gauss führte daraus elliptische Funktionen und Modulformen ein, man kann also sagen, dass daraus die algebraische Geometrie entstand...);
  • Die Zahlenfeldsieb (für ganzzahlige Faktorisierung): sehr kompliziertes, aber durchaus schönes theoretisches Ergebnis (das gilt auch für die AKS Algorithmus, der bewies, dass PRIMES in P ist).

Es hat mir auch Spaß gemacht, Quantencomputing zu studieren (Shor Und Deutsch-Josza Algorithmen zum Beispiel):Dadurch lernen Sie, über den Tellerrand hinaus zu denken.

Wie Sie sehen, bin ich etwas voreingenommen gegenüber mathematisch orientierten Algorithmen :)

Floyd-Warshall-Algorithmus für alle Paare kürzester Wege

procedure FloydWarshall ()
   for k := 1 to n
     for i := 1 to n
        for j := 1 to n
          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

Deshalb ist es cool:Wenn Sie in Ihrem Graphentheoriekurs zum ersten Mal etwas über das Problem des kürzesten Weges lernen, beginnen Sie wahrscheinlich mit dem Dijkstra-Algorithmus, der es löst einzel-Quelle kürzester Weg.Am Anfang ist es ziemlich kompliziert, aber dann kommt man darüber hinweg und hat es vollständig verstanden.

Dann sagt der Lehrer: „Jetzt wollen wir das gleiche Problem lösen, aber für.“ ALLE Quellen".Du denkst dir: „Oh Gott, das wird ein viel schwierigeres Problem!“ Es wird mindestens N-mal komplizierter sein als Dijkstras Algorithmus!!!".

Dann gibt Ihnen der Lehrer Floyd-Warshall.Und dein Verstand explodiert.Dann beginnt einem die Tränen in den Augen, wie wunderbar einfach der Algorithmus ist.Es ist nur eine dreifach verschachtelte Schleife.Es verwendet nur ein einfaches Array für seine Datenstruktur.

Am aufschlussreichsten für mich ist die folgende Erkenntnis:Angenommen, Sie haben eine Lösung für Problem A.Dann haben Sie ein größeres „Superproblem“ B, das Problem A enthält.Die Lösung für Problem B kann tatsächlich einfacher sein als die Lösung für Problem A.

Schnelle Sorte.Es hat mir gezeigt, dass Rekursion mächtig und nützlich sein kann.

Das hört sich vielleicht trivial an, aber für mich war es damals eine Offenbarung.Ich war in meinem allerersten Programmierkurs (VB6) und der Professor hatte uns gerade etwas über Zufallszahlen beigebracht und er gab die folgenden Anweisungen:„Erstellen Sie einen virtuellen Lotterieautomaten.Stellen Sie sich eine Glaskugel voller 100 Tischtennisbälle vor, die mit 0 bis 99 markiert sind.Wählen Sie sie nach dem Zufallsprinzip aus und zeigen Sie ihre Anzahl an, bis alle ausgewählt wurden, keine Duplikate.“

Alle anderen haben ihr Programm so geschrieben:Wählen Sie einen Ball aus, tragen Sie seine Nummer in eine „bereits ausgewählte Liste“ ein und wählen Sie dann einen anderen Ball aus.Überprüfen Sie, ob er bereits ausgewählt ist. Wenn ja, wählen Sie einen anderen Ball aus. Wenn nicht, tragen Sie seine Nummer in die Liste „bereits ausgewählt“ usw. ein.

Am Ende führten sie natürlich Hunderte von Vergleichen durch, um die wenigen Bälle zu finden, die noch nicht ausgewählt worden waren.Es war, als würde man die Kugeln nach der Auswahl wieder in das Glas werfen.Meine Offenbarung bestand darin, Bälle nach dem Picken wegzuwerfen.

Ich weiß, das klingt verblüffend offensichtlich, aber das war der Moment, in dem in meinem Kopf der „Programmierschalter“ umgelegt wurde.Dies war der Moment, in dem das Programmieren vom Versuch, eine fremde Fremdsprache zu lernen, zum Versuch überging, ein unterhaltsames Rätsel zu lösen.Und als ich den mentalen Zusammenhang zwischen Programmieren und Spaß erst einmal hergestellt hatte, gab es für mich wirklich kein Halten mehr.

Die Huffman-Kodierung würde mir gehören. Ich hatte ursprünglich meine eigene dumme Version erstellt, indem ich die Anzahl der Bits zum Kodieren von Text von 8 auf weniger reduziert hatte, hatte aber nicht über eine variable Anzahl von Bits abhängig von der Frequenz nachgedacht.Dann fand ich die Huffman-Codierung, die in einem Artikel in einer Zeitschrift beschrieben wurde, und sie eröffnete viele neue Möglichkeiten.

Strichzeichnungsalgorithmus von Bresenham hat mein Interesse für Echtzeit-Grafik-Rendering geweckt.Dies kann verwendet werden, um gefüllte Polygone wie Dreiecke für Dinge wie das Rendern von 3D-Modellen zu rendern.

Rekursives Abstiegs-Parsing - Ich erinnere mich, dass ich sehr beeindruckt war, wie ein so einfacher Code etwas so scheinbar Komplexes bewirken konnte.

Quicksort in Haskell:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Obwohl ich Haskell damals nicht schreiben konnte, verstand ich diesen Code und damit auch die Rekursion und den Quicksort-Algorithmus.Es hat einfach Klick gemacht und da war es...

Der iterative Algorithmus für Fibonacci, weil er für mich die Tatsache auf den Punkt gebracht hat, dass der eleganteste Code (in diesem Fall die rekursive Version) nicht unbedingt der effizienteste ist.

Zur Erläuterung: Der Ansatz „fib(10) = fib(9) + fib(8)“ bedeutet, dass fib(9) zu fib(8) + fib(7) ausgewertet wird.Die Auswertung von fib(8) (und damit fib7, fib6) wird also alle zweimal ausgewertet.

Die iterative Methode (curr = prev1 + prev2 in einer Forloop) verzweigt nicht auf diese Weise und benötigt auch nicht so viel Speicher, da es nur drei transiente Variablen anstelle von n Frames im Rekursionsstapel gibt.

Ich strebe beim Programmieren eher nach einfachem, elegantem Code, aber dieser Algorithmus hat mir klar gemacht, dass dies nicht das A und O für das Schreiben guter Software ist und dass die Endbenutzer es letztendlich nicht tun. Es ist mir egal, wie Ihr Code aussieht.

Aus irgendeinem Grund gefällt mir das Schwartzsche Transformation

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
                @unsorted;

Wo foo($) stellt einen rechenintensiven Ausdruck dar, der $ benötigt (jedes Element der Liste nacheinander) und erzeugt den entsprechenden Wert, der seinerseits verglichen werden soll.

Minimax Ich habe gelernt, dass Schachprogramme nicht intelligent sind, sie können einfach mehr Züge vorausdenken als Sie.

Ich weiß nicht, ob es sich hier um einen Algorithmus handelt oder nur um einen klassischen Hack.In jedem Fall hat es mir geholfen, über den Tellerrand zu schauen.

Tauschen Sie 2 ganze Zahlen aus, ohne eine Zwischenvariable zu verwenden (in C++)

void InPlaceSwap (int& a, int &b) {
     a ^= b;
     b ^= a;
     a ^= b;
}

Schnelle Sorte:Bis ich aufs College kam, hatte ich nie in Frage gestellt, ob die Brute-Force-Blasensortierung die effizienteste Sortiermethode sei.Es schien einfach intuitiv offensichtlich zu sein.Aber als ich nicht offensichtlichen Lösungen wie Quicksort ausgesetzt war, habe ich gelernt, über die offensichtlichen Lösungen hinauszuschauen, um zu sehen, ob etwas Besseres verfügbar ist.

Für mich ist es der Weak-Heapsort-Algorithmus, weil er (1) zeigt, wie sehr eine klug gewählte Datenstruktur (und die darauf arbeitenden Algorithmen) die Leistung beeinflussen kann und (2) dass sich auch in Altbekanntem Faszinierendes entdecken lässt Dinge.(Weak-Heapsort ist die beste Variante aller Heap-Sortierungen bewiesen acht Jahre später.)

Das ist langsam :)

Durch das Verstehen habe ich viel über C und Computer im Allgemeinen gelernt Duffs-Gerät Und XOR-Swaps

BEARBEITEN:

@Jason Z, das ist mein XOR-Tausch :) Cool, nicht wahr?

Aus irgendeinem Grund ist mir Bubble Sort immer aufgefallen.Nicht weil es elegant oder gut ist, sondern nur weil es einen albernen Namen hatte/hat, nehme ich an.

Ich habe keine Favorit – es gibt so viele schöne zur Auswahl – aber eines, das ich immer faszinierend fand, ist das Bailey-Borwein-Plouffe-Formel (BBP)., mit dem Sie eine beliebige Ziffer von Pi berechnen können, ohne die vorhergehenden Ziffern zu kennen.

RSA hat mich in die Welt der modularen Arithmetik eingeführt, die man nutzen kann lösen A überraschend Nummer von interessant Probleme!

Hat mir nicht viel beigebracht, aber das Johnson-Trotter-Algorithmus Es haut mich immer wieder um.

Binäre Entscheidungsdiagramme, Obwohl formal kein Algorithmus, sondern eine Datenstruktur, führen sie zu eleganten und minimalen Lösungen für verschiedene Arten von (booleschen) Logikproblemen.Sie wurden erfunden und entwickelt, um die Anzahl der Gates beim Chipdesign zu minimieren, und können als eine der Grundlagen der Siliziumrevolution angesehen werden.Die resultierenden Algorithmen sind erstaunlich einfach.

Was sie mir beigebracht haben:

  • eine kompakte Darstellung von beliebig Problem ist wichtig;klein ist schön
  • Um dies zu erreichen, kann ein kleiner Satz rekursiv angewendeter Einschränkungen/Reduktionen verwendet werden
  • Bei Problemen mit Symmetrien sollte zunächst die Transformation in eine kanonische Form in Betracht gezogen werden
  • Nicht jede Literatur wird gelesen.Knuth erfuhr von BDDs mehrere Jahre nach ihrer Erfindung/Einführung.(und verbrachte fast ein Jahr damit, sie zu untersuchen)

Für mich der einfache Tausch bei Kelly & Pohl’s Ein Buch über C Call-by-Reference zu demonstrieren, hat mich aus dem Konzept gebracht, als ich es zum ersten Mal sah.Als ich mir das ansah, rasteten die Zeiger ein.Wörtlich...

void swap(int *p, int *q)
{
   int temp;

   temp = *p;
   *p = *q;
   *q = temp;
}

Der Algorithmus der Türme von Hanoi ist einer der schönsten Algorithmen.Es zeigt, wie Sie mit der Rekursion ein Problem viel eleganter lösen können als mit der iterativen Methode.

Alternativ veranschaulichen der Rekursionsalgorithmus für Fibonacci-Reihen und die Berechnung von Potenzen einer Zahl die umgekehrte Situation, in der ein rekursiver Algorithmus zum Zwecke der Rekursion verwendet wird, anstatt einen guten Wert zu liefern.

Der iterative Algorithmus für Fibonacci, weil er für mich die Tatsache auf den Punkt gebracht hat, dass der eleganteste Code (in diesem Fall die rekursive Version) nicht unbedingt der effizienteste ist.

Die iterative Methode (curr = prev1 + prev2 in einer Forloop) verzweigt nicht auf diese Weise und benötigt auch nicht so viel Speicher, da es nur drei transiente Variablen anstelle von n Frames im Rekursionsstapel gibt.

Sie wissen, dass Fibonacci eine geschlossene Lösung hat, die eine direkte Berechnung des Ergebnisses in einer festen Anzahl von Schritten ermöglicht, oder?Nämlich (phiN - (1 - Phi)N) / sqrt(5).Es kommt mir immer etwas bemerkenswert vor, dass dies eine Ganzzahl ergeben sollte, aber das ist der Fall.

Phi ist natürlich der Goldene Schnitt;(1 + sqrt(5)) / 2.

Ein Algorithmus, der eine Liste von Primzahlen generiert, indem er jede Zahl mit der aktuellen Liste von Primzahlen vergleicht, sie hinzufügt, wenn sie nicht gefunden wird, und am Ende die Liste der Primzahlen zurückgibt.In mehrfacher Hinsicht umwerfend, nicht zuletzt wegen der Idee, die teilweise abgeschlossene Ausgabe als primäres Suchkriterium zu verwenden.

Das Speichern von zwei Zeigern in einem einzigen Wort für eine doppelt verkettete Liste hat mir die Lektion erteilt, dass man in C tatsächlich sehr schlechte Dinge tun kann (womit ein konservativer GC große Probleme haben wird).

Am meisten stolz war ich auf eine Lösung, als ich etwas geschrieben habe, das dem DisplayTag-Paket sehr ähnlich ist.Es hat mir viel über Code-Design, Wartbarkeit und Wiederverwendung beigebracht.Ich habe es lange vor DisplayTag geschrieben und es war in einer NDA-Vereinbarung verankert, sodass ich es nicht als Open Source veröffentlichen konnte, aber ich kann in Vorstellungsgesprächen immer noch überschwänglich darüber sprechen.

Karte verkleinern.Zwei einfache Konzepte, die zusammenpassen, um die Parallelisierung einer Vielzahl von Datenverarbeitungsaufgaben zu erleichtern.

Oh...und es ist nur die Grundlage der massiv-parallelen Indizierung:

http://labs.google.com/papers/mapreduce.html

Nicht mein Favorit, aber der Miller-Rabin-Algorithmus Denn das Testen der Primalität hat mir gezeigt, dass es fast immer gut genug ist, fast immer Recht zu haben.(d. h.Misstrauen Sie einem probabilistischen Algorithmus nicht, nur weil die Wahrscheinlichkeit besteht, dass er falsch ist.)

@Krishna Kumar

Die bitweise Lösung macht noch mehr Spaß als die rekursive Lösung.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top