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

19

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?

hat
quelle
Herzlich willkommen! Ich hoffe, dass die meisten Papiere keine Laufzeiten verwenden. Ich weiß jedoch, dass einige dies tun, insbesondere in den eher angewandten Communities und wenn die betrachteten Systeme sehr komplex sind.
Raphael

Antworten:

14

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.

Raphael
quelle
1
Beachten Sie, dass die formale Analyse auch ihre Grenzen hat. Beispielsweise ist der Durchschnittsfall für ungleichmäßige Eingangsverteilungen oftmals unlösbar.
Raphael
10

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 .

Chris Howell
quelle
1
Die tatsächliche Laufzeit hängt auch von der Größe und dem Inhalt der tatsächlichen Eingabe ab, die zum Ausführen der Algorithmen verwendet wird!
Tsuyoshi Ito
7

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 )
Sasho Nikolov
quelle
1) "Es werden mindestens so viele Vergleiche durchgeführt wie bei jeder anderen Elementaroperation" - nur bis zu einem konstanten Faktor. 2) "Vergleiche sind die teure Operation" - das setzt eine generische Einstellung voraus. Bei der Integer-Sortierung (die normalerweise analysiert wird) sind Swaps in der Regel teurer.
Raphael
sicher. op schien über die Analyse von Algorithmen im Allgemeinen verwirrt zu sein, wollte keine konstanten Faktoren bringen. Ich hoffe, die Tatsache, dass ich über eine generische Einstellung spreche, wird aus der Beschreibung deutlich - die Sortierroutine in einer Standardbibliothek ist keine Ganzzahlensortierung
Sasho Nikolov
plus die Papiere, die op sah, sind definitiv nicht über spezialisierte Ganzzahl-Sortieralgorithmen, es gibt niemanden, der die Anzahl der Vergleiche zählt
Sasho Nikolov
@Raphael Das Sortieren kleiner Ganzzahlen ist in der Praxis kein alltägliches Problem. Ich wette, dass die meisten Sortierungen auf der Welt auf Saiten (von der einen oder anderen Länge ) stattfinden. Selbst bei der Ganzzahlsortierung bin ich mir nicht sicher, ob es richtig ist, dass Auslagerungen teurer sind - Verzweigungen sind auf einem modernen High-End-Prozessor relativ teuer, da die Verzweigungsvorhersage beim Sortieren meistens unbrauchbar wäre.
Gilles 'SO - hör auf böse zu sein'
@ Gilles Swaps sind an sich teurer als Ganzzahlvergleiche als jede mir bekannte Plattform. "Nebenkosten" wie zB Branchenfehler sind definitiv ein Faktor, dessen Auswirkungen Gegenstand laufender Forschung sind. (In Bezug auf die Verwendung in der Praxis kann ich keine qualifizierte Aussage machen. Ich beobachte jedoch, dass Standardbibliotheksbetreuer die Sortieralgorithmen, die sie für primitive Datentypen verwenden, ständig verbessern, sodass ich davon ausgehe, dass sie viel (ab) verwenden.)
Raphael