Sollte ein kompetenter Programmierer in der Lage sein, seinen eigenen Algorithmus für kürzeste Wege zu entwickeln?

58

Ich leide unter einer Vertrauenskrise in meine Fähigkeiten als Computerprogrammierer.

Gestern habe ich versucht, einen eigenen Algorithmus für den kürzesten Weg für ein Diagramm zu finden, und nach einigen Stunden habe ich einfach das Handtuch geworfen und Dijkstra's Algorithmus gelernt.

Ist das die Art von Dingen, die ein guter Programmierer in ein paar Stunden "neu erfinden" kann oder bin ich unrealistisch?

Na ja, zumindest konnte ich die Blasensorte neu erfinden: D

Newbie Programmer
quelle
7
Jemand, der seit 20 Jahren UI betreibt, wird es wahrscheinlich schwer haben, in kurzer Zeit eine Lösung für ein Problem aus einer anderen Domäne zu finden.
Coder
38
Wenn Sie viel Zeit auf den SE-Sites verbringen, ist das für jeden eine Vertrauenskrise, denke ich! (Nicht, dass das eine schlechte Sache wäre). Glück im Leben ist das perfekte Gleichgewicht zwischen Akzeptanz dessen, was ist, und dem Wunsch, es zu ändern.
TrojanName
2
Ich konnte es nicht neu erfinden, aber ich versuche mich zu erinnern, wie es funktioniert. Stellen
Job
6
@ Brian Tragödie des lokalen Genies. Man kann kaum noch der Beste sein.
Rei Miyasaka
7
ein guter Computer Wissenschaftler sollte aber ein Computer - Programmierer oder Software - Ingenieur nicht unbedingt
Neil McGuigan

Antworten:

118

Ein guter Programmierer sollte erkennen, dass bereits ein großartiger Algorithmus zur Lösung eines Problems geschrieben wurde, und keine Zeit damit verschwenden, Räder neu zu erfinden.

Ich bezweifle, dass Dijkstra in ein paar Stunden den kürzesten Pfad-Algorithmus gefunden hat. Das scheint also ein wirklich hoher Standard zu sein, um festzustellen, ob jemand ein „guter Programmierer“ ist.

GSto
quelle
25
@Nakilon - Programmierer, die vorhandene Lösungen ignorieren, verschwenden nur ihre Zeit, und wenn sie nicht ihre Zeit verschwenden, machen sie eine schlechtere Lösung. Siehe: Jeder, der sein eigenes Passwort-Hashing-Schema erstellt, vergleicht es mit bcrypt.
Setzen Sie Monica
10
@GSto: Laut Wikipedia Dijkstra kam mit dem Algorithmus , der in weniger als eine Stunde: 20 Minuten, Acording zum ersten Hinweis auf wikipedia: en.wikipedia.org/wiki/Dijkstra%27s_algorithm
woliveirajr
9
Es ist ein relativ einfacher Algorithmus, aber Dijkstra war sehr talentiert und in theoretischer Physik und fortgeschrittener Mathematik ausgebildet. Es gibt nichts Schöneres, als ein paar Jahre lang Beweise zu schreiben, um die Fähigkeit zu verbessern, Algorithmen zu entwerfen.
Kevin Cline
19
@woliveirajr - Ich bin sicher, Newton hat die gleiche Zeit gebraucht, um sich mit den Bewegungsgesetzen auseinanderzusetzen. Nachdem ich 20 Jahre lang darüber nachgedacht habe.
Rook
6
@Nakilon - Ja, deshalb schreibt jeder alles in C, weil Sie sonst nur ein Programmierer sind und die Hochsprache eines anderen verwenden. Oh warte, ich meine Montage, sonst benutzt du nur die einfache Sprache einer anderen Person. Oh, warte, ich meine Schalter umlegen, um die Stromkreise zu wechseln, sonst benutzt du nur den Befehlssatz eines anderen. Oder Sie können einfach das verwenden, was bereits vorhanden ist, und daran arbeiten, etwas Neues zu erstellen . Warum Zeit damit verschwenden, den Algorithmus von Dijkstra neu zu erfinden, wenn Sie etwas Neues erfinden können, wie ein Programm, das es verwendet?
Setzen Sie Monica
54

