komplexen Algorithmus implementieren
-
Hi.
Wenn Ihr einen komplexen Algorithmus implementieren wollt, wie geht Ihr da vor? Ich merke, dass es fuer mich dabei sehr wichtig ist, die einzelnen Schritte des Algorithmus vorher explizit als Kommentare in die Codedatei zu schreiben. Bevor ich also den eigentlichen Code schreibe, steht der Algorithmus schon grob skizziert in Kommentaren in der Datei. Wenn ich das nicht mache, dann kann es vorkommen, dass ich irgendwie keinen Anfang beim Implementieren finde. Geht es Euch da aehnlich?
-
Ab wann gilt ein Algorithmus denn als komplex?
Als ich damals einen A* implementiert habe, fand ich das schon ziemlich schwer und musste auch stark systematisch vorgehen und mir erstmal ueberhaupt die Struktur ueberlegen, dann die wichtigsten Funktionen aufstellen und schliesslich mit Schritt fuer Schritt anweisungen implementieren.Ich gehe aber allgemein sehr gerne in (durchnummerierten) Schritten vor, also z.B.
// 1. Read raw data from file ... // 2. parse data ... // 3. calculate possible results ... // 4. choose best solution ...
-
Ab wann findest du einen Algorithmus denn "komplex"? Es kommt schon vor, dass ich für nur 15 Zeilen Code mächtig nachdenken muss (besonders, wenn er Rekursionen benutzt). Ich mache mehr den Frickel-Ansatz:
Sobald ich nur einen Hauch einer Idee habe, schreibe ich es sofort in Code auf (egal ob es falsch ist oder nicht) und lasse mir per Debugger bequem die Konsequenzen präsentieren. Bei jedem Step vergleiche ich dann stets "was macht der Algorithmus" und "was hätte ich gerne" und passe den Algo so an. Auf die Weise taste ich mich dann an die Lösung immer näher ran, bis alles passt. Dann wird getestet.
-
Gregor schrieb:
Wenn ich das nicht mache, dann kann es vorkommen, dass ich irgendwie keinen Anfang beim Implementieren finde. Geht es Euch da aehnlich?
Nein, gar nicht.
-
Ab wann ein Algorithmus komplex ist, ist eine gute Frage. Vermutlich ist das eine subjektive Sache und die Antwort lautet für jeden anders. Ich vermute, dass meine Schwelle da relativ hoch liegt. Wenn ich mich an mein Studium zurückerinnere, dann habe ich dieses Problem, keinen Anfang zu finden, eigentlich fast nie gehabt. Ich hatte es aber sicherlich bei einigen Algorithmen, die ich im Rahmen meiner Diplomarbeit implementiert habe. Zum Beispiel beim Ball Pivoting.
[EDIT: Rest des Beitrags entfernt.]
-
Gregor schrieb:
[EDIT: Rest des Beitrags entfernt.]
Hab ja schon 5 Minuten gebraucht, um die Kurzbeschreibung des Algos zu lesen. Da das alles rein muss, muss man sich erstmal die Notizen in den Code-Editor kopieren. Schwupps, isses das Vorgehen von Posting 1 und 2.
-
volkard schrieb:
Gregor schrieb:
[EDIT: Rest des Beitrags entfernt.]
Hab ja schon 5 Minuten gebraucht, um die Kurzbeschreibung des Algos zu lesen. Da das alles rein muss, muss man sich erstmal die Notizen in den Code-Editor kopieren. Schwupps, isses das Vorgehen von Posting 1 und 2.
Ja, wie gesagt, bei solchen Algorithmen bin ich auf so ein Vorgehen angewiesen, sonst geht es irgendwie nicht. Die Frage ist, ob es schlauere Ansätze gibt, sich einen komplexen Algorithmus vorzuknöpfen. Im Kopf alleine geht es halt ab einem bestimmten Punkt nicht mehr. Wäre es vielleicht besser, sich statt solcher kurzen Notizen kleine Skizzen zu machen? Macht das jemand hier? Ich meine, im Studium werden einem ja durchaus eine ganze Menge Modellierungsansätze nähergebracht.
-
UML-Diagramme, Struktogramme, Programmablaufpläne?
Nee. Wenn überhaupt, dann Pseudocode. Also genau das, was Du machst.
(Stehengelassener Pseudocode ist dann gleichzeitig die beste Kommentierung.
)
-
Ich bin ja noch C++-Anfänger und für mich ist fast jeder Algorithmus noch eine Überlegung wert. Sobald es für mich komplizierter wird, bin ich am Zeichnen was das Zeug hält. Kein UML, sondern es geht mir da mehr darum Zusammenhänge zu visualisieren. Auch schreibe ich mir oft Tabellen auf, wo ich bei jeder Iteration dann mal schwarz auf weiß sehe, wie sich die Zahlen verändern, um vielleicht eine Struktur zu erkennen. Das hilft mir ungemein. Beim implementieren schreibe ich dann auch soviele Kommentare wie möglich auf, wenn es sich um eine neue Sache handelt, die ich noch nicht so gut kenne. Denn schon zwei Wochen später helfen mir die Kommentare viel schneller wieder in das Thema rein zu kommen, als der Code allein.
Etwas Visuelles vor mir zu haben, ersetzt fast jeden Text den ich dazu schreiben könnte. Eigentlich schade, dass man in Quellcode keine wirklichen Zeichnungen unterbringen kann(z.B. mit Latex und die IDE kann das dann rendern bei Bedarf), aber so Ascii-Drawing ist wenigtens ein Kompromiss.
-
ich implementiere das in kleineren schritten und bei jedem schritt gebe ich meine angenommenen (notfalls ausgedachten) parameter ein und pruefe die ausgabe. da ich viel mit graphic arbeite und dort breakpoints oder sogar nur printf oft nicht moeglich sind, gebe ich die dinge als farben aus.
wie sowas ausschaut ist z.b. auf page 47, 49,... in http://blog.selfshadow.com/publications/s2014-shading-course/hoffman/s2014_pbs_physics_math_slides.pdf zu sehen.
ich versuche oft die ausgabe visuel darzustellen, da man viel mehr daten ausgeben kann und das auge meist dennoch sieht wenn in all der menge testdaten etwas falsch herauskommt. wenn etwas falsches herauskommt (z.b. beim oben erwaehnten A*), dann gebe ich mir die einzelschritte als quasi animation aus. manchmal ist das dann wirklich nur ein eingehacktes bild das ich pro durchlauf weiterzeichne und mit einem counter als bildsequenz (z.b. TGAs) abspeichere.
die fehlervisualisierung hilft manchmal auch den fehler einzugrenzen, wenn etwas nur leicht falsch ausschaut sind die gruende anders als wenn es total unerwartete ausgaben gibt. es hilft mir auch zu sehen ob nicht vielleicht meine annahmen falsch waren (da manchmal in papern impliziert wird dass man dinge weiss, z.b. wertebereiche (0.f-1.f vs 0 bis 255) oder datenformate (z.b. linear vs srgb), was ohne visualisierung manchmal garnicht auffaellt).
-
rapso schrieb:
ich versuche oft die ausgabe visuel darzustellen, da man viel mehr daten ausgeben kann und das auge meist dennoch sieht wenn in all der menge testdaten etwas falsch herauskommt. wenn etwas falsches herauskommt (z.b. beim oben erwaehnten A*), dann gebe ich mir die einzelschritte als quasi animation aus. manchmal ist das dann wirklich nur ein eingehacktes bild das ich pro durchlauf weiterzeichne und mit einem counter als bildsequenz (z.b. TGAs) abspeichere.
die fehlervisualisierung hilft manchmal auch den fehler einzugrenzen, wenn etwas nur leicht falsch ausschaut sind die gruende anders als wenn es total unerwartete ausgaben gibt. es hilft mir auch zu sehen ob nicht vielleicht meine annahmen falsch waren (da manchmal in papern impliziert wird dass man dinge weiss, z.b. wertebereiche (0.f-1.f vs 0 bis 255) oder datenformate (z.b. linear vs srgb), was ohne visualisierung manchmal garnicht auffaellt).Bei der Fehlersuche greife ich auch oft auf Visualisierungen zurück, was teilweise nicht so ganz leicht ist, wenn es sich nicht gerade um einen Algorithmus handelt, der etwas mit Grafik zu tun hat. Ob man auf solche Darstellungen zurückgreifen muss, ist glaube ich auch wieder eine Frage der Komplexität des Algorithmus, den man implementiert. Auch die Art der Daten, die man verarbeitet, ist hier relevant. Visualisieren muss man nur Dinge, die man in Textform nicht begreifen kann.
volkard schrieb:
UML-Diagramme, Struktogramme, Programmablaufpläne?
Nee. Wenn überhaupt, dann Pseudocode. Also genau das, was Du machst.
(Stehengelassener Pseudocode ist dann gleichzeitig die beste Kommentierung. )Naja, ich kann mir schon vorstellen, dass es bestimmte Programmkonstrukte gibt, die sich besser grafisch als in Textform modellieren lassen. Zum Beispiel, wenn sich ein Teil eines Programms wie eine Finite State Machine verhalten soll, dann ist es sicherlich sinnvoll, sich das explizit im Vorfeld einmal aufzuzeichnen.
-
Ach, wer erinnert sich nicht mit wehmütiger Freude an die Login-Sequenz aus RFC959!
+---+ USER +---+------------->+---+ | B |---------->| W | 2 ---->| E | +---+ +---+------ | -->+---+ | | | | | 3 | | 4,5 | | | -------------- ----- | | | | | | | | | | | | | | --------- | | 1| | | | V | | | | +---+ PASS +---+ 2 | ------>+---+ | |---------->| W |------------->| S | +---+ +---+ ---------->+---+ | | | | | 3 | |4,5| | | -------------- -------- | | | | | | | | | | | | ----------- | 1,3| | | | V | 2| | | +---+ ACCT +---+-- | ----->+---+ | |---------->| W | 4,5 -------->| F | +---+ +---+------------->+---+
-
Gregor schrieb:
... Ob man auf solche Darstellungen zurückgreifen muss, ist glaube ich auch wieder eine Frage der Komplexität des Algorithmus, den man implementiert. Auch die Art der Daten, die man verarbeitet, ist hier relevant. Visualisieren muss man nur Dinge, die man in Textform nicht begreifen kann.
einfache daten zu visualisieren hilft fehler zu minimieren, weil ein verarbeitungsschrit entfaellt (abstrakte zahlen mit einem wertgefuehl zu fuellen) und bei komplexen daten/algorithmen hilft es die daten ueberhaupt zu verstehen bzw im ganzen umfang aufzunehmen. Mit diesem "Big Data" usw. gibt es viele start ups die einzig darauf abzielen daten verstaendlich zu visualisieren.
der nachteil von sowas ist dass es eventuell ein wenig mehr zeit kostet es zu implementieren (wobei ich das gefuehl habe es spart mir im nachhinein viel zeit) und natuerlich, dass die visualisierung auch mal fehlerhaft sein kann, dann jagt man geister.