Euer schwierigster Algorithmus?
-
- Ein Korrelationskoeffizientenberechnungsalgorithmus (o0 - Wort ?) für Pixelmatrizen. Das klingt jetzt furchtbar kompliziert, ists aber gar net.
(Sprich passt Bild zu Bild)
- Meine dritte Selfmade Verschlüsselung, ich behaupte nicht, dass sie sehr sicher oder effizient ist, aber zu der Zeit sehr kompli gemacht war
- Eine Taschenrechner, der ganze Therme interpretieren / ausrechnen kann.
- Eine automatische Berechnung von Schlachtausgängen. (Strategiespiel)Nicht umbeding ein Algo, aber auch kompliziert:
- Eine Oberfläche, die komplett zur Laufzeit geladen wird (noch nicht fertig)
- Eine Entwicklungsumgebung um Kaskadierende Stylesheets und Webseiteninhalte zu modifizieren (An einer speziellen Seite)Ich programmier erst seit ≈ 2 Jahren und kann noch viel lernen.
-
Ich sehe das ähnlich wie rapso, nicht nur das "absolut Schwierigste" ist relevant. Zudem, wie misst du Schwierigkeit? Ich verstehe darunter vor allem folgende Faktoren:
- Totaler Zeitaufwand
- Anzahl und Hartnäckigkeit von Bugs
- Wie viele Unterbrüche notwendig sind, um sich das Problem zu veranschaulichen und darüber nachzudenken
Und diese Punkte bringen auch nur was, wenn man sie an der resultierenden Funktionalität misst. Wenn etwas nur einen kleinen Teil eines Projektes ausmacht, aber den grössten Aufwand und die meisten Probleme mit sich bringt, würde ich es viel eher als schwierig bezeichnen als ein grosses Projekt, dessen Umsetzung einfach nur lange dauert.
Beispiele, die mich vor allem wegen vieler Bugs und langer Implementierungszeit etwas herausgefordert haben, sind z.B. eine Kollisionsabfrage in einem 2D-Jump'n'Run oder eine Delaunay-Triangulation. In letzter Zeit habe ich zudem etwas Mühe damit, Komponenten einer Bibliothek sauber und intuitiv zu designen. Wobei ich da häufig das Gefühl habe, mir zu viele Gedanken zu machen, und daher teilweise kaum vorankomme.
-
Nexus schrieb:
oder eine Delaunay-Triangulation
Das glaube ich sofort.
2D oder 3D?
-
Gregor schrieb:
Das glaube ich sofort.
2D oder 3D?Nur 2D, aber constrained. Das Problem war vor allem, dass ich damals noch nie einen "klassischen" Algorithmus in dieser Grössenordnung umgesetzt hatte.
Hast du demnach auch schon was Ähnliches implementiert?
-
Nexus schrieb:
Gregor schrieb:
Das glaube ich sofort.
2D oder 3D?Nur 2D, aber constrained. Das Problem war vor allem, dass ich damals noch nie einen "klassischen" Algorithmus in dieser Grössenordnung umgesetzt hatte.
Hast du demnach auch schon was Ähnliches implementiert?
Ich habe etwas weiter oben in diesem Thread schon geschrieben, dass der Ball Pivoting Algorithmus eine große Herausforderung für mich war.
-
Ah sorry, habe wohl zu wenig genau geschaut. Aber ich stimme dir zu, die Vorstellungskraft ist manchmal ein Limit. Bei mir ging es gerade noch... Man kann zwar immer versuchen, möglichst modular zu arbeiten und sich Notizen auf Papier zu machen, aber je nachdem nützt das auch nur begrenzt, weil die einzelnen Teile zu fest miteinander verdrahtet sind.
-
Gradientenberechnung für ein rekurrentes Netzwerk im Batchmodus. War echt fricklig das aus den Formeln richtig schnell zu implementieren...
-
Bei Algorithmen, die auf "komplexen Daten" arbeiten, kann das Debuggen auch sehr problematisch sein. Vor allem dann, wenn man keine kleinen Mini-Testfälle konstruieren kann. Dann kann es sinnvoll sein, einiges an Aufwand zu betreiben, um die Daten nach einem bestimmten Schritt des Algorithmus zu visualisieren. Ich habe das in der näheren Vergangenheit durchaus recht häufig gemacht. Der Ball Pivoting Algorithmus war diesbezüglich der Anfang. Dort habe ich debuggt, indem ich bestimmte Schritte des Algorithmus mit Gnuplot visualisiert habe. Sonst hätte ich nicht feststellen können, was da eigentlich schief läuft. Ich hätte nur feststellen können, dass es irgendwie nicht funktioniert.
-
Kürzlich habe ich einen Renderer für Indoor-Szenen in OpenGL geschrieben und fand das teilweise recht anspruchsvoll.
Die Geometrie wird in einem Octree verwaltet und klassisches Frustum-Culling schneidet viel nicht sichtbare Würfel weg. Ich wollte es aber noch mit Occlusion-Culling (Occlusion-Queries) kombinieren und das hat ein paar Hirnzellen gekostet bis es mit der Octree-Hierarchie, ohne Darstellungsfehler und mit möglichst geringen Wartezeiten auf die Query-Ergebnisse funktioniert hat.Ich finde OpenGL bockschwer zu debuggen.
Nützlich sind weitere Viewports wie z.B. hier: http://img94.imageshack.us/i/culling2.jpg
So ist schön in Echtzeit zu sehen wie das Culling arbeitet.War nur ein Beispiel. Eigentlich gibt es in jedem Bereich Herausforderungen. Vor allem wenn es um Hardwareansteuerung geht wird es auch schnell anspruchsvoll
-
Wirklich schwierige Algorithmen hatte ich in letzter Zeit eigentlich nicht zu bearbeten (zumindest nicht seitdem ich von der Uni runter bin :)). In der Praxis geht es bei mir eher um "kleine" Probleme und wie sie im Rahmen eines größeren bestehenden Systems umgesetzt und integriert werden.
-
Nexus schrieb:
In letzter Zeit habe ich zudem etwas Mühe damit, Komponenten einer Bibliothek sauber und intuitiv zu designen. Wobei ich da häufig das Gefühl habe, mir zu viele Gedanken zu machen, und daher teilweise kaum vorankomme.
Das Problem habe ich auch oft. Es war zwar nach dem schwierigsten Algorithmus gefragt, aber richtig schwierig ist doch, z.B. Schnittstellen zu designen.
Beim Algorithmus ist ja meistens klar, was am Ende raus kommen soll. Ob ein Schnittstelle-Entwurf gut oder schlecht ist, stellst sich womöglich erst nach der 5.Version raus. Die Fähigkeit, in die Zukunft zu schauen, wäre hier von großem Nutzen.Für mich war es schwierig einen Leader-Follower wirklich mal komplett zu implementieren. Schwierig war für mich auch dieser Parser - als ich die Antwort geschrieben hatte, hatte ich vielleicht nur eine gute Stunde investiert. Dem ging aber eine "jahrelange" Suche nach der einfachen Lösung voraus. Das Problem poppte immer wieder hoch, und mir fiel lange dazu nichts ein, was ich gut gefunden hätte. Und weil es nur reines Interesse an der Sache war, hatte ich ich es immer wieder bei Seite gelegt. Den Durchbruch brachte erst dieser Artikel über Recursive Descent Parser.
Also schwierig ist alles, was man nicht kann bzw. kennt, oder von dem man nicht weiß, wie es am Ende aussehen soll.
Gruß
Werner
-
Ehrlich gesagt, das erste "Hello World".
Es gab damals keine Foren und niemanden den ich hätte fragen können.
Für mich ein Sprung ist ganz kalte Wasser und für meinen ersten PC die
Chance aus dem Fenster zu fliegen. Mehrfach. Sehr mehrfach
Heute sind ja bei jedem Compiler Demos dabei die sich sogar ohne Zicken
kompilieren lassen. Mädchenkram
-
Ist für euch das Umsetzen eines Algo in Code schwierig oder das Verstehen des Algo oder das Ausdenken eines Algo?