Ist das die Art von Dingen, die ein guter Programmierer in ein paar Stunden "neu erfinden" kann oder bin ich unrealistisch?

Zunächst verwechseln Sie vielleicht die Programmierung mit der theoretischen Informatik. Ein fantastischer Programmierer braucht ein gutes Fundament in der Informatik, aber er muss nicht fantastisch sein. Dijkstra war fantastisch in der Informatik.

Zweitens würde ich erwarten, dass jeder mit einem soliden Verständnis von Graphen nach einigem Überlegen seinen eigenen Graphendurchlauf entwickelt. Aber kein kürzester Weg Algorithmus. Insbesondere der Algorithmus von Dijkstra ist hochentwickelt. Sobald Sie es verstanden haben, ist es verblüffend offensichtlich. Aber die meisten Dinge sind so.

Sie könnten wahrscheinlich eine Art Algorithmus für den kürzesten Weg ableiten, nachdem Sie einige Dinge ausprobiert und die Idee einige Zeit gegeben haben. Aber seien Sie nicht enttäuscht, wenn das Stunden oder sogar ein paar Tage dauert. Das ist völlig in Ordnung und normal.

(Vorsichtsmaßnahme: Nun, Sie sollten in der Lage sein, das Problem in ein paar Stunden zu lösen, aber dies würde selbst bei relativ kleinen Diagrammen keinen funktionierenden Algorithmus ergeben.)

Konrad Rudolph
quelle
56
Keine Sorge, wenn Brute Force nicht funktioniert, nutzen Sie einfach nicht genug davon.
Robbie
2
+1 für die Hervorhebung des Unterschieds zwischen theoretischem CS und Programmierung. Das Programmieren ist eine echte Problemlösung, und das theoretische CS unterstützt das Programmieren. Die theoretische CS ist jedoch in den alltäglichen Programmen der meisten Menschen nicht zu 100% essentiell.
Phil
17

Ist das die Art von Dingen, die ein guter Programmierer in ein paar Stunden "neu erfinden" kann oder bin ich unrealistisch?

Auf jeden Fall unrealistisch. Die Leute "kommen" nicht einfach in wenigen Stunden auf Algorithmen. Es erfordert viel Mühe und Arbeit. So zitieren Sie diesen Blog:

Bentley zitiert Donald Knuth in Programming Pearls: "Während die erste binäre Suche 1946 veröffentlicht wurde, erschien die erste binäre Suche, die für alle Werte von n korrekt funktioniert, erst 1962."

und Bentleys Version war auch problematisch, wenn sie für große Mengen implementiert wurde.

Darüber hinaus weiß ein guter Programmierer, welche Werkzeuge ihm zur Verfügung stehen und wann sie verwendet werden müssen. Sie erhalten keine zusätzlichen Punkte für Originalität oder für eine andere Vorgehensweise - Sie möchten, dass es funktioniert und gut funktioniert.

BlackJack
quelle
1
BlackJack, ich musste mich diesem Forum anschließen, um darauf hinzuweisen, dass Bentley nicht gesagt hat, was Sie behauptet haben, dass er gesagt hat: Knuth hat es gesagt, und Bentley hat ihn zitiert. Als ich Ihren Kommentar las, dachte ich, dass Sie einen guten Punkt gemacht haben, aber ich überprüfe gerne meine Quellen und hatte noch nie von Bentley gehört. Ich habe jedoch von Knuth gehört und kann mich auf das verlassen, was er sagt. Bitte überprüfen Sie Ihre Quellen beim nächsten Mal besser.
Richard
8
@Richard - Der Kommentar lautete "In Programming Pearls, sagt Bentley ..." Knuth war der erste, der das sagte, aber meine Quelle ist Programming Pearls, nicht TAoCP, also schrieb ich, was Bentley schrieb. Ich habe nicht behauptet, dass Bentley der Urheber ist - ich habe nur das zitiert, was in dem Buch gesagt wird. Ein Großteil des Materials in Büchern wurde nicht von den Autoren selbst erfunden, deshalb verstehe ich nicht, warum Sie es so sehen würden.
Blackjack
Indem Sie das Zitat ausschließlich Bentley zuschreiben, werden Sie Knuth nicht gutgeschrieben, und wenn die Aussage von "Bentley" falsch war, haben Sie Bentley in die Lage versetzt, falsche Informationen zu liefern, anstatt sie nur zu verbreiten. Genau genommen hast du nicht gesagt, was Bentley gesagt hat: Wenn du das getan hättest, hättest du gesagt: "Bentley hat gesagt, dass Knuth das gesagt hat ...". Das Zitat wird hier gut verwendet, aber es wird aus dem Kontext herausgenommen, in dem es gesagt wurde.
Richard
3
@ Richard - Das Zitat, das ich aufgelistet habe, stammt direkt aus dem Blog, das direkt aus dem Buch zitiert (im wahrsten Sinne des Wortes, ich denke, es ist Seite 57 der ersten Ausgabe). Wenn Sie so viele Probleme mit der Aussage haben, wenden Sie sich an den Autor des Blogs und lassen Sie ihn dies ändern.
Blackjack
1
@Richard und BlackJack: Sie sind beide richtig, aber die Zuordnung zum ursprünglichen Autor verleiht der Aussage Glaubwürdigkeit und Kontext. Meine Bearbeitung sollte ausreichen.
Steven Evers
9

