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

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!

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)

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!