Schätzung der tatsächlichen (nicht theoretischen) Laufzeitkomplexität einer Implementierung

9

Jeder in der Informatik weiß, dass HeapSort in der Theorie der theoretisch schlimmste Fall ist, während QuickSort im schlimmsten Fall O(n log n) ist. In der Praxis wird jedoch ein gut implementiertes QuickSort (mit guten Heuristiken) HeapSort bei jedem einzelnen Datensatz übertreffen. Auf der einen Seite beobachten wir kaum den schlimmsten Fall und auf der anderen Seite z. CPU-Cache-Zeilen, Prefetch usw. machen bei vielen einfachen Aufgaben einen enormen Unterschied. Und während z.B. QuickSort kann vorsortierte Daten (mit einer guten Heuristik) in O(n^2) verarbeiten, HeapSort reorganisiert die Daten immer in O(n) , da die vorhandene Struktur nicht ausgenutzt wird.

Für mein Spielzeugprojekt caliper-analyze habe ich kürzlich Methoden zur Schätzung des < em> tatsächliche durchschnittliche Komplexität von Algorithmen aus Benchmark-Ergebnissen. Insbesondere habe ich Lawson und Hansons NNLS-Anpassung mit verschiedenen Polynomen versucht.

Allerdings funktioniert es noch nicht so gut. Manchmal bekomme ich brauchbare Ergebnisse, manchmal nicht. Ich denke, es kann helfen, größere Benchmarks zu machen, insbesondere mehr Parameter auszuprobieren.

Die folgenden Ergebnisse dienen zum Sortieren doppelter Objekte in einem SAW-Muster mit 10% Zufälligkeit. n war für diesen Lauf nur bis zu 500, daher ist es für die tatsächliche Verwendung nicht sehr repräsentativ ... Die Zahlen sind die geschätzte Laufzeitabhängigkeit von der Größe. Die Ausgabe wird manuell bearbeitet und manuell sortiert , so dass nicht angibt, was das Werkzeug derzeit bietet!

%Vor%

Sie können feststellen, dass die Ergebnisse in dieser speziellen Einstellung (oft überhaupt nicht zufriedenstellend) mit dem bekannten Verhalten weitgehend übereinstimmen: Bubble Sort ist sehr teuer und eine gute Heuristik auf QuickSort ist viel besser. B. QuickSort mit Median-von-drei-Heuristiken ergibt zum Beispiel eine Schätzung von O(n log n) , während die anderen QuickSorts als O(n + n^2)

geschätzt werden

So zu meinen aktuellen Fragen:

  • Kennst du Algorithmen / Ansätze / Werkzeuge, die eine Laufzeitkomplexitätsanalyse aus Benchmarkdaten durchführen, um vorherzusagen, welche Implementierung (wie oben zu sehen) für mich interessant ist, verschiedene Implementierungen der selben Algorithmus!) funktioniert am besten mit realen Daten?
  • Kennst du wissenschaftliche Artikel in diesem Zusammenhang (Schätzung der durchschnittlichen Komplexität von Implementierungen)?
  • Kennen Sie robuste Anpassungsmethoden, mit denen Sie hier genauere Schätzungen erhalten? Z.B. eine regulierte Version von NNLS.
  • Kennen Sie Faustregeln darüber, wie viele Proben Sie benötigen, um eine vernünftige Schätzung zu erhalten? (Wann sollte das Tool insbesondere keine Schätzung abgeben, da es ohnehin wahrscheinlich ungenau ist?)

Und lassen Sie mich noch einmal betonen, dass ich nicht an theoretischer Komplexität interessiert bin oder an formeller Analyse. Ich bin interessiert zu sehen, wie Implementierungen (von theoretisch sogar identischen Algorithmen) Benchmark-Daten auf realen CPUs durchführen ... die numerischen Faktoren für einen gemeinsamen Bereich sind für mich von großem Interesse, mehr als das asymptotische Verhalten . (und nein, auf die Dauer ist es nicht nur Zeitkomplexität und Sortierung. Aber ich interessiere mich für Indexstrukturen und andere Parameter. Und Messschieber kann zB auch Speicherverbrauch messen, wenn ich mich nicht täusche) Plus, ich bin Arbeiten in Java . Ein Ansatz, der nur einen eingebauten Matlab nennt, nützt mir nichts, da ich nicht in der Matlab-Welt lebe.

Wenn ich Zeit habe, werde ich versuchen, einige dieser Benchmarks mit einer größeren Auswahl an Größen erneut auszuführen, damit ich mehr Datenpunkte bekomme. Vielleicht wird es dann einfach funktionieren ... aber ich glaube, dass es robustere Regressionsverfahren gibt, mit denen ich auch aus kleineren Datensätzen bessere Schätzungen erhalten könnte. Außerdem würde ich gerne feststellen, wenn die Probe zu klein ist, um überhaupt eine Vorhersage zu treffen!

    
Erich Schubert 05.07.2013, 16:52
quelle

1 Antwort

2

Wenn Sie die tatsächliche Komplexität wünschen, messen Sie sie besser. Versuchen zu erraten, wie ein Programm ohne Messung funktioniert, ist sehr unzuverlässig.

Dasselbe Programm kann auf einer anderen Maschine sehr unterschiedlich arbeiten. z.B. Ein Algo könnte auf einer Maschine schneller sein, auf einer anderen langsamer.

Ihre Programme können langsamer sein, je nachdem, was die Maschine sonst noch macht. Ein Algo, der gut aussieht, aber Ressourcen wie Caches stark beansprucht, kann langsamer sein und andere Programme langsamer machen, wenn er diese Ressourcen teilen muss.

>

Das Testen eines Algo auf einer Maschine allein kann bis zu 2-5x schneller sein als der Versuch, es in einem echten Programm zu verwenden.

  

Kennen Sie Faustregeln darüber, wie viele Proben benötigt werden, um eine vernünftige Schätzung zu erhalten? (Wann sollte das Tool insbesondere keine Schätzung abgeben, da es ohnehin wahrscheinlich ungenau ist?)

Um ein Perzentil wie 90% oder 99% zu bestimmen, benötigen Sie 1 / (1-p) ^ 2, d. h. für 99% Kachel benötigen Sie nach dem Aufwärmen mindestens 10.000 Proben. Für 99,9% Kacheln benötigen Sie eine Million.

    
Peter Lawrey 05.07.2013 21:40
quelle