Es ist sehr unwahrscheinlich, dass Sie eine bessere Lösung finden als die, aus denen Sie wählen können.

Es ist nicht jedermanns Sache, mit einem besseren Algorithmus als dem "besten" (in Ihrem Fall dem kürzesten) herauszukommen. Möglicherweise ist das gar nicht möglich.

Ein guter Programmierer sollte in der Lage sein, die Logik hinter dem Algorithmus zu verstehen und zu verstehen, warum er besser oder schlechter (oder für dieses bestimmte Problem einfach unangemessen) ist als andere Algorithmen, die versuchen, dasselbe Problem zu lösen.

(s) Er sollte auch wissen können, ob dies wirklich der beste Weg ist, um dieses bestimmte Problem zu lösen.

Wie auch immer, wenn Sie üben möchten, können Sie trotzdem versuchen, Ihre persönliche Implementierung eines Algorithmus zu schreiben und ein Problem mit Ihrem Verstand zu lösen. Es ist vielleicht nicht das Beste, aber es ist eine gute Methode zur Problemlösung.

Jose Faeti
quelle
6

Das erinnert mich an etwas, was ich über den Unterschied zwischen "Software Engineering" (was ich als Programmierung bezeichnen würde) und den anderen technischen Disziplinen gelesen habe. Ich denke, es war das ursprüngliche Design Patterns-Buch. Ich bin sicher, dass jemand hier es aus seinem Kopf zitieren kann.

Wie auch immer, der Punkt (obwohl nicht genau auf Algorithmus-Design ausgerichtet) war, dass die technischen Disziplinen kodifiziert sind; Es ist unwahrscheinlich, dass Bauingenieure Zeit damit verbringen, den I-Beam neu zu erfinden, aber Programmierer tun dies die ganze Zeit. Das Problem (und mir ist klar, dass ich nur die Gefühle vieler wiedergebe) ist, dass dieses Verhalten verschwenderisch und fehleranfällig ist und dem Ego mehr dient als der Lösung.

Die Informatik hat mich zum Programmieren geführt, und ich liebe beides. Ich bin jedoch ein viel besserer Programmierer als ein Informatiker. Ich würde Sie niemals beschuldigen, inkompetent zu sein, weil Sie den Dijkstra-Algorithmus an einem Nachmittag nicht neu erfinden konnten. Ich würde Ihre Kompetenz als Programmierer in Frage stellen, wenn Sie ein Problem nicht erkennen könnten, das mit einem Graph-Algorithmus mit kürzestem Pfad gelöst werden könnte.

Trotzdem glaube ich, dass das Nachdenken über Algorithmen und der Versuch, neue zu entwerfen und zu implementieren, (potentiell) Spaß macht und (fast) immer lehrreich ist. Ich versuche nur, meine CS-Zeit sauber von meiner Programmierzeit zu trennen. Für Programmierer ist es besser, unsere (besonders bezahlte) Zeit damit zu verbringen, praktische Probleme zu lösen, als sie zu lösen. Außerdem zerstört die CS-Zeit fast immer mein Selbstvertrauen.

