www.mikrocontroller.net

Forum: PC-Programmierung Beschleunigung von Algorithmen, Quelle gesucht


Autor: Kevin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: MaWin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Kevin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: ich (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Kevin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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ö

Autor: Kevin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ich: Danke, du verstehst mich :-)
Ich werde mal versuchen, das Buch zu finden.

Kevin

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Kevin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: High Performer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Nico S. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Oliver R. (superberti)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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ß,

Autor: Simon Budig (nomis)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Kevin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sonst noch Beschwerden?

(Vielleicht hat Michael Mittermaier doch recht?)

Autor: Kevin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das war keine Beschwerde. Das war eine Danksagung an Karl Heinz.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 :-)

Autor: Nico S. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Sven H. (dsb_sven)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Autor: Bartli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
"Problem auf zwei Programme/Kerne/CPUs aufteilen/verteilen"

und damit wird ein Problem einfacher?

Autor: Loonix (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bartli schrieb:
> und damit wird ein Problem einfacher?

Beschleunigung von Algorithmen und Vereinfachung eines 
(Programmier-)Problems sind nach wie vor zwei Paar Stiefel.

Autor: Bartli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: hans (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Georg A. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: asdfghjklöä# (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: hans (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>     - Zeiger stat Index

Erkläre bitte mal, warum das schneller sein sollte. Es tut exakt das 
gleiche und das weiss auch der Compiler.

Autor: Vlad Tepesch (vlad_tepesch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Georg A. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: asdfghjklöä# (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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"

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das habe ich auch schon so verstanden.
Eben deshalb macht es mir Sorgen, wenn er genau an diese Leute
seine Lebenszeit vergeudet.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.