Algorithmen verbessern

[Johnny2]

Hallo,

ich programmiere zwar schon seit einiger Zeit ein bisschen, nur hab ich mich nie sehr mit Algorithmen auseinandergesetzt. Interessiere mich aber jetzt dafür und würde gerne erfahren wie man Algorithmen verbessert bzw. schneller macht. Mir ist klar, dass dies mathematisch geschehen kann, aber wie funktioniert das noch? Welche Möglichkeiten gibt es da und kann ich das lernen oder lernt man aus der Erfahrung, durch z.B. lesen von Quellcodes, die Algorithmen verbessern? Gibt es da bestimmte Schemen, also z.B. das Addieren von 25 mit sich selbst (25+25) geht schneller als das multiplizieren mit 2 (25*2) usw.
Hoffe ich hab das jetzt nicht zu blöd erklärt und ihr wisst was ich mein.

 

[Ark]

Performanceprobleme? Her damit! :3 Ich liebe es, Programme noch schneller zu machen.

Allerdings muss so etwas von Grund auf passieren, oder besser gesagt: Das richtige Design spielt eine wichtige Rolle. Hier hilft die O-Notation, mit der sich schon gut Aufwand abschätzen lässt. Wenn es wirklich um das letze Fünkchen Geschwindigkeit geht, helfen dabei auch Assemblerkenntnisse. Algorithmen arbeiten immer auf bestimmten Datenstrukturen, und diese müssen dazu geeignet sein, von einem "schnellen" Algorithmus verarbeitet werden zu können. Meistens ist es beispielsweise so, dass mindestens ein Operand in irgendeiner Form eine reine Zweierpotenz sein muss, wenn man "Vollgas" geben können will.

Am besten, du kommst mit einem ganz speziellen Problem, dann lässt sich das ganze am Beispiel viel leichter erklären.

Ark

 

[0x7F800000]

Was willst du denn? Irgendeine ultimative mathematische Formel zum verbessern aller Algorithmen^^?
Klar, kannst du haben! Soll ich noch das Elixir der Unsterblichkeit und die Baupläne für die Zeitmaschine einpacken? :autsch:

Die Antwort "baue einen Quantencomputer" würde es vielleicht noch am ehesten treffen...

 

[Johnny2]

@ Andrey: Jep, Unsterblichkeit wär schon nen klasse Ding und Zeitreisen - her damit...

@ Ark: Assemblerkenntnisse hab ich und O-Notation sagt mir auch was - ist doch schon mal ein Anfang^^
Ich denke mir kommst auf das "letzte Quäntchen" an, also z.B. ich will 25 mal 2 nehmen: Da kann ich wie oben gesagt, 25+25 rechnen und 2*25 rechnen, aber auch in der Binärdarstellung alles um eine Stelle nach links schieben. Was mit Sicherheit ja alles unterschiedlich schnell geht. Von diesen Dingen gibt es ja viele, nur woher weiß ich was wirklich am Meisten bringt, ohne alle Optionen durchzuprobieren.
Gibt es sowas wie ne Liste, wie lang diese und jene Operation unter Java benötigt? Und wie seit ihr im Verbessern von Algorithmen besser geworden? Mathebücher, Bücher über Algorithmen, Übung oder alles zusammen?

 

[0x7F800000]

zum einen dürfte es ziemlich egal sein, ob du 25*2 oder 25<<1 hinschreibst, wenn das sinnvoll ist, wird ds der compiler auch ohne dich optimieren, wegen solchen kleinigkeiten lohnt es sich nicht sonderlich, den code unnötig zu verkomplizieren.
Mit "Algorithmen" hat das eh nichts zu tun.

Und wie seit ihr im Verbessern von Algorithmen besser geworden?

Zum einen hilft der schlichte gesunde Menschenverstand.
Wenn man sieht, dass man dauernd irgendwelche sinnfreien Aktionen wiederholt ausführt, obwohl man das nur einmal machen müsste, dann ist natürlich jedem sofort klar, dass das optimiert werden kann.

Anschauung hilft auch ungemein. Für bessere Anschauung könnte man auch versuchen, selbst irgendwas per hand zu lösen.

Analogien zu bereits gelösten Problemen suchen schadet natürlich auch nie.

Vorsichtige mathematische modellierung und präzise Abschätzungen der laufzeit erfordern im einfachsten Fall viel Geduld und Konzentration, in komplizierteren Fällen findest du wohl auch den einen oder den anderen abgefahrenen probabilistischen Algorithmus, der auch einige Mathematiker zur kapitulation zwingen würde, weil's einfach zu kompliziert ist, irgendeine wharscheinlichkeit explizit auszurechnen.

Dann ist es einfacher, eine Benchmark zu schreiben, und stur zig tausend (millionen/milliarden) beispiele durchprobieren, und schauen, ob das, was man erhält, besser oder schlechter ist, als das, was man mal hatte. Ist in den meisten Fällen auch schneller vollbracht, als wenn man haufen Mathematiker zusammentrommelt, und monatelang nach einem exakten Beweis sucht, warum etwas schneller oder langsamer läuft.

Solche Beweise sind dann weniger dazu nützlich, um die schnelligkeit des Algorithmus zu schätzen.
Das kann auch das dumme Benchmarking programm durch stures durchprobieren.
Die Beweise sind eher dazu da, damit man den algorithmus gut versteht, und sieht, wo man es verbessern könnte.

____________________
Auf viele elementare Algorithmen kommt man oftmals nicht selbst. Erst wenn man das mal erzählt bekommt, oder irgendwo liest oder hört, erscheint es einem plötzlich alles offensichtlich.

Dazu sind imho alle quellen gut genug.
Bücher.
Bücher.
Internetsuchen.
Vorlesungen.
Foren.
Lies dir einfach ein schönes Grundlagenbuch durch, versuche selbst irgendwelche Algorithmen umzusetzen und diese zu verbessern.

Wenn es um neue Algorithmen geht, ist das eher sowas wie eine hohe Kunst. Da braucht man haufen erfahrung und talent dafür.

Ob man das Talent hat, kann man nicht sofort einsehen. Aber Übung ist eh eine (zwar nicht hinreichende) aber notwendige Bedingung. Also solltest du üben. Ob daraus was wird, wirst du dann selber sehen.

 

[Johnny2]

Danke für deine ausführliche Erläuterung, hat mir einiges bewusst gemacht.

Übrigens: Bin erstaunt wie schnell man hier Hilfe bekommt. Klasse.

 

[Ark]

Von diesen Dingen gibt es ja viele, nur woher weiß ich was wirklich am Meisten bringt, ohne alle Optionen durchzuprobieren.
Gibt es sowas wie ne Liste, wie lang diese und jene Operation unter Java benötigt?

Ich habe mir mal auch so eine Liste gewünscht, aber bisher bin ich nicht über etwas Derartiges gestolpert. Meine Erfahrungen sagen mir jedoch für Ganzzahlen Folgendes bzw. theoretisch könnte es so sein (vom Schnellsten zum Langsamsten, keine Garantie):

& | ^ ~
<< >> >>>
== !=
< <= > >= + -
*
/ %

Quasi immer "ungefährlich" ist der Einsatz der genannten Operationen bis zur Addition/Subtraktion; bei der Multiplikation wird's schon kritisch. Schneller als eine UND-Verknüpfung wird wohl nichts sein, und wenn du deinen Rechner so richtig ausbremsen willst, benutzt du am besten Division bzw. Modulo. Falls dir selbst das noch zu schnell ist, kannst du Gleitkommazahlen verwenden. FP-Operationen sind grundsätzlich langwieriger als Integer-Operationen.

Und wie seit ihr im Verbessern von Algorithmen besser geworden? Mathebücher, Bücher über Algorithmen, Übung oder alles zusammen?

Ich habe mal ein Buch über Algorithmen und Datenstrukturen gelesen. Da finden sich einige sehr interessante Ansätze, die man auch in seinem "Programmieralltag" gewinnbringend einsetzen kann. Ansonsten kommt so etwas, denke ich, mit Erfahrung.

Ark

 

[Johnny2]

Danke dir. Werd mir mal so ein Buch besorgen und dann noch ein bisschen mehr rumprobieren über die Feiertage. Übung macht den Meister ;-)

 

[0x7F800000]

will jetzt am Montag (=offizieller beginn der Vorlesungsfreien Zeit) damit anfangen, "Analysis of Algorithms" von Sedgewick und Flajolet durchzublättern, mal schaun was daraus wird^^ Kennt einer das Buch zufällig? Stand jetzt nicht auf der Liste der empfohlenen Literatur, aber auf den ersten blick war das nicht das schlimmste, was in der Bücherei noch nicht vergriffen wurde [woow, was für eine schwammige Bewertung, ich sollte vielleicht doch Politiker werden ]

Denn bisher bis ich praktisch aussließlich mit dem "gesunden Menschenverstand" drangegangen...

 

[Landei]

Statt a + a oder 2*a kannst du auch a << 1 schreiben, aber ich denke, so schlau ist der Compiler auch.

 

[Leroy42]

LOL!

Da haben sich ja mal die richtigen 2 Optimierungsfetischisten gefunden!

 

[Ebenius]

Hier muss ich doch glatt mal auf meine Signatur verweisen. :-D