Gibt es eine Methode zur automatischen Laufzeitanalyse von Algorithmen?

10

Ich frage mich, gibt es eine Methode zur automatischen Laufzeitanalyse, die zumindest für eine relevante Teilmenge von Algorithmen funktioniert (Algorithmen, die analysiert werden können)?

Ich googeln „Automatische Algorithmus Analyse“ , die mir gegeben haben dies aber es ist zu Mathy. Ich möchte nur ein einfaches Beispiel im Pseudocode, das ich verstehen kann. Könnte zu spezifisch sein, aber ich dachte, es wäre einen Versuch wert.

algorithms algorithm-analysis reference-request runtime-analysis Nathvi
quelle
Ich verstehe nicht, wie der Stress zwischen "any" und "an" klar macht, wonach Sie wirklich suchen. Wenn eine Entscheidungsprozedur an einen bestimmten Algorithmus B gebunden ist, gibt es keine echte Eingabe und die Antwort ist immer dieselbe. Ich denke, was Sie fragen möchten, ist, ob 'irgendein Algorithmus innerhalb einer Klasse von Algorithmen', an die die Klasse gebunden / bekannt ist. (edit: dies wurde auch auf den Kommentar meiner Mutter hingewiesen).
Nicholas Mancuso
2
Die Mehrdeutigkeit bei der Verwendung von "an" und "any" ist genau der Grund, warum Quantifizierer erfunden wurden.
Nate Eldredge
2
Θ(nlog⁡n)

Antworten:

12

Das COSTA- Tool tut genau dies, obwohl es in vielen Fällen, wie Sie sich vorstellen können, aufgrund von Berechenbarkeitsproblemen fehlschlägt . Es gibt viele Papiere darüber; Die Kostenanalyse von Java-Bytecode durch E. Albert, P. Arenas, S. Genaim, G. Puebla und D. Zanardini ist ein guter Ausgangspunkt.

Der Ansatz besteht darin, aus dem Javabyte-Code eine Laufzeitwiederholung abzuleiten und diese in eine geschlossene Form zu konvertieren. Das Tool berechnet auch die Speicherplatznutzungsgrenzen.

Dave Clarke
quelle
8
@Nathvi Ich kann verstehen, dass Sie durch einige Kommentare irritiert sind, die meiner Meinung nach nicht wirklich notwendig waren, aber Sie sollten auch darauf achten, den Begriff "pedantischer Trottel" nicht für die Arbeit sehr seriöser Wissenschaftler zu verwenden (und im Übrigen meine Antwort). Sie haben das Recht, Mathematik nicht zu mögen, aber es ist unwahrscheinlich, dass Sie ohne sie weit kommen, und unbegründete abfällige Worte helfen niemandem.
Babou
12

Kein Algorithmus kann entscheiden, ob ein bestimmter Algorithmus jemals angehalten wird oder nicht, so dass insbesondere kein Algorithmus die Komplexität eines bestimmten Algorithmus genau analysieren kann.

Yuval Filmus
quelle
2
Meine Frage bezieht sich nicht auf einen willkürlich eingegebenen Algorithmus. Wenn dies der Fall wäre, wäre Ihre Antwort aufgrund des Stoppproblems korrekt. Sie wären richtig, wenn meine Frage lauten würde: "Gibt es einen Algorithmus A, der einen Algorithmus B aufnimmt und dann die zeitliche Komplexität von Algorithmus B ausgibt?"
Nathvi
6
Wenn der Algorithmus B festgelegt ist, ist sicher, dass es einen Algorithmus A gibt. Es reicht aus, einen Algorithmus zu haben, der nur "O (n)" oder ein beliebiges Komplexitätsmaß ausgibt, das B entspricht. Wenn es nur eine mögliche Eingabe für Algorithmus A gibt, dann brauchen wir nur einen Ausgang.
mhum
5
@Nathvi es war mir auch nicht klar - ich verstand die Frage auch als "Gibt es einen Algorithmus, um die Komplexität eines anderen Algorithmus zu finden", und ich verstehe Ihre eigentliche Frage immer noch nicht . Wenn Sie Upvotes zählen möchten, haben es anscheinend> 2 Personen so interpretiert. Im Falle von Verwirrung ist es wirklich eine gute Idee, Ihre Frage zu bearbeiten. Andernfalls verstehen nur Personen, die diese Konversation lesen (und nicht alle, die die Frage lesen), was Sie fragen, und geben gute Antworten. Sieht so aus, als hätten Sie das Gefühl, dass die Antwort von DW feindlich war - FWIW, ich glaube nicht, dass es beabsichtigt war ..
jkff
6
@ignis Die Antwort mag unvollständig sein, aber der Satz, den Yuval geschrieben hat, ist absolut korrekt. Und das Problem des Anhaltens ist kein exotischer Nebenfall: Es ist das Wesen der Berechnung.
David Richerby
3
@nikie Das hilft nicht, was diese Frage betrifft. Laufzeitgrenzen sind selbst bei allen immer terminierenden Algorithmen unentscheidbar .
Raphael
9

