Euer schwierigster Algorithmus?
-
rapso schrieb:
ich dachte man ist programmierer damit man immer etwas noch schwierigereres programmiert als vorher, waere es sonst nicht sehr langweilig?
Eben. Daher auch in meinem Eingangstext das "bisher"
-
cooky451 schrieb:
Hm.. AES vermutlich, aber wie schon gesagt, wenn mans einmal geschafft hat..
Ich dachte, AES wurde unter anderem so entworfen, dass er einfach zu implementieren ist (z.B. auch auf Hardware)?
Meinen "schwersten" Algorithmus hatte ich erst vor kurzem. Tasächlich ist es eigentlich ein ganz einfaches Problem, auf einem x*y-Schachbrett (oder einem anderen Brett mit Feldern) soll die Länge (also Anzahl der Felder) einer bestimmten Diagonalen ermittelt werden, gegeben durch Diagonalenindex (von 0 bis x+y-1) und Ausrichtung (links oben nach rechts unten bzw. rechts oben nach links unten - gibts dafür eigentlich Fachbegriffe?). Durch irgendeine Schraube im Kopf wollte mir keine einfache Formel einfallen, die ohne viele Fallunterscheidungen auskommt. Selbst die endgültige einfache Lösung ist mehr oder weniger durch Probieren entstanden.
-
@ipsec: Übersehe ich etwas oder reicht dazu der Satz von Pythagoras?
MfG SideWinder
-
Algorithmen werden fuer mich immer dann schwer, wenn die Vorstellungskraft nicht mehr ausreicht. Zum Beispiel die Vorstellungskraft bezueglich der moeglichen Sonderfaelle und so weiter. Einfach, wenn alles zu komplex wird. Irgendwie habe ich da vor allem schlechte Erfahrungen mit Oberflaechenrekonstruktionen von 3D-Punktwolken gemacht. Eigentlich handelt es sich dabei noch um Daten, die man sich recht gut bildlich vorstellen kann und man kann sich auch gut vorstellen, was ein Algorithmus an einer bestimmten Stelle macht, trotzdem kann es in den Daten derart viele Sonderfaelle und so weiter geben, dass man schnell Probleme kriegt. Wer sich daran mal probieren moechte, kann ja mal den Ball Pivoting Algorithmus umsetzen. Ich habe das mal gemacht, glaube aber, dass der bis heute nicht komplett bugfrei ist.
www.research.ibm.com/vistechnology/pdf/bpa_tvcg.pdf
Allerdings kann das fuer einen anderen, der vielleicht eine andere Arbeitsweise als ich hat, recht leicht umsetzbar sein. Weiss ich nicht. Vielleicht gehe ich an die Sache zu unsystematisch ran.
-
SideWinder schrieb:
@ipsec: Übersehe ich etwas oder reicht dazu der Satz von Pythagoras?
MfG SideWinder
In meinem Fall nur sehr bedingt. Angenommen es ist ein 4x4-Feld gegeben und man möchte die Länge der Diagonalen 4 (von 0 beginnend), die von links unten nach rechts oben geht (es wird von links oben nach rechts unten gezählt). Die richtige Antwort wäre 3. Wo nehme ich hier den Satz des Pythagoras?
Noch lustiger wird es, wenn die Höhe und Breite des Feldes unterschiedlich sind.
-
ipsec: Für Quadrate wäre das halt sqrt(4^2 + 4^2) / sqrt(1^2 + 1^2).
Für Rechtecke analog, wenn alle diese gleich groß sind. Sind sie unterschiedlich groß, wird's wilder.
-
Eisflamme schrieb:
sqrt(4^2 + 4^2) / sqrt(1^2 + 1^2).
Das ist die längste Diagonale (Index min(width, height)-1 bis max(width, height)-1). Deren Länge ist allgemein min(width, height). Allgemein ist Länge der Diagonalen x gleich x+1, wenn x < min(width, height). Ansonsten ist es max(width, height)-(x-min(width, height)-1, wenn x >= max(width, height) (oder so ähnlich, ich habe grade nicht Zugriff auf den Quellcode). Ansonsten ist es min(width, height). Das ganze gilt nur, wenn die Diagonale von links unten nach rechts oben geht, ansonsten ist wieder alles anders (auch durch meine Art und Weise, in welcher Reihenfolge die Diagonalen dann indiziert sind).
Ich dachte halt, dass es für so ein einfaches Problem eine einfache Formel gibt.
-
Mein "schwierigster" Algorithmus (wobei ich Annehme, das man diesen Mathematisch recht trivial beschreiben kann) war bislang war eine Berechnung der geringsten Konditionen für Kunden, die Verträge auf Basis einzelner Monate abschließen können.
Je nach ausgewählten Monaten etc. konnte es günstiger sein ganze Quartale, Halbjahre oder Jahre zu buchen (Wobei jeder einzelne Abrechnungszeitraum unterschiedliche Kosten aufgewiesen hat [Etwa so wie Saisonpreise, wenn auch in einen anderen Sektor]). Der Algorithmus buchte nach der Auswahl der Monate die kostengünstigste Variante (die dann effektiv auch die Leistung für mehr als die gewählten Monate umfassen konnte - sofern dies billiger oder zumindest gleich teuer war).
Und ja, wie man sieht, hatte ich noch nicht wirklich komplizierte Algorithmen in meiner gesamten Zeit, die ich nun als Softwareentwickler tätig bin, zu lösen... Ein Beispiel dafür das Mathematik und Algorithmen nicht zwangsweise Voraussetzungen sind, je nach dem was man macht.
-
Eisflamme schrieb:
Hat hier sonst niemand etwas Kompliziertes programmiert oder ist das gar furchtbar geheim ?
Ich könnt es dir sagen, aber dann müsste ich dich umbringen
-
Komplexe Software setzt man aus Bausteinen zusammen. Bausteine aus noch kleineren Bausteinen. U.s.w. Da gibt es dann auch nicht "den Algorithmus". Das ist eine Sammlung von Algorithmen. Sowie eine Sammlung von Datenstruktoren.
Und wie schon gesagt wurde, wenn man etwas geschafft hat, dann kommt einem das auch alles nicht mehr so kompliziert vor. Bei dem, was ich im Job mache (relativ viel Mathe) würden wahrscheinlich auch viele sagen, dass das recht komplex oder schwierig ist. Aber das ist alles nur eine Frage der Erfahrung. <mal_angeb> Um mal ein Beispiel zu nennen. Ich habe die Software geschrieben, die für das hier die Auswertung macht (frequency domain beamforming). </mal_angeb> Das ist nicht ohne, wenn man mit so etwas noch nie zu tun hatte. Aber auf der anderen Seite auch wieder ganz einfach wenn man sich dementsprechend länger mit beschäftigt...
-
- 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.
