Ich bin kein professioneller Programmierer und studiere es nicht. Ich bin ein Student der Luft- und Raumfahrt und habe eine numerische Methode für meine Diplomarbeit gemacht und auch ein Programm programmiert, um zu beweisen, dass es funktioniert.
Ich machte mehrere Methoden und implementierte mehrere Algorithmen und versuchte, die Beweise zu zeigen, warum verschiedene Situationen ihren eigenen Algorithmus brauchten, um die Aufgabe zu lösen.
Ich habe diesen Beweis mit einem mathematischen Ansatz gemacht, aber einige Algorithmen waren so spezifisch, dass ich weiß, was sie tun und sie machen es richtig, aber es war sehr schwer eine mathematische Funktion oder etwas zu finden, um zu zeigen, wie viele Iterationen oder Schleifen es muss tun, bis es fertig ist.
Ich würde gerne wissen, wie Sie diesen Vergleich machen. Stellen Sie auch eine mathematische Funktion vor, oder machen Sie nur einen Geschwindigkeitstest beider Algorithmen, und wenn Sie es mathematisch tun, wie tun Sie das? Lernst du das während deines Studiums oder wie?
Vielen Dank im Voraus, Andreas
Die Standardmethode zum Vergleichen verschiedener Algorithmen besteht im Vergleichen ihrer Komplexität mit der Big O -Notation. In der Praxis würden Sie natürlich auch die Algorithmen benchmarken.
Als ein Beispiel haben die Sortieralgorithmen Bubble-Sort und Heap-Sort die Komplexität O (n 2 ) und O (n log n)
Als abschließende Anmerkung ist es sehr schwierig, repräsentative Benchmarks zu erstellen, siehe diesen interessanten Beitrag von Christer Ericsson zum Thema .
Während die Groß-O-Notation Ihnen die Möglichkeit bietet, einen schrecklichen Algorithmus von einem vernünftigen Algorithmus zu unterscheiden, wird Ihnen nur eine bestimmte Definition der Rechenkomplexität vermittelt. In der realen Welt wird dies nicht erlauben, zwischen zwei Algorithmen zu wählen, denn:
1) Zwei Algorithmen in der gleichen Größenordnung, nennen wir sie f und g , beide mit O(N^2) Komplexität können sich in Laufzeit um mehrere Größenordnungen unterscheiden. Die Big-O-Notation misst nicht die Anzahl der einzelnen Schritte, die mit jeder Iteration verbunden sind. Daher kann f 100 Schritte ausführen, während g 10 dauert.
Außerdem können verschiedene Compiler oder Programmiersprachen mehr oder weniger Befehle für jede Iteration des Algorithmus generieren, und feine Wahlmöglichkeiten in der Beschreibung des Algorithmus können dazu führen, dass Cachespeicher oder CPU-Hardware 10 bis 1000 mal schlechter arbeiten, ohne sie zu ändern die große O-Reihenfolge oder die Anzahl der Schritte!
2) Ein Algorithmus O(N) könnte einen Algorithmus O(log(N)) übertreffen
Die Big-O-Notation misst nicht die Anzahl der einzelnen Schritte, die mit jeder Iteration verbunden sind. Wenn also O(N) 100 Schritte benötigt, aber O(log(N)) 1000 Schritte für jede Iteration benötigt, dann für Datensätze bis zu einer bestimmten Größe O(N) wird besser sein.
Die gleichen Probleme gelten für Compiler wie oben.
Die Lösung besteht darin, eine erste mathematische Analyse der Big-O-Notation durchzuführen, gefolgt von einem Benchmark-gesteuerten Performance-Tuning-Zyklus unter Verwendung von Zeit- und Hardware-Performance-Zählerdaten sowie einer guten Portion Erfahrung.
Zuerst müsste man definieren, welche effizienteren Mittel, dh schneller, weniger Systemressourcen (wie Speicher) usw. verwendet werden (diese Faktoren schließen sich manchmal gegenseitig aus)
Im Hinblick auf Standarddefinitionen der Effizienz würde man oft Big-0 Notation verwenden, jedoch in der "realen Welt" Außerhalb der Wissenschaft würde man normalerweise beide Gleichungen profilieren / benchmarken und dann die Ergebnisse vergleichen
Es ist oft schwierig, allgemeine Annahmen über die Big-0-Notation zu treffen, da es hauptsächlich um Schleifen geht und feste Kosten für den Code innerhalb einer Schleife annimmt, daher wäre ein Benchmarking der bessere Weg
Ein Nachteil, auf den Sie achten sollten, ist, dass das Ergebnis manchmal stark variieren kann, je nachdem, mit welcher Datasetgröße Sie arbeiten - für kleine N in einer Schleife wird man manchmal nicht viel Unterschied finden.
Sie könnten leicht aussteigen, wenn es einen signifikanten Unterschied in der asymptotischen Big-O-Komplexitätsklasse für den schlimmsten Fall oder für den erwarteten Fall gibt. Selbst dann müssen Sie zeigen, dass die versteckten konstanten Faktoren den "besseren" (aus der asymptotischen Perspektive) Algorithmus für Eingaben mit vernünftiger Größe nicht langsamer machen.
Wenn der Unterschied nicht groß ist, dann ist das Benchmarking mit verschiedenen Datensätzen angesichts der Komplexität der heutigen Computer der einzig richtige Weg. Sie können nicht einmal das gesamte verschachtelte Zusammenspiel berücksichtigen, das aus der Genauigkeit der Verzweigungsvorhersage, den Trefferraten von Daten und Code-Caches, Sperrkonflikten usw. stammt.
Laufgeschwindigkeitstests werden Ihnen keine so gute Antwort liefern wie die Mathematik. Ich denke, Ihr Ansatz ist korrekt - aber vielleicht lassen Sie Ihre Erfahrung und Ihr breites Wissen bei der Analyse Ihrer Algorithmen im Stich. Ich empfehle das Buch "Konkrete Mathematik" von Knuth und anderen, aber es gibt viele andere gute (und noch mehr nicht gute) Bücher, die das Thema Analysieren von Algorithmen behandeln. Ja, das habe ich während meines Studiums gelernt.
Nachdem Sie all dies geschrieben haben, wird die meiste algorithmische Komplexität im Hinblick auf die Ausführungszeit im schlimmsten Fall analysiert (so genanntes big-O) und es ist möglich, dass Ihre Datensätze nicht an die schlimmsten Fälle heranreichen run kann eher Ihre tatsächliche Leistung als die theoretische Leistung des Algorithmus beleuchten. Also sind Tests nicht ohne ihren Wert. Ich würde jedoch sagen, dass der Wert gegenüber dem der Mathematik zweitrangig ist, was Ihnen keine unnötigen Kopfschmerzen bereiten sollte.
Das kommt darauf an. An der Universität lernt man, Algorithmen zu vergleichen, indem man die Anzahl der Operationen berechnet, die es ausführt, abhängig von der Größe / dem Wert seiner Argumente. (Vergleichen Analyse von Algorithmen und große O-Notation ). Ich würde von jedem anständigen Programmierer verlangen, die Grundlagen zumindest zu verstehen.
In der Praxis ist dies jedoch nur für kleine Algorithmen oder kleine Teile größerer Algorithmen nützlich. Sie werden Schwierigkeiten haben, dies beispielsweise für einen Parsing-Algorithmus für ein XML-Dokument zu berechnen. Aber wenn man die Grundlagen kennt, kann man keine braindead-Fehler machen - siehe zum Beispiel Joel Spolskys amüsanten Blogeintrag "Back to the Basics ".
Wenn Sie ein größeres System haben, werden Sie Algorithmen entweder durch erratenes Raten vergleichen, Zeitmessungen durchführen oder die problematischen Stellen in Ihrem System finden, indem Sie ein Profiling-Tool . Meiner Erfahrung nach ist das selten so wichtig - der Kampf um die Komplexität des Systems hilft mehr.
Um Ihre Frage zu beantworten: "Stellen Sie auch eine mathematische Funktion vor oder führen Sie nur einen Geschwindigkeitstest beider Algorithmen durch."
Ja zu beiden - fassen wir zusammen.
Die oben diskutierte "Big O" -Methode bezieht sich auf die Worst-Case-Leistung wie oben erwähnt. Der "Speedtest", den Sie erwähnen, wäre eine Möglichkeit, die "durchschnittliche Fallleistung" zu schätzen. In der Praxis kann es einen großen Unterschied zwischen der Leistung im schlechtesten Fall und der durchschnittlichen Fallleistung geben. Deshalb ist Ihre Frage interessant und nützlich.
Worst-Case-Performance ist die klassische Methode zur Definition und Klassifizierung von Algorithmen. In jüngerer Zeit beschäftigte sich die Forschung mehr mit der durchschnittlichen Fallleistung oder mit genaueren Leistungsgrenzen wie: 99% der Probleme erfordern weniger als N Operationen. Sie können sich vorstellen, warum der zweite Fall für die meisten Probleme viel praktischer ist.
Abhängig von der Anwendung haben Sie möglicherweise sehr unterschiedliche Anforderungen. Eine Anwendung erfordert möglicherweise eine Reaktionszeit von weniger als 3 Sekunden in 95% der Zeit - dies würde zur Definition von Leistungsgrenzen führen. Ein anderer könnte eine Leistung erfordern, die NIEMALS 5 Sekunden überschreitet - dies würde zur Analyse der Worst-Case-Leistung führen.
In beiden Fällen wird dies an der Universität oder auf der Ebene der Oberstufe gelehrt. Jeder, der neue Algorithmen entwickelt, die in Echtzeitanwendungen verwendet werden, sollte etwas über den Unterschied zwischen der Durchschnittsleistung und der Worst-Case-Leistung erfahren und sollte auch darauf vorbereitet sein, Simulationen und Analysen der Algorithmusleistung als Teil eines Implementierungsprozesses zu entwickeln.
Hoffe, das hilft.
Die große O-Notation gibt Ihnen die Komplexität eines Algorithmus im schlimmsten Fall und ist hauptsächlich nützlich, um zu wissen, wie der Algorithmus in der Ausführungszeit wächst, wenn die Menge der Daten, die verarbeitet werden müssen, größer wird. Zum Beispiel (C-Stil-Syntax, das ist nicht wichtig):
%Vor% Also, in asymptotischer Notation, wird es Kosten von O(n log n) (nicht so effizient) haben, was in diesem Beispiel ein vernünftiges Ergebnis ist, aber nimm dieses Beispiel:
Gleicher Algorithmus, aber mit einer kleinen neuen Zeile mit einer Bedingung. In diesem Fall wählt die asymptotische Notation den schlechtesten Fall und wird die gleichen Ergebnisse wie oben in O(n log n) ziehen, wenn leicht feststellbar ist, dass der (3) Schritt nur die Hälfte der Zeiten ausführt.
Daten und so sind nur Beispiele und möglicherweise nicht genau, nur um das Verhalten der Big-O-Notation zu veranschaulichen. Es gibt Ihnen hauptsächlich das Verhalten Ihres Algorithmus, wenn Daten aufkommen (Ihr Algorithmus wird linear, exponentiell, logarithmisch, ... sein), aber das ist nicht, was jeder als "Effizienz" kennt, oder fast, das ist nicht das einzige " Effizienz "bedeutet.
Allerdings kann dieser Methot "unmögliche Prozesse" (Entschuldigung, ich kenne nicht das genaue englische Wort) Algoritmen erkennen, das sind Algorithmen, die eine riesige Menge an Zeit benötigen, um in ihren frühen Schritten verarbeitet zu werden Fakultäten zum Beispiel oder sehr große matix).
Wenn Sie eine echte Welt-Effizienz-Studie wollen, möchten Sie vielleicht lieber einige Daten aus der realen Welt aufspüren und mit diesen Daten einen realen Maßstab für den Wert Ihres Algorithms bilden. Es ist kein mathematischer Stil, aber es wird in der Mehrzahl der Fälle genauer sein (aber nicht im schlimmsten Fall!;)).
Hoffe, das hilft.
Unter der Annahme, dass Geschwindigkeit (nicht Speicher) Ihr Hauptanliegen ist, und unter der Annahme, dass Sie eine empirische (nicht theoretische) Methode zum Vergleichen von Algorithmen wünschen, würde ich vorschlagen, dass Sie mehrere Datensätze mit unterschiedlicher Größe um drei Größenordnungen vorbereiten. Führen Sie dann jeden Algorithmus für jeden Datensatz aus, takten Sie sie und zeichnen Sie die Ergebnisse auf. Die Form der Zeit-gegen-Datensatz-Größenkurve jedes Algorithmus gibt eine gute Vorstellung von seiner großen O-Leistung.
Wenn die Größe Ihrer Datensätze in der Praxis bekannt ist, ist ein Algorithmus mit besserer O-Leistung nicht unbedingt schneller. Um zu bestimmen, welcher Algorithmus für eine bestimmte Datasetgröße schneller ist, müssen Sie die Leistung jedes einzelnen so lange optimieren, bis es "so schnell wie möglich" ist, und dann sehen, welcher davon gewinnt. Performance-Tuning erfordert Profiling oder Single-Stepping auf der Anweisungsebene oder meine Lieblings-Technik, Stackshots .
Wie andere zu Recht angemerkt haben, ist es üblich, die große O-Notation zu verwenden.
Aber das große O ist nur gut, solange Sie die Verarbeitung von Algorithmen in Betracht ziehen, die klar definiert und definiert sind (z. B. eine Blasensortierung).
Wenn andere Hardware-Ressourcen oder andere parallel laufende Running-Software ins Spiel kommen, kommt der Teil namens Engineering ins Spiel. Die Hardware unterliegt Einschränkungen. Speicher und Datenträger sind begrenzte Ressourcen. Die Festplattenleistung hängt sogar von den beteiligten Mechanismen ab.
Ein Betriebssystem-Scheduler unterscheidet beispielsweise zwischen I / O-gebundenen und CPU-gebundenen Ressourcen, um die Gesamtleistung für eine bestimmte Anwendung zu verbessern. Ein DBMS berücksichtigt das Lesen und Schreiben von Platten, die Speicher- und CPU-Nutzung und sogar die Vernetzung im Fall von Clustern.
Diese Dinge sind schwer mathematisch zu beweisen, aber sie können oft leicht mit einer Reihe von Nutzungsmustern verglichen werden.
Ich denke also, die Antwort lautet, dass Entwickler sowohl theoretische Methoden wie Big O als auch Benchmarking verwenden, um die Geschwindigkeit von Algorithmen und deren Implementierung zu bestimmen.
Dies wird normalerweise mit großer O-Notation ausgedrückt. Grundsätzlich wählen Sie eine einfache Funktion (wie n 2 , wobei n die Anzahl der Elemente ist), die die tatsächliche Anzahl der Iterationen dominiert.
Tags und Links algorithm math performance comparison