Ich kenne einen Ansatz zur (halb-) automatisierten durchschnittlichen Fallanalyse, nämlich MaLiJAn ¹. Es ähnelt stark der Art der Analyse, die Knuth in TAoCP verwendet. Die Kernidee ist zu

  • Modellieren Sie das Programm (Flow) als Markov-Kette.
  • n
  • n
  • Verwenden Sie Computeralgebra, um die durchschnittlichen Kosten abzuleiten (für diese Funktionen).

Beachten Sie, dass nur additive Kostenmaße (z. B. Vergleiche, "Zeit") funktionieren und nur der erwartete Wert genau ist (unter der Annahme perfekter Wahrscheinlichkeitsfunktionen). Höhere Momente können nicht abgeleitet werden.

Alle Schritte außer der Extrapolation sind streng [2], und es wurde gezeigt, dass die Methode bekannte Ergebnisse mit hoher Präzision reproduziert - natürlich bei geeigneten Zufallsstichproben. Obwohl es keinen Beweis oder gar keine Annäherungsgarantie für die Ergebnisse gibt (der Extrapolationsschritt ist bislang rein heuristisch), dienen die mit dem Tool erhaltenen Ergebnisse gut dazu, mit schwer zu analysierenden Algorithmen zu experimentieren und Hypothesen zu formulieren [3,4].

  1. Vollständige Offenlegung: Ich war Mitglied dieser Forschungsgruppe und war an der Entwicklung des Tools beteiligt.
  2. Maximum-Likelihood-Analyse von Algorithmen und Datenstrukturen von U. Laube und M. Nebel (2010) [ Preprint ]
  3. Engineering des Dual Pivot Quicksort von Java 7 mit MaLiJAn von S. Wild et al. (2012) [ Preprint ]
  4. Maximum-Likelihood-Analyse der Ford-Fulkerson-Methode auf Spezialgraphen von U. Laube und M. Nebel (2015) [ Preprint ]
Raphael
quelle
Kommen diese Techniken mit einer Schätzung der Genauigkeit der durchschnittlichen Fallanalyse?
Martin Berger
@ MartinBerger Leider nein. Wir haben einige Ideen dazu, aber noch nichts Festes, geschweige denn umgesetzt. Beachten Sie, dass es einfach ist, eine Methode zu täuschen, die nur endlich viele Eingabegrößen überprüft, sodass im Allgemeinen wenig Hoffnung besteht. Mit Annahmen zu den Laufzeitfunktionen und / oder Datensätzen kann etwas möglich sein. Das Tool sollte zumindest sagen können, dass mehr Daten benötigt werden.
Raphael
Das ist interessant. Ich hoffe, Sie kommen mit dieser zusätzlichen Arbeit zurecht.
Martin Berger
8

Natürlich sollte man, wie Yuval Filmus bemerkte, keine allgemeine Lösung für solche Probleme erwarten. Aber wie gewöhnlich können Lösungen für interessante Teilmengen des allgemeinen Falls gefunden werden.

Ich bin in keiner Weise Experte oder in diesem Bereich sogar sehr gut informiert, da ich zufällig von einer Arbeit dieser Art weiß. Es handelt sich um eine automatische Analyse der durchschnittlichen Komplexität, und die Arbeit wurde von Philippe Flajolet und seinen Kollegen durchgeführt.

λυ´ω

Ein Artikel, den ich im Internet gefunden habe, ist ein Artikel aus dem Jahr 1990: Automatische Durchschnittsanalyse von Algorithmen von Philippe Flajolet, Paul Zimmermann und Bruno Salvy .

Ich würde erwarten, dass spätere Arbeiten diese Arbeit erweitert haben, aber ich weiß es nicht wirklich. Die Arbeit wurde ziemlich häufig zitiert, und das Durchsuchen des Webs nach ihr sollte zu neueren Arbeiten zum gleichen Thema führen.

Jetzt befürchte ich, dass die Arbeit von Flajolet und seinen Kollegen sehr mathematisch war, und ich würde nicht viel einfaches Lesen erwarten.

babou
quelle