Keith Layne
quelle
Oh die Ironie ... jetzt, wo ich irgendwo etwas kommentieren kann, sollte ich die Antwort löschen, die mir dieses Privileg eingebracht hat? Dafür sollte es ein Abzeichen geben.
Keith Layne
Es gibt jedoch - Diszipliniert , wenn Ihr Ruf neu berechnet wird, sind Sie wieder auf 1
gesunken.
Ja, das ist genau mein Punkt ... Ich würde an diesem Punkt über die Disziplin hinausgehen, IMO. Wenn ich meine Antwort vor dem Löschen in einen Kommentar konvertiert hätte , könnte ich alles haben ... Ich schlage ein neues Abzeichen mit dem Namen UberDisciplined vor, damit Sie bei jeder Löschung wieder zum brandneuen Benutzerstatus zurückkehren. :)
Keith Layne
3

Sie werden nicht die gleichen Dinge bemerken, die alle anderen tun. Ich denke, das ist nur eine Tatsache des Lebens, mit der wir leben müssen. Ein Großteil davon hängt von Ihrem passiven Lernen und den mentalen Modellen ab, die Sie als Ergebnis davon entwickelt haben.

Ich kenne einige sehr intelligente und kompetente Programmierer, denen DeMorgans Gesetz in der Schule beigebracht werden musste, bevor sie es konsequent tun konnten. Ich habe den Dijkstra-Algorithmus zufällig selbst herausgefunden (und ich muss zugeben, dass ich ein bisschen stolz darauf bin), aber es hat sehr lange gedauert, bis ich die Art der Blasen überhaupt verstanden habe.

Noch berühmter ist, dass Einstein, von dem man annehmen würde, dass er ein Experte für Knotentheorie ist, seine eigenen Schnürsenkel erst mit etwa zehn Jahren binden konnte.

Die Chancen stehen gut, dass Sie viele Dinge unwissentlich neu erfunden haben , die viele andere niemals herausgefunden hätten, wenn sie nicht explizit unterrichtet worden wären.

Rei Miyasaka
quelle
3

Ich bitte darum, mich zu unterscheiden, was die meisten Antworten aussagen. Obwohl ich nicht erwarten würde, dass ein Programmierer irgendeines Niveaus in der Lage ist, sich selbst mit Dijkstras Algorithmus auseinanderzusetzen, würde ich auf jeden Fall erwarten, dass er einen (effizienten oder nicht effizienten) Weg findet, um das Problem zu lösen.

Als Nebenkommentar haben Sie beispielsweise gesagt, dass Sie die Blasensortierung selbst durchführen können. Ich weiß, es ist der stinkigste Sortieralgorithmus, aber Sie haben einen Weg gefunden, ein Problem zu lösen, und ich erwarte, dass Programmierer in der Lage sind, einen Weg zu finden, um Probleme zu lösen.

Das Nachforschen und Finden von Lösungen, die von anderen gemacht wurden, funktioniert natürlich auch, aber das Extrem ist ein Typ, der nicht an sich selbst denkt und dessen Programme ein Kompendium der Google-Suche sind.

Ich denke, ich höre mich härter an, als ich eigentlich möchte, aber mein Punkt ist: Ich würde erwarten, dass ein Programmierer kreativ genug ist, um eine Lösung für ein Problem zu finden, selbst wenn die Lösung fehlerhaft oder chaotisch ist.


Um auf Ihren Fall zurückzukommen: Ich denke nicht, dass Sie den Dijkstra-Algorithmus entwickeln müssen, aber wenn Sie die Möglichkeit haben, einen Algorithmus zu schreiben, um mehrere Möglichkeiten auszuprobieren und den kürzesten Weg zu finden, ohne in einer Endlosschleife zu enden, dann hast du meine Zustimmung.

(Übrigens gilt meine Zustimmung in der gleichen Reihenfolge wie ein Gutschein für eine kostenlose Autowäsche.)

