Warum Vergleiche anstelle von Laufzeit verwenden, um zwei Algorithmen zu vergleichen?

Ich stelle fest, dass in einigen CS-Forschungsarbeiten zum Vergleich der Effizienz von zwei Algorithmen die Gesamtzahl der Schlüsselvergleiche in den Algorithmen verwendet wird und nicht die tatsächlichen Rechenzeiten selbst. Warum können wir nicht vergleichen, welches Programm besser ist, indem wir beide Programme ausführen und die Gesamtzeit für die Ausführung der Algorithmen zählen?

Dies ist eigentlich ein tiefes Thema, das einige methodische und einige pragmatische Antworten hat. Ich gehe davon aus, dass Sie etwas über die verfügbaren Algorithmen wissen möchten . Wenn Sie wissen möchten, welcher Algorithmus auf einem bestimmten Computer mit bestimmten Eingaben besser funktioniert, messen Sie die Laufzeiten. Wenn Sie die Qualität eines Compilers für einen bestimmten Algorithmus vergleichen möchten, messen Sie die Laufzeiten. Tun Sie es nicht, um etwas über den Algorithmus zu lernen.

Lassen Sie mich zunächst einige Gründe nennen, warum die Verwendung von Laufzeiten keine gute Idee ist.

1. Allgemeines
   Laufzeiten, die mit einer Sprache und einem Compiler auf einem Computer gemessen werden, haben wenig Bedeutung, wenn Sie eine Komponente ändern. Selbst geringfügig unterschiedliche Implementierungen desselben Algorithmus können unterschiedlich ausgeführt werden, da Sie eine gewisse Compileroptimierung in Einzelfällen auslösen, in den anderen jedoch nicht.
2. Vorhersage
   Sie haben also einige Laufzeiten für einige Eingaben. Was sagt das über die Laufzeit einer anderen Eingabe aus? Im Allgemeinen nichts.
3. Bedeutung
   Normalerweise werden Sie nicht alle Eingaben (von einer bestimmten Größe) einem Benchmarking unterziehen, sodass Sie die Möglichkeit zum Vergleichen von Algorithmen sofort einschränken: Hat Ihr Testsatz möglicherweise den schlechtesten und den besten Fall im anderen Algorithmus ausgelöst? Oder Ihre Eingaben waren zu klein, um das Laufzeitverhalten aufzuzeigen .
4. Zumessen
   Messlaufzeiten und ist nicht trivial. Gibt es eine GEG? Hat es Streit gegeben, dh zählen Sie die Zeit, die der Algorithmus nicht einmal ausgeführt hat? Können Sie genau denselben Maschinenzustand für einen anderen Durchlauf (des anderen Algorithmus) reproduzieren, insbesondere für gleichzeitige Prozesse und Caches? Wie wird mit Speicherlatenz umgegangen?

Ich hoffe, diese haben Sie überzeugt, dass Laufzeiten ein schreckliches Maß für den Vergleich von Algorithmen sind und dass eine allgemeine, abstrakte Methode zur Untersuchung der Laufzeit von Algorithmen erforderlich ist.

Weiter zum zweiten Teil der Frage. Warum verwenden wir Vergleiche oder ähnliche elementare Operationen?

1. Analytische Nachvollziehbarkeit
   Angenommen, Sie möchten eine formale Analyse durchführen, müssen Sie dazu in der Lage sein . Das Zählen einzelner Aussagen ist sehr technisch, manchmal sogar schwierig. manche Leute machen es trotzdem (zB Knuth). Es ist einfacher, nur einige Anweisungen zu zählen, die die Laufzeit dominieren . Aus dem gleichen Grund untersuchen wir oft "nur" (obere Schranken) die Worst-Case-Laufzeit.

