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ö
@ich: Danke, du verstehst mich :-) Ich werde mal versuchen, das Buch zu finden. Kevin
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.
Sonst noch Beschwerden? (Vielleicht hat Michael Mittermaier doch recht?)
Das war keine Beschwerde. Das war eine Danksagung an Karl Heinz.
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!
"Problem auf zwei Programme/Kerne/CPUs aufteilen/verteilen" und damit wird ein Problem einfacher?
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.
> - Zeiger stat Index
Erkläre bitte mal, warum das schneller sein sollte. Es tut exakt das
gleiche und das weiss auch der Compiler.
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"
Das habe ich auch schon so verstanden. Eben deshalb macht es mir Sorgen, wenn er genau an diese Leute seine Lebenszeit vergeudet.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.