Alpha
quelle
3
Ich bin damit einverstanden, dass ein kompetenter Programmierer in der Lage sein sollte, eine Blasensorte oder eine gleichwertige zu entwickeln. Es könnte sogar eine produktive Nutzung der Zeit sein, um es tatsächlich zu implementieren und auszuprobieren, vielleicht nur, um das Problem besser zu verstehen. Aber ich denke, es muss gesagt werden, dass dann kein kompetenter Programmierer weitermachen und es tatsächlich in Produktionscode verwenden würde. Auf diese Weise kehren Ihre Kunden nächstes Jahr zurück und beschweren sich, dass Ihr O (n!) - Algorithmus, sobald er mehr Daten zu verarbeiten hat, doppelt so alt ist wie das Universum ...
Thomas Padron-McCarthy
Wen kümmert es, wenn Sie Algorithmen erfinden können, wenn Sie nicht einmal erkennen können, wann es scheiße ist? Selbstkritik ist für einen Programmierer ebenso wichtig wie Kreativität. Ich würde lieber mit einem Programmierer arbeiten, der schnell zugeben kann, dass seine eigene Lösung zu lange dauert oder wahrscheinlich nicht die beste ist, als mit einem Programmierer, der jedes Rad neu erfinden möchte, weil es sein Ego verletzt, wenn es anders ist.
Rei Miyasaka
Ich stimme in beiden Punkten überein, aber ich denke, wir messen zwei verschiedene Dinge. Eine davon ist die Fähigkeit des Programmierers, Probleme zu lösen (etwas, das ich für wesentlich halte). Andere sind Selbstkritik (ich halte dies für wesentlich, aber nicht für das Programmieren: für das Leben) und die Fähigkeit, Code zu beurteilen (höchst wünschenswert). Ich würde auch sagen, dass Lösungen, die ewig dauern, nicht wirklich Lösungen sind, oder? ;)
Alpha
2

Ja, er / sie sollte.

Es mag das moralische Äquivalent von Bubble Art sein, aber ich denke, ein guter Programmierer sollte in der Lage sein, zumindest etwas zu finden, das funktioniert, wie ineffizient es auch sein mag.

Es erübrigt sich zu erwähnen, dass ein guter Programmierer zunächst prüfen würde, ob es eine Bibliothek gibt, die dies für ihn erledigt, oder welche veröffentlichten Algorithmen dies tun und einfach zu implementieren sind.

Natürlich sind viele Programmieraufgaben viel einfacher und nicht jeder muss in der Lage sein, solche schwierigen Probleme anzugehen. Aber Sie möchten jemanden mit einem solchen Verstand in Ihrem Team haben, da Sie möglicherweise einige komplizierte projektspezifische Probleme haben, bei denen Sie sich nicht auf eine Menge früherer wissenschaftlicher Forschungen verlassen können.

Hans-Peter Störr
quelle
1

Keine Sorge

Als Perl-Programmierer geht es mir darum, das Rad nie wieder neu zu erfinden. Das ist die Aufgabe von CPAN. Wenn es einen einfachen, gut unterstützten Algorithmus oder ein Modul gibt, verwenden wir es. Wenn es kein gutes Modul ist, dann wir erfinden das Rad. Das ist eines der größten Dinge bei Perl.

Also, was ich sage, ist das:

  1. Ich empfehle nicht, das Rad neu zu erfinden, aber wenn Sie es tun ...
  2. Versuche es nicht komplett neu zu erfinden und ...
  3. Mach dir keine Sorgen, wenn du es nicht kannst. Deshalb haben wir eine Programmiergemeinschaft :-).
Dynamisch
quelle
Es geht nicht darum, etwas neu zu erfinden, sondern generell Probleme zu lösen. Wenn Sie nicht versuchen, Dinge selbst zu erfinden, werden Sie sich nie verbessern.
Nils
0

Die Graphentheorie und die Algorithmen, die darauf angewendet werden, sehen auf der Oberfläche einfach aus, sind aber im Allgemeinen weit davon entfernt. Man könnte denken, dass die Bildung von nicht überkreuzenden (planaren) Graphen zum Beispiel auf den ersten Blick einfach ist. Letztes Jahr habe ich mich eingehend mit diesem Problem befasst (Planarität durch Eliminierung von Kuratowski-Teilgraphen). Aus dieser Erfahrung kann ich Ihnen sagen, dass die Leute, die diese Algorithmen schreiben, in der Regel die Zeit ihrer Promotion damit verbringen und manchmal in Teams recherchieren. Und als Forscher ist dies in dieser Zeit ihr einziger Arbeitsschwerpunkt. Es ist nicht sinnvoll zu glauben, dass wir Ingenieure vor Ort dasselbe erwarten können. Wie jemand anderes hier zu Recht sagte, ist es verblüffend offensichtlich, wenn die Lösung vor Ihnen liegt. Das scheint immer so zu sein!

