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?
- 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?
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.
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.
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.