Laufzeit von Algorithmen abschätzen

Gast #4770520
Ziel:
Vgl. von Algorithmen

Möglichkeit:
(O-Notation), Bench Mark

Beispiel:
Sortieralgorithmen

Vorgehen:
- Umsetzung Alg. A, Alg. B in Standard C (Zielprozessor: DSP)
- Ausführung der Alg. A und B auf Standard CPU.
- Bestimmung der Laufzeit.

Frage:
- Entwicklungsumgebung? (Dev-C++, ...)
- Ergebnisse aussagekräftig?
- Alternativen?
Gast #4770545
- Bietet sich für den Vgl. eine bestimmte Entwicklungsumgebung an? (das 
Betriebssystem und Prozesse im Hintergrund sollen das Ergebnis nicht 
stark beeinflussen)
- Ist das Vorgehen nachvollziehbar bzw. führt es auf ein 
aussagekräftiges/allgemeingültiges Ergebnis?
- Gibt es Alternativen zum vorgeschlagenen Vorgehen?
#4770563
Die Analyse der Eigenschaften und Struktur der Eingabedaten hilft 
ungemein, e.g., es kommen nur dünnbesetzte Matrizen vor. In deinem 
Beispiel von Sortieralgorithmen kann man mit O-Notation arbeiten, wenn 
man an dem Worst-case interessiert ist, oder man überlegt sich, dass das 
Array aus vorhergehender Rechnung schon zu 90% sortiert ist, dann 
interessiert einem der Worst-case nicht mehr so wirklich.

Auf dem System spielt auch die Kompetenz des Programmierers eine Rolle, 
also man kommt um den direkten Vergleich diverser zur Verfügung 
stehender Implementierungen auf den konkreten Daten nicht herum.
Gast #4770617
WiInfor schrieb:
> - Bietet sich für den Vgl. eine bestimmte Entwicklungsumgebung an?

Diejenige, die Du am besten beherrscht. Muß nur für alle 
Implementationen exakt dieselbe sein, bis hin zur identischen 
Compilerversion und Compileroptionen.

Ach ja, und bei Quicksort nicht den C-Library-qsort nehmen, weil der für 
jeden Vergleich und jeden Tausch einen extra Funktionsaufruf machen muß, 
der nicht inlined werden kann, so daß das Ergebnis dann verzerrt wird.

> (das
> Betriebssystem und Prozesse im Hintergrund sollen das Ergebnis nicht
> stark beeinflussen)

Unter Linux kannste Dir die reine CPU-Zeit ausgeben lassen, die Dein 
Prozeß verbraucht hat. Damit sind Betriebssystem und andere laufende 
Anwendungen egal.

> - Ist das Vorgehen nachvollziehbar

Finde ich schon.

> bzw. führt es auf ein
> aussagekräftiges/allgemeingültiges Ergebnis?

Nicht unbedingt. Denn wie "gut" Algorithmen sind, hängt von einigen 
Randbedingungen ab:

- Welche Größenordnung der Listenlänge ist von Interesse?
Beispielsweise ist Quicksort bei kurzen Listen (unter 100) schlecht, 
weil der Overhead zu stark ist.
Die O-Notation ist nur von Belang für große Listenlängen und drückt im 
Wesentlichen nicht aus, wie schnell ein Algorithmus ist, sondern wie gut 
er mit wachsender Listenlänge skaliert. Der konstante Faktor, der bei 
der O-Notation weggelassen wird, ist für verschiedene Algorithmen 
nämlich auch unterschiedlich.

- Wie ist der Aufwand eines Vergleiches im Verhältnis zu einem Tausch?
Es gibt Algorithmen, die möglichst wenig Tauschaktionen machen, dafür 
aber mehr Vergleiche. Das rechnet sich nur, wenn der Tausch wirklich 
aufwendiger ist.
Also beispielsweise, wenn die Elemente sagen wir mal structs mit 64 Byte 
sind, während der Vergleichsschlüssel nur ein 4 Byte Integer ist.
Hast Du hingegen als Elemente eine Union aus einem 4-Byte-Integer, den 
Du auf einen Schlag kopieren kannst, und der Vergleichsschlüssel ist 
eines der Bytes der Union, dann ist ein Vergleich genauso aufwendig wie 
ein Tausch.

- Was auch noch berücksichtigt werden sollte: Braucht der Algorithmus 
zusätzlichen Speicherplatz (temporäres Array oder, wie Quicksort, 
impliziten Stack)? Wenn ja, wieviel? Wie sind die Schwankungen der 
Laufzeit? Gibt es da gelegentlich fiese Ausreißer? Beispielsweise hat 
Heapsort eine extrem konstante Laufzeit, ist allerdings langsamer als 
Shellsort (bei kurzen Listen zumindest). Umgedreht ist Quicksort 
schwierig so zu implementieren, daß er nicht in seltenen Randfällen 
pathologische Ausreißer zeigt.

Gemessen werden sollte auf jeden Fall immer die Sortierzeit mit bereits 
vorsortierter Liste, mit invers vorsortierter Liste und mit 
Zufallszahlen. Die Zufallszahlen müssen dann aber für jeden Algorithmus 
dieselben sein. Also die zufällige Liste nach der Erzeugung einmal 
wegspeichern. Außerdem nicht nur eine Messung mit Zufallsliste machen, 
sondern viele.

Auch interessant ist, was passiert, wenn viele doppelte Einträge 
vorhanden sind. Im Extremfall 95% Nullen und nur 5% eigentlich 
ausgefüllte Felder.

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 10 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.