Techniker
quelle
0

Ist das die Art von Dingen, die ein guter Programmierer in ein paar Stunden "neu erfinden" kann oder bin ich unrealistisch?

Ich würde sogar sagen, dass Sie ein schlechter Programmierer sind , wenn Sie in der Lage sind, einen Algorithmus für ein bekanntes Problem wie Shortest Path allein zu erfinden .

Es würde bedeuten, dass Sie eine ganze Geschichte des Problems des kürzesten Pfades ignorieren , indem Sie von einem 1955 veröffentlichten O (| V | ^ 4) -Algorithmus zu dem 1984 veröffentlichten O (E + V log V) -Algorithmus übergehen (das ist Dijkstra's) Algorithmus mit Fibonacci-Bäumen). Es ist fast garantiert, dass Sie schlechter abschneiden als die bereits entwickelten Algorithmen. Schlimmer noch, es besteht eine gute Chance, dass Ihr Algorithmus Lücken oder Fehler aufweist, die ihn falsch machen. Außerdem verbringen Sie mit ziemlicher Sicherheit viel mehr Zeit damit, Ihren Algorithmus zu überdenken, zu implementieren und zu testen, als die Zeit, die erforderlich ist, um einen vorhandenen Algorithmus wiederzuverwenden.

Überlassen Sie den Entwurf von Algorithmen den Algorithmenentwicklern. Programmierer sind Konsumenten ihrer Ergebnisse. Programmierer kombinieren Algorithmen und setzen sie für reale Aufgaben ein. Ein Polizist muss nicht in der Lage sein, das Gesetz neu zu erfinden, um arbeiten zu können oder ein guter Polizist zu sein.

Ich empfehle Ihnen sogar, Implementierungen von Experten zu verwenden, anstatt die Algorithmen selbst für jeden mäßig komplizierten Algorithmus zu implementieren. Es ist wahrscheinlicher, dass es richtig ist. Wahrscheinlich haben sie es schneller als je zuvor geschafft und Sie sparen viel Zeit. Dies gilt insbesondere für kryptografische Algorithmen, da Sie den zusätzlichen Sicherheitsbedarf haben, den normalerweise nur Experten bieten können.

Alex ten Brink
quelle
Kryptografische Algorithmen lassen sich leicht auf ihre Implementierung überprüfen. Bekannte korrekte Testvektoren sind für jeden öffentlich spezifizierten Algorithmus ungefähr ein Dutzend, und sie sind entweder korrekt oder nicht korrekt. (Möglicherweise erzielen Sie mit einer benutzerdefinierten Implementierung eine suboptimale Leistung, aber wenn sie nur korrekt ist, kann daran gearbeitet werden.) Der schwierige Teil der Kryptografie sind Dinge wie die Erzeugung von Zufallszahlen, der ordnungsgemäße Umgang mit Rohschlüsseln und speicherinternen Schlüsselerweiterungstabellen Umgang mit Benutzereingaben (Salting usw.), Speichern von Informationen, um herauszufinden, ob die entschlüsselten Daten gültig sind, und so weiter.
ein Lebenslauf vom
Ich dachte mehr an Timing-Angriffe usw., Dinge, die fast kein Programmierer kennt. Es ist nicht immer ein Thema, aber dennoch ein wichtiges. Das Kombinieren von kryptografischen Primitiven funktioniert normalerweise nicht wie erwartet, dies ist auch ein schwieriger Teil der Sicherheit.
Alex ten Brink
Während das Timing von Angriffen usw. sicherlich ein berechtigtes Anliegen ist (und nicht nur in der Kryptografie), würde ich argumentieren, dass die Anfälligkeit einer Implementierung für solche Angriffe keinen Einfluss auf ihre Richtigkeit hat . Und es gibt viele, viele Möglichkeiten, Kryptografie zu verschleiern, anstatt nur Timing-Angriffe zu ermöglichen. Bruce Schneier leitete früher seine Doghouse- Serie. Ich habe in letzter Zeit nichts darin gesehen, aber es gibt dort viele warnende Beispiele. google.com/search?q=site%3Aschneier.com+%22the+doghouse%22
ein Lebenslauf vom