Forum: PC-Programmierung Laufzeit von Algorithmen abschätzen


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von WiInfor (Gast)


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

von Nop (Gast)


Bewertung
2 lesenswert
nicht lesenswert
Deine Frage ist jetzt konkret was?

von WiInfor (Gast)


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

von Thomas P. (thp)


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

von Nop (Gast)


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

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]
  • [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.