Beschleunigung von Algorithmen, Quelle gesucht
Hi!
Ich hatte einmal eine schöne Anleitung in 5 oder 6 Schritten gefunden,
wo die Schwerpunkte zu setzen sind, wenn eine computerbasierte Lösung zu
langsam zum Ziel führt. Kennt ihr die Quelle die (sinngemäß) folgende
Schritte aufgeführt hatte:
1) Problemstellung vereinfachen
...
3) Algorithmus geringerer Komplexität wählen
...
5) Leistungsfähigere Hardware anschaffen
6) Codeoptimierung
Es geht nicht um Sinn oder Unsinn dieser Reihenfolge, sondern nur um den
Ursprung dieser Liste. Wahrscheinlich existiert solch eine Anleitung in
den verschiedensten Ausführungen, aber eine beliebige - ordentlich
diskutierte - Quelle würde mich schon zufriedenstellen.
Danke
Kevin
> Es geht nicht um Sinn oder Unsinn dieser Reihenfolge,> sondern nur um den Ursprung dieser Liste
Wahrscheinlich aus dem Kindergarten.
Mann ist das eine abstruse Aufstellung.
Soo... also ich hätt da gern ein Traveling Salesman Problem:
Kevin schrieb:> 1) Problemstellung vereinfachen
Ok, also weniger "Reiseziele"... löst dann aber mein Problem nicht mehr
> ...> 3) Algorithmus geringerer Komplexität wählen
Hmm... Dummerweise steht in meinem Algo-Buch keiner mit O(n). Also nix
mit wählen.
> ...> 5) Leistungsfähigere Hardware anschaffen
Quantencomputer sind bei Aldi grad ausverkauft :(
> 6) Codeoptimierung
Wow. Ein bischen Inline-ASM hier, etwas Pointer-Magie dort, und schon
ist das Problem trivial ;)
SCNR.
Sehr witzig.
In dem Artikel wurde diskutiert, dass es keinen Sinn macht, mehrere
Mannjahre in die Codeoptimierung zu investieren, damit das Programm 20%
schneller läuft oder Supercomputer anzuschaffen, um ineffiziente
Algorithmen um 2 bis 3 Größenordnungen schneller zum Ergebnis zu
bringen.
Stattdessen sollte, um beim TSP zu bleiben, z.B. von der
Wunschvorstelung einer deterministischen, optimalen Lösung, ausgewichen
werden auf eine heuristische nahezu-optimale Lösung. Ja, die bekommt man
in O(n^2) statt O(n!).
Aber ich sehe schon, es geht hier im Forum nur darum, sich zu
profilieren und die Fragestellung zu zerreissen, statt eine Antwort
(oder auch einfach gar keine Antwort) zu geben.
Kevin
Kevin schrieb:> Sehr witzig.> In dem Artikel wurde diskutiert, dass es keinen Sinn macht, mehrere> Mannjahre in die Codeoptimierung zu investieren, damit das Programm 20%> schneller läuft oder Supercomputer anzuschaffen, um ineffiziente> Algorithmen um 2 bis 3 Größenordnungen schneller zum Ergebnis zu> bringen.
Und wie alle Generalisierungen ist auch diese falsch.
Es kommt immer auf den konkreten Fall an.
Und deswegen ist es auch so schwer hier generelle Empfehlungen zu geben.
In einem allerdings sind sich nahezu alle einig.
* Schreibe deinen Code so, dass er gut zu lesen ist
Vermeide offensichtliche Fallen. Übergib in C++ zb keine
Objekte, wenn es gar nicht notwendig ist, sondern benutze Referenzen
(auch const Referenzen) wo es auch immer geht
Lege auf jeden Fall am Anfang nicht zuviel Augenmerk auf sog.
clevere Optimierungen, die dir nur den Algorithmus verschleiern
* läuft das Programm
dann: Ist es schnell genug? -> Ja -> Lass es so
* Ist es nicht schnell genug?
Dann lass einen Profiler auf dein Programm los und sieh nach, wo
die Zeit verbraucht wird
* Zurücklehnen und überlegen, in wieweit das Profilerergebnis dir
Hinweise gibt, wo in deinem Algorithmus die Flaschenhälse sind
* Kannst du etwas dagegen tun?
Auch wenn das bedeutet, weite Teile des Verfahrens neu zu gestalten?
Wenn ja, dann tu es
Anschliessend geht es wieder ein paar Schritte zurück und der Prozess
beginnt bei 'Ist es schnell genug?' erneut
* Wenn nein.
Schau dir nochmal das Profilerergebnis an. Es wird so sein, dass
es ein paar Funktionen gibt, die für den Löwenanteil der Rechenzeit
verantwortlich ist.
Sieh zu, dass du da etwas drehen kannst.
Bevorzuge zunächst Hi-Level Codeänderungen ehe du dich in die
Niederungen von Bits und Bytes runterbegibst.
Tja. Man kann natürlich noch bei jedem Punkt ein bischen was erzählen.
Aber in a nutshell wars das. Jedes Problem, jeder Algorithmus ist
anders. Konkrete Empfehlungen sind daher sehr sehr schwer, weil sie in
den meisten Fällen nicht passen.
* Bevorzuge algorithmische Optimierungen vor Codeoptimierungen
* Bevorzuge Hi-Level Code Optimierungen vor Low-Level Codeoptimierungen
* Optimization - don't do it
* Optimization - don't do it yet
* Premature optimization is the root of all evil
Wenn ich mich recht erinnere hab ich die punkte auch schon mal gelesen,
und zwar in 'Algorithmen kompakt und verständlich : Lösungsstrategien am
Computer' von Markus von Rimscha - 1. Aufl.
Hier offenbart sich der Unterschied zwischen Softwareentwicklern
einerseits und reinen Programmierern (wie anscheinend Karl Heinz)
andererseits.
In unserem Betrieb nutzt niemand niemals nie einen Profiler als ersten
Schritt, wenn es darum geht, Engpässe aufzuspüren. Stattdessen wirft man
einen Blick in die Dokumentation und nutzt seinen gesunden
Menschenverstand, um mögliche Ursachen zu finden. Oft sind in der
Dokumentation bereits Hinweise auf mögliche, aber noch nicht
implementierte, Verbesserungen zu finden. Wer seinem Compiler das Denken
überlässt oder selbst in Bits und Bytes denkt, kommt hier natürlich
nicht weiter.
Dann frickelt mal fleißig weiter. Mein Hinweis, dass ich nur eine Quelle
suche, aber nicht an euren natürlich zigfach wertvolleren
Expertenmeinungen interessiert bin, verlangt euren uC-Köpfen anscheinend
zuviel ab.
Tschö
Kevin schrieb:> In unserem Betrieb nutzt niemand niemals nie einen Profiler als ersten> Schritt, wenn es darum geht, Engpässe aufzuspüren. Stattdessen wirft man> einen Blick in die Dokumentation und nutzt seinen gesunden> Menschenverstand, um mögliche Ursachen zu finden.
Dokumentation ist gut.
gesunder Menschenverstand ist schlecht. Der liegt nämlich nachweislich
mehr als nur des öfteren daneben.
> Oft sind in der> Dokumentation bereits Hinweise auf mögliche, aber noch nicht> implementierte, Verbesserungen zu finden.
Echt?
Welche Doku hast du, wenn da drinnen steht, was man an einer Library
verbessern könnte und warum hat das der Entwickler dann nicht schon
längst gemacht?
> Wer seinem Compiler das Denken> überlässt oder selbst in Bits und Bytes denkt, kommt hier natürlich> nicht weiter.
Richtig.
Daher auch der Profiler:
Optimierung fangt am besten eben nicht damit an, dass man anfängt wie
wild rumzufrickeln, sondern indem man erst einmal Zahlen sammelt.
> Dann frickelt mal fleißig weiter. Mein Hinweis, dass ich nur eine Quelle> suche, aber nicht an euren natürlich zigfach wertvolleren> Expertenmeinungen interessiert bin, verlangt euren uC-Köpfen anscheinend> zuviel ab.
Das nicht.
Nur kennt deine 'Quelle' offenbar niemand.
Wobei sich dann natürlich auch die Frage stellt, wie wertvoll diese
Quelle ist. Denn Optimierung in 5 bis 6 leicht verständlichen, einfach
umzusetzenden Schritten .... mit Verlaub, aber das gibt es nicht.
Edit: Kann es sein, dass du gar nicht weißt, was ein Profiler macht,
oder du das jetzt irgendwie verwechselst? Anders ist dieser Satz
> nutzt niemand niemals nie einen Profiler als ersten> Schritt, wenn es darum geht, Engpässe aufzuspüren
nämlich nicht richtig zu interpretieren. Ein Profiler IST ein Werkzeug
um Engpässe aufzuspüren. Das ist sein einziger Daseinszweck.
Lieber Karl-Heinz, du lebst in deiner eigenen Welt, und das ist gut so.
Ich möchte dich gar nicht animieren, über deinen Tellerrand zu schauen,
denn es könnte frustrierend werden.
>Welche Doku hast du, wenn da drinnen steht, was man an einer Library>verbessern könnte
Unsere hausinterne Doku
>und warum hat das der Entwickler dann nicht schon>längst gemacht?
Weil wir Fristen einzuhalten haben. Zunächst muss ein Produkt
abgeliefert werden. Vielleicht kennst du die 80/20-Regel. Wir treiben
20% Aufwand, um 80% des möglichen Ergebnisses zu erreichen. Wir
verzichten auf die 80% Aufwand, um die restlichen 20% zu schaffen. Und
damit fahren wir im Allgemeinen sehr gut.
>Optimierung fangt am besten eben nicht damit an, dass man anfängt wie>wild rumzufrickeln, sondern indem man erst einmal Zahlen sammelt.
Genau hier liegt dein Problem. Wenn ich ich der Dokumentation lese, dass
z.B. ein O(n!) Algorithmus verwendet wird, brauche ich keine Zahlen, um
zu wissen, dass es ab n=5 oder n=10 ungemütlich wird. Einen Profiler
anzuschmeißen IST frickeln, denn das machst du nur, weil du keinen
Überblick hast, wo dein Problem liegt. Aber das wirst du nicht einsehen,
und darum diskutiere ich es nicht weiter mit dir.
>Ein Profiler IST ein Werkzeug um Engpässe aufzuspüren. Das ist sein>einziger Daseinszweck.
Genau. Zum Glück ist der einzige Daseinszweck meines Kopfes NICHT, einen
Profiler bedienen zu können. Du kennst den Unterschied zwischen "alle
Raben sind schwarze Vögel" und "alle schwarzen Vögel sind Raben"?
Sieh mal nach, ob du das Buch findest, das der Autor "ich" oben genannt
hat. Es könnte ein paar erschreckende Neuigkeiten für dich bereithalten,
z.B. dass Computer und Softwareentwicklung heute anders aussehen als vor
50 Jahren.
@Kevin:
Jetzt verstehe ich nur eins nicht: Wenn du wirklich so genau weißt, wie
Softwareentwicklung geht, wieso brauchst du dann noch ein Buch, in dem
solche Binsenweisheiten stehen:
> 1) Problemstellung vereinfachen> ...> 3) Algorithmus geringerer Komplexität wählen> ...> 5) Leistungsfähigere Hardware anschaffen> 6) Codeoptimierung
Das passt doch überhaupt nicht zusammen.
Kevin schrieb:
LOL
> Genau hier liegt dein Problem. Wenn ich ich der Dokumentation lese, dass> z.B. ein O(n!) Algorithmus verwendet wird,
Du hast recht.
Solange in deiner DOku steht, dass du es mit einem O(n!) Algo zu tun
hast, brauchst du das alles nicht.
Sorry. Meine Algos sind ein wenig komplexer. Da kann man selten bis gar
nicht angeben, welcher O Klasse sie angehören :-)
> hat. Es könnte ein paar erschreckende Neuigkeiten für dich bereithalten,> z.B. dass Computer und Softwareentwicklung heute anders aussehen als vor> 50 Jahren.
Genau.
Zb. das die O Notation toll ist. Für praktische Zwecke in Algorithmen,
die aus ein paar 1000 Schritten bestehen aber nicht zu gebrauchen ist,
weil man sie einfach nicht ermitteln kann.
Also leb weiter in deiner heilen Welt, in der es nur O-Notation gibt und
man alles andere davon ableiten kann. Vielleicht schreibst du ja auch
eines Tages mal richtige Programme und nicht nur Micky Mouse Teile.
Und PS: Die 80/20 Regel besagt etwas anderes. Aber seis drum.
>Da kann man selten bis gar>nicht angeben, welcher O Klasse sie angehören :-)
Kann ich mir kaum vorstellen. Die Faktoren für eine Bewertung des
Algorithmus sind doch zumeist sofort ersichtlich.
Beispiel:
einfache Schleife: O(n)
zwei verschachtelte Schleifen: O(n^2)
OK, das ist vielleicht ein wenig stark vereinfacht, aber das Prinzip
sollte klar sein.
> zwei verschachtelte Schleifen: O(n^2)
wenn sich beide auf dasselbe n beziehen, kein break und keine
Ausnahme dazwischen kommt, ...
In der Tat etwas vereinfacht.
Lieber Kevin,
anscheinend lebt nicht Karl Heinz in seiner eigenen Welt, sondern du.
Wenn ihr in eurer Firma so schlampig programmiert, kann es gut sein,
dass eine so banale Liste zum Erfolg führt. Das ist dann aber keine
"Beschleunigung" von Algorithmen, sondern einfach das saubere
Implementieren eines solchen.
Karl Heinz sprach von dem eigentlichen Fall, dass etwas schon "sauber"
implementiert ist, aber es trotzdem noch irgendwie zu langsam ist. Da
hilft dir dann keine Doku, da hilft dir der Profiler.
Zu deinem eigentlichen Problem kann man sagen: Implementiert euer Zeug
sauber, da braucht es auch keine Liste für.
Nico.
High Performer schrieb:>>Da kann man selten bis gar>>nicht angeben, welcher O Klasse sie angehören :-)>> Kann ich mir kaum vorstellen. Die Faktoren für eine Bewertung des> Algorithmus sind doch zumeist sofort ersichtlich.>> Beispiel:>> einfache Schleife: O(n)>> zwei verschachtelte Schleifen: O(n^2)>> OK, das ist vielleicht ein wenig stark vereinfacht, aber das Prinzip> sollte klar sein.
Das Problem ist, dass reale Programme nicht so banal aufgebaut sind. In
seiner Lehrzeit lernt man viele Algorithmen, die sich so bewerten
lassen, aber in der Realität kommen die selten genau so vor.
Wie ist denn die Komplexität eines Hidden Liners? Pinrizpiell muss er
jede Kante mit jeder Fläche verschneiden. Also O(N^2). Nur wenn du das
so implementierst hast du schon verloren. Das ist zu langsam. Viel zu
langsam. Ein Profiler sagt dir, dass von der kompletten Laufzeit rund
80% dafür draufgehen, dass du versuchst Schnittpunkte auszurechnen, die
es nicht gibt. Also wirst du versuchen, diese unnötigen Berechnungen zu
vermeiden wo es nur geht. Eergo kommt ein Box-Vortest da mit hinein. Die
Laufzeit sinkt drastisch. Und obwohl dein Algorithmus dem Prinzip nach
immer noch o(n^2) hat und du das auch durch die beiden ineinander
geschachtelten Schleifen auch siehst, hat er in der Realität durch den
Boxvortest jetzt schon eher O(1.5*n). Mit anderen Methoden wie zb Triage
Tabeln lässt sich das noch weiter drücken, so dass man einen prinzipiell
O(n^2) Algorithmus in weit weniger als O(n^2) implementieren kann. Man
könnte auch sagen: prinzipiell sind alle immer noch O(a*n^2). Ich weiß
schon, dass es bei der O Notation keine konstanten Faktoren mehr gibt.
Aber es ist genau dieses a, dass den unterschied zwischen einem
langsamen Hidden Liner und einem akzeptablen Hidden Liner und einem der
produktionstauglich ist ausmacht. Klar im Falle eines Hidden Liners kann
man dann auch ausweichen, ein Warnock-Quadtree Verfahren hat als
Divde-and-Conquer Algorithmus eine andere Komplexität, aber was tust du,
wenn du keinen anderen Algorithmus kennst.
Es ist eine Sache zu sagen: Och ich hab in meiner Lib einen O(n!)
ALgorithmus. Nur: Was machst du wenn du diese Funktionalität brauchst?
Wenn es nun mal kein anderes Verfahren gibt? Du kannst nicht einfach
sagen, dann nehm ich das halt nicht, denn du hast eine Aufgabe zu lösen!
Das jemand nicht mutwillig einen O(n^3) Algo einsetzt, wenn es einen
O(n^2) Algo gibt, das setze ich vorraus und das hat auch nichts, aber
rein gar nichts mit Optimierung zu tun, sondern eher damit dass man sein
Handwerk beherrscht.
Hi,
hinzu kommt noch, dass reale Algorithmen von irgendwo her die Daten
bekommen müssen und auch irgendwohin wieder ablegen müssen. Die
Engstelle muss also noch nicht einmal der Algo selbst sein, sondern kann
ebenso beim Beschaffen der Daten (aus Datenbank, Internet usw.)
auftreten.
Da würde dem tollen Softwareentwickler Kevin dann auch seine
Dokumentation nicht mehr weiterhelfen.
Wer Profiler als "Frickelwerkzeug" bezeichnet hat einfach noch nie an
größeren Projekten gearbeitet, sonst würde er hier nicht so einen Stuss
ablassen.
Diesen Thread zu verlassen war das einzig Richtige, was Kevin machen
konnte, um sich selbst nicht noch mehr zu diskreditieren ;-)
Gruß,
Pardon, jetzt muss ich aber doch mal einhaken.
Es gibt den schönen Spruch "Premature Optimization is the root of all
evil", womit ausgesagt werden soll, dass man nicht anfangen soll zu
optimieren, bevor man weiß wo die Laufzeit hingeht. Damit eben
sichergestellt ist, dass man nicht an etwas rumoptimiert, was sowieso
nur 0.001% der Laufzeit benötigt. Und um das festzustellen ist natürlich
- und da hat Karl heinz völlig recht - ein Profiler ein essentielles
Werkzeug.
Aber das hier:
Karl heinz schrieb:
> Ergo kommt ein Box-Vortest da mit hinein. Die Laufzeit sinkt drastisch.> Und obwohl dein Algorithmus dem Prinzip nach immer noch o(n^2) hat und du> das auch durch die beiden ineinander geschachtelten Schleifen auch> siehst, hat er in der Realität durch den Boxvortest jetzt schon> eher O(1.5*n).
ist - mit Verlaub - Blödsinn. Ich nehme an dass Du mit einem
"Box-Vortest" meinst, dass Du die Bounding-Boxen der Linien erstmal auf
(potentielle) Überlappung testest, bevor Du dann erst eine aufwendigere
Schnittpunktberechnung machst.
Dieser zusätzliche Test ändert nichts - aber auch gar nichts - an der
Laufzeitklasse O(n²). Es ist sehr gut möglich, dass sich der Algorithmus
dramatisch schneller anfühlt, wahrscheinlich sogar auch absolut
schneller ist. Das macht ihn aber nicht zu einem O(1.5n)-Algorithmus und
die Formulierung lässt mich fürchten, dass hier ein Missverständnis
vorliegt, was diese Laufzeitklassen überhaupt bedeuten.
O(1.5n) ist exakt das gleiche wie O(n) und das ist exakt das gleiche wie
O(0.00001n). Und es ist etwas fundamental anderes als O(n²). Eine
Laufzeitklasse taugt einfach nicht, um eine Beschleunigung eines
Algorithmus um einen gewissen Faktor zu beschreiben, genauer gesagt ist
das genau das, was man mit den Laufzeit*klassen* wegabstrahieren möchte.
Die Laufzeitklassen treffen eigentlich auch nur eine Aussage über ein
Verhalten von Algorithmen, wenn die Problemgröße gegen unendlich wächst.
Insofern sind sie natürlich ein theoretisches Werkzeug die in der Praxis
nur vergleichsweise wenig Aussagekraft haben. Ich halte sie dennoch für
sehr wichtig, weil ein Programmierer es merken sollte, dass er gerade
die dritte Schleife über den Input ineinanderschachtelt und damit sein
Algorithmus plötzlich O(n³) wird und eine verdammt hohe Chance besteht,
dass das Resultat unbenutzbar langsam wird. Ein Programmierer sollte
IMHO verstanden haben, dass es sich quasi immer lohnt, etwas Aufwand in
die Infrastruktur zu stecken, so dass da eventuell ein O(n log
n)-Algorithmus draus werden kann.
Ich werde nie das Aha-Erlebnis vergessen, als ich (um die
Fouriertransformation zu verstehen) eine naive DFT in Python
hingeschrieben habe. Und das schon für verdammt kleine Eingabegrößen
endlos lange rechnete. Dann habe ich eine FFT implementiert und mit
einem Wimpernschlag war das Ergebnis da. Augenöffnend.
Viele Grüße,
Simon
Simon Budig schrieb:> Karl heinz schrieb:>> Ergo kommt ein Box-Vortest da mit hinein. Die Laufzeit sinkt drastisch.>> Und obwohl dein Algorithmus dem Prinzip nach immer noch o(n^2) hat und du>> das auch durch die beiden ineinander geschachtelten Schleifen auch>> siehst, hat er in der Realität durch den Boxvortest jetzt schon>> eher O(1.5*n).>> ist - mit Verlaub - Blödsinn.
Da hast du recht. Ich hab mich schlecht ausgedrückt.
> Dieser zusätzliche Test ändert nichts - aber auch gar nichts - an der> Laufzeitklasse O(n²). Es ist sehr gut möglich, dass sich der Algorithmus> dramatisch schneller anfühlt, wahrscheinlich sogar auch absolut> schneller ist. Das macht ihn aber nicht zu einem O(1.5n)-Algorithmus und> die Formulierung lässt mich fürchten, dass hier ein Missverständnis> vorliegt, was diese Laufzeitklassen überhaupt bedeuten.
Nein.
Das ist schon klar. Prinzipiell ist er schon noch O(n^2)
Nur kann man die Parabel so strecken, dass sie für die
Problemstellungen, auf die man den Algo anwendet, in der Praxis die
Parabel soweit gestreckt wird, dass daraus mit den relevanten n de
facto eine Gerade wird. Das das Verfahren prinzipiell nach wie vor x^2
ist, ist schon klar.
Es geht hier einfach um den Unterschied zwischen einer Kenngröße aus der
Theorie und wie sie sich dann in der Parxis auswirkt. Und ich denke,
genau in dasselbe Horn stößt ja auch dein weiterer Artikel, dass es hier
sehr wohl Unterschiede gibt, die man nicht einfach wegdiskutieren kann.
> O(1.5n) ist exakt das gleiche wie O(n) und das ist exakt das gleiche wie> O(0.00001n).
Aus theoretischer Sicht: ja natürlich.
In der Praxis kann das aber einen Unterschied ausmachen, indem 10*n^2
für die praxisrelevanten n noch tragbar ist, 10000*n^2 aber nicht mehr.
Von daher ist die O - Notation nur bedingt aussagekräftig, weil sie
natürlich eine Betrachtung "für alle n" anstellt. Des öfteren hat man
aber gar nicht den Fall, bzw. man kann eine praxisrelevante obere
Schranke angeben über die man nicht drüberkommen wird. Und das verändert
dann die Sache.
Beispiel: Wir alle wissen, dass Bubble-Sort (mit vorzeitigem Abbruch)
ein schlechter Sortier-Algo ist. O(n^2) im Worst Case. Da gibt es
wesentlich besseres. Und doch kann ich mich an einen Fall erinnern, in
dem Bubble Sort alle anderen Sortierverfahren schlägt. Warum: Weil meine
Daten dergestalt waren, dass
* es wenige Daten waren
* die schon nahezu sortiert vorlagen, wenn überhaupt dann waren bei
~10 Aufrufen maximal 2 bis 3 Vertauschungen notwendig.
Hier hat die Einfachheit des Bubble Sort voll zugeschlagen, indem er zu
einem reinen Überprüfen der korrekten Reihenfolge mit gelegentlichem
Eingreifen mutiert ist.
> Und es ist etwas fundamental anderes als O(n²). Eine> Laufzeitklasse taugt einfach nicht, um eine Beschleunigung eines> Algorithmus um einen gewissen Faktor zu beschreiben, genauer gesagt ist> das genau das, was man mit den Laufzeit*klassen* wegabstrahieren möchte.
Exakt.
Und daher ist es auch Unsinn, seine 'Optimierung' rein nur danach zu
richten.
Natürlich wähle ich Zweifelsfall den Algo mit dem bessern O Verhalten.
Aber das hat IMHO nichts mit Optimierung, so wie sie tatsächlich
verstanden wird, zu tun.
Und Algorithmen-Optimierung in dem Sinne, dass man einen Algorithmus
'optimiert' um aus einem O(n^2) einen O(nlogn), das hat mehr mit
Erfinden als mit systematischer Optimierung zu tun. Entweder ich habe
eine radikal andere Idee für einen Algorithmus um ein Problem zu lösen
oder ich habe sie nicht. Aber ich kann mich nicht hinsetzen und kann mir
einen Algo vornehmen um ihn durch irgendwelche Transformationen von
O(n^2) auf etwas anderes zu bringen. Das ist ja das Wesen eines
Algorithmuses, dass er immer die gleiche Komplexität hat. Ein O(n^2)
Algo wird immer ein O(n^2) Algo bleiben. Wenn das prinzipiell nicht
passt, dann muss ich mir einen neuen Algo mit einer radikal andere Idee
einfallen lassen.
Lieber Karl Heinz,
vielen Dank für deine tiefschürfenden Erkenntnisse:
- man sollte keine Algorithmen einsetzen, die es nicht gibt
- die Tangente an einer Parabel ist eine Gerade
- ein O(n) Algo kann länger dauern als O(n^2) für n->0
- dass es bei der O Notation keine konstanten Faktoren mehr gibt, aber
Karl Heinz benutzt sie trotzdem
Wäre doch nur jeder so schlau, dann müsstest du keine 2 Seiten über
solche Trivialitäten füllen.
Sorry, dann habe ich es falsch verstanden.
Kevin schrieb:> ...> - dass es bei der O Notation keine konstanten Faktoren mehr gibt, aber> Karl Heinz benutzt sie trotzdem
Eine Danksagung sehe ich da immer noch nicht drin, aber das wird
wohl an mir liegen.
Kevin schrieb:> Wäre doch nur jeder so schlau, dann müsstest du keine 2 Seiten über> solche Trivialitäten füllen.
Bitte, gern geschehen.
Jetzt geh weiter Doku lesen, damit du auch einen schönen Ersatz für
deinen O(n!) Algo findest.
Klaus Wachtler schrieb:> Sorry, dann habe ich es falsch verstanden.>> Kevin schrieb:>> ...>> - dass es bei der O Notation keine konstanten Faktoren mehr gibt, aber>> Karl Heinz benutzt sie trotzdem>> Eine Danksagung sehe ich da immer noch nicht drin, aber das wird> wohl an mir liegen.
Man kann alles misverstehen und durch Wortklauberei ins Gegenteil
verkehren, wenn man sich nur genug Mühe gibt :-)
Kevin schrieb:> - dass es bei der O Notation keine konstanten Faktoren mehr gibt, aber
Hach, wie schön. Die O-Notation ist ja auch nicht dazu gedacht, die
tatsächliche Laufzeit anzugeben, sondern einen "schnellen" Vergleich zu
geben. Da Karl Heinz die tatsächliche Laufzeit meinte, ist die
Verwendung von konstanten Faktoren doch wohl nur berechtigt.
1,5n ist eben mehr als n. Praktisch. Das spielt "theoretisch" bei der
O-Notation keine Rolle, aber ist praktisch relevant.
Nico.
Kinder, bitte :-)
Kann es sein, dass solche, ich nenn es mal "Flamewars" hier in letzter
Zeit verstärkt auftreten? Irgendjemand fragt was und stellt die Frage
vielleicht nicht 100% präziese und es wird direkt dran rum kritisiert.
Dann werden Fragen beantwortet, die garnicht gestellt worden sind,
Annahmen gemacht, die vollkommen aus der Luft gegriffen sind und wenn
man dann so weit ist, versucht man sich gegenseitig durch
Besserwissergetue nieder zu machen. Ich finde das ziemlich traurig, da
ich das Forum hier eigentlich mal als sehr diszipliniertes und nettes
Forum kennen und schätzen gelernt habe...
So long.
TSP läuft nur in einer trivialen Implementeirung in O(n!), normal hat er
bisher die Laufzeit (wie alle anderen NP-Probleme) O(2^n)
Nur dass das mal festgestellt wird :P
Wenn ich es richtig sehe, wurde dem TO nicht geholfen.
Auch ich habe so eine Liste schohn mal irgendwo gesehen, konnte sie aber
auch nicht wieder finden.
Des halb habe ich mal die Liste (aus meiner Erfahrung) ergänst und mit
Beispielen versehen:
[Phase in dem die Änderung sinnvoll ist]
a) Problemstellung vereinfachen [Specifikation]
b) besseren Algorithmus/Datenstrucktur wählen [Design]
c) Leistungsfähigere Hardware anschaffen [Auslieferung]
d) Codeoptimierung [Implementierung]
e) Compileroptimierung nutzen [Test]
f) Betriebssystem optimieren [Test/Auslieferung]
Beispiele
a) - Problem auf zwei Programme/Kerne/CPUs aufteilen/verteilen
b) - Algorithmus mit geringerer Komplexität/Laufzeit wählen
- Einfachverkettete Liste stat doppelt verkettet
- Multithreading verwenden
d) - Integer stat Float verwenden
- Speicherverbrauch optimieren (Stack stat Globale Variable)
- Daten im Speicher halten (nicht immer neu lesen)
- Schleifen entrollen
- Zeiger stat Index
e) - Speed optimierung einschalten
- Befehlssatserweiterungen einschalten
f) - Prozess-Priorität erhöhen
- Andere Programme/Treiber terminieren um zB das Swabing zu
verhindern
Bitte ergänzen und Berichtigen!
Bartli schrieb:> und damit wird ein Problem einfacher?
Beschleunigung von Algorithmen und Vereinfachung eines
(Programmier-)Problems sind nach wie vor zwei Paar Stiefel.
Und der Preis für die Binsenweisheit des Tages geht an Loonix.
> "a) Problemstellung vereinfachen [Specifikation]"> ...> Beispiele> a) - Problem auf zwei Programme/Kerne/CPUs aufteilen/verteilen
MaWin schrieb:> Mann ist das eine abstruse Aufstellung.
Die Aufstellung ist überhaupt nicht abstrus. Wenn man manchmal liest,
wie Leute daherkommen und behaupten, dies oder jenes ginge sowieso nur
in Assembler oder nur auf einem viel dickeren Controller, dann ist man
froh, wenn man auf so eine Liste verweisen kann. ("Mein Roboter soll 100
Koordinaten anfahren, ich muss also das TSP lösen, da es aber sehr
rechenaufwändig ist, reicht mein AVR nicht mehr, welchen Controller
könnt ihr empfehlen?" Tja, und wenn dann plötzlich 107 Koordinaten
angefahren werden sollen, dann wundert sich der Heini, warum das jetzt
auf dem 100 Mal schnelleren ARM wieder so lange dauert wie vorher auf
dem AVR...)
Εrnst B✶ schrieb:> Kevin schrieb:>> 1) Problemstellung vereinfachen>> Ok, also weniger "Reiseziele"... löst dann aber mein Problem nicht mehr
Mit dem TSP bringst du das beste Beispiel für 'Problemstellung
vereinfachen' gleich selbst: Da es für grosse n praktisch nicht lösbar
ist, wird man auf gute Heuristiken für Näherungslösungen zurückgreifen.
Obwohl die Problemstellung damit von 'perfekte Lösung' auf 'Näherung'
stark vereinfacht wurde, wird man in der Praxis voll und ganz zufrieden
sein.
Diese Punkte 1-6 kommen mir ein bisschen vor wie SW-Optimierung in a
Nutshell für BWLer. Sie sind sicher nicht falsch, aber helfen tun sie
auch nicht wirklich ;)
Und das Profiler anscheinend bei manchen verpöhnt sind, finde ich schon
auch seltsam. Klar kann ich Doku wälzen und mir Gründe überlegen, aber
das Bauchgefühl ignoriert meistens Amdahls Law und das Problem, dass ein
Redesign from Scratch bei den meisten Workflows/Deadlines eh nicht drin
ist. Wenn das so einfach wäre, hat bei der Spec und weiteren Feinplanung
eh schon jemand massiv geschlampt.
Einmal einen Profiler drüberlaufen lassen und man hat KONKRETE und
belastbare Zahlen, WO man mit dem genaueren Nachdenken anfangen sollte.
Und die diversen Effekte, die inzwischen mit den Cache-Sttrukturen und
Multicores auftreten und ein Programm locker mal auf 1% runterbremsen
können, kann man ohne Profiling eh nicht eingrenzen können.
Volker Zabe schrieb:> d) - Integer stat Float verwenden> - Daten im Speicher halten (nicht immer neu lesen)
dabei sollte man aber auch die speicherhierarchie im kopf behalten - der
cache- und arbeitsspeicher ist nun mal begrenzt, und daten, die auf die
festplatte ausgelagert wurden dauern auch länger zum laden.
> - Zeiger stat Index
autsch -> wenn jemand selbst an den pointern herumschraubt sinken die
chancen drastisch, dass der compiler z.b. array-zugriffe optimieren
kann. in einer lehrveranstaltung an der uni haben wir mal ein experiment
gemacht, bei dem ein simpler algorithmus (ich glaube sowas wie matrix
rotation - weiß es nicht mehr genau) vom compiler optimiert wurde. die
version mit pointern war um längen LANGSAMER als die direkten
array-zugriffe.
Volker Zabe schrieb:> - Schleifen entrollen
macht auch nur Sinn, wenn man stark unterbesetzte Matrizen hat.
In der Regel sollte man auch dies dem Compiler überlassen.
> In der Regel sollte man auch dies dem Compiler überlassen.
Ja, es ist oft erstaunlich, wie wenig bis gar nichts manuelle
Optimierungen in dem Bereich bringen, das können Compiler (selbst der
gcc) inzwischen deutlich besser. Dasselbe gilt fürs Prefetching. Ausser
in ganz abstrusen Fällen kann der gcc das besser, das Bauchgefühl
täuscht da sehr oft.
Wo der Mensch (und Fortran, örks) einen Vorteil hat, ist zB. bei dem
Aliasingproblem. Bei C kann der Compiler nicht allgemein wissen, ob zwei
Pointer auf denselben Speicher zeigen oder nicht, das kann durchaus
einige Optimierungen erlauben. Gibt noch so ein paar andere Fälle, wo
Metawissen hilft...
Und wer C++ macht, sollte auch mal schauen, ob er da mit = überflüssige
Objekte produziert. Abstrahierung ist schön und gut, aber manchmal
nervig ;)
Bei dem Code einer durchaus schön geschriebenen, aber algorithmisch doch
recht komplexen industriellen Bilderkennung waren da so unscheinbare
"a_old=a"-Einzeiler drin, weil der alte Wert von a später (nach einer
potentiellen Veränderung) nochmal gebraucht wurde. Allerdings hingen an
dem a dann dank OO so einige 10MB Memberdaten dran, die immer fleissig
kopiert wurden, selbst wenn sie nachher doch nicht gebraucht wurden.
Vom Codeanschauen ist das in den >10k LOC völlig untergangen, Profiling
hats ans Tageslicht gebracht. Das "on-demand"-Kopieren hat AFAIR allein
so 10-20% gebracht.
Georg A. schrieb:> Vom Codeanschauen ist das in den >10k LOC völlig untergangen, Profiling> hats ans Tageslicht gebracht.
Psst.
Sei vorsichtig. Gleich kommt Kevin und erzählt dir, dass du doch besser
anstelle des O(irgendwas) umkopierens besser eines mit O(n) genommen
hättest. Den Profilen brauchen echte Profis nicht. Die wissen wo der
Schuh drückt und ersetzen einen Travelling Salesmann durch eine
Approximation. Selbst dann wenn das n nicht größer als 5 oder 10 wird
und auch nie größer werden wird. Das 80% der Laufzeit auf
Datenbankzugriffe drauf gehen, interessiert nicht. Hauptsache der TS
wird in der Komplexität gedrückt.
Sorry. Konnte nicht widerstehen.
Aber wenn jemand sagt, Optimierung beginnt nicht damit, dass man zuerst
mal analysiert wo denn eigentlich der Schuh drückt, dann gibt mir das
lange zu denken.
Karl heinz Buchegger schrieb:> Aber wenn jemand sagt, Optimierung beginnt nicht damit, dass man zuerst> mal analysiert wo denn eigentlich der Schuh drückt, dann gibt mir das> lange zu denken.
Wenn du über solche Aussagen lange nachdenkst, solltest du etwas
optimieren.
Klaus Wachtler schrieb:>> mal analysiert wo denn eigentlich der Schuh drückt, dann gibt mir das>> lange zu denken.>> Wenn du über solche Aussagen lange nachdenkst, solltest du etwas> optimieren.>
ich denke, karl heinz gibt eher die ignoranz/dummheit mancher menschen
zu denken - wie einstein schon sagte "... beim universum bin ich mir
nicht sicher"