2. Dominanz
   Die ausgewählte Operation dominiert die Laufzeit. Das bedeutet nicht, dass es die meiste Laufzeit beiträgt - Vergleiche, z. B. in Quicksort, wenn Ganzzahlen in Wortgröße sortiert werden, sind dies eindeutig nicht. Sie werden jedoch am häufigsten ausgeführt. Wenn Sie sie also zählen, bestimmen Sie, wie oft die am häufigsten ausgeführten Teile des Algorithmus ausgeführt werden. Folglich ist Ihre asymptotische Laufzeit proportional zur Anzahl der dominanten Elementaroperationen. Aus diesem Grund verwenden wir gerne die Landau-Notation und das Wort "Laufzeit", obwohl wir nur Vergleiche zählen.

Beachten Sie, dass es nützlich sein kann, mehr als eine Operation zu zählen. Zum Beispiel führen einige Quicksort-Varianten mehr Vergleiche durch, aber weniger Swaps als andere (im Durchschnitt).

Wenn Sie die gesamte Theorie durchgearbeitet haben, möchten Sie möglicherweise die Laufzeiten erneut überprüfen, um sicherzustellen, dass die in Ihrer Theorie enthaltenen Vorhersagen stichhaltig sind. Wenn dies nicht der Fall ist, ist Ihre Theorie (in der Praxis) nicht nützlich und muss erweitert werden. Die Speicherhierarchie ist eines der ersten Dinge, die Sie für wichtig halten, die jedoch in grundlegenden Analysen fehlen.

Dies liegt daran, dass die Gesamtlaufzeit der Algorithmen neben anderen Faktoren von der Hardware abhängt, auf der sie ausgeführt werden. Es ist nicht zuverlässig, zwei Algorithmen zu vergleichen, wenn einer auf einem Pentium 4 und der andere auf einem Core i7 ausgeführt wird. Angenommen, Sie haben beide auf demselben Computer ausgeführt. Was ist zu sagen, dass beide die gleiche Prozessorzeit haben? Was passiert, wenn ein anderer Prozess eine höhere Priorität hat als der Prozess des einen der Algorithmen?

Um dies zu überwinden, entkoppeln wir diese Gesamtzeit zum Abschluss und vergleichen stattdessen basierend darauf, wie gut der Algorithmus skaliert. Möglicherweise haben Sie Notationen wie O (1) oder O (n ^ 2) in den Forschungsarbeiten bemerkt. Dies kann etwas mehr Lesen erfordern, wenn Sie an der Big O-Notation interessiert sind .

Da die anderen Antworten erklären, warum wir die Laufzeit in Bezug auf die Anzahl der Elementaroperationen analysieren, möchte ich einige Gründe für die Gründe für Vergleiche nennen die richtige Metrik für viele (nicht alle) Sortieralgorithmen sind:

• Bei vielen Sortieralgorithmen dominiert die Anzahl der Vergleiche die Laufzeit, dh es werden mindestens so viele Vergleiche durchgeführt wie bei jeder anderen Elementaroperation
• vergleiche sind die teuren Operation; Überlegen Sie, wie eine Sortierroutine in der Bibliothek implementiert ist: Der Sortierfunktion wird ein Array von Elementen und ein Zeiger auf eine Funktion übergeben, die zwei Elemente vergleicht. Im Allgemeinen ist das Aufrufen und Warten auf die Ausführung der Vergleichsfunktion teurer als "interne" Operationen. Da diese Funktion vom Benutzer bereitgestellt wird, ist es schwieriger, sie zu optimieren
• (Dies kann für manche ein guter Grund sein oder auch nicht). Wir können etwas Interessantes über die Anzahl der Vergleiche sagen , die ausreichen und zum Sortieren einer Sequenz erforderlich sind. Wir wissen, wie man dies im schlimmsten Fall und im Durchschnitt für verschiedene Distributionen macht, selbst wie man einen Algorithmus entwirft, der optimal konvergiert, wenn er mit Elementen ausgeführt wird, die aus einer unbekannten Distribution abgetastet wurden ( selbstverbessernde Algorithmen ). wir wissen, wie das geht, wenn einige Vergleiche kostenlos sind ( Sortieren mit Teilinformationen )