Gibt es einen Standard für den experimentellen Vergleich von Laufzeiten?

10

Meine Situation

Ich schreibe ein Papier mit einem von mir entwickelten Softwaremodul und möchte dessen Laufzeit mit anderen Modulen für dieselbe Aufgabe vergleichen. Ich bin mir der Nachteile von Laufzeitversuchen bewusst, gehe aber bitte davon aus, dass es in meinem Fall keinen Weg daran vorbei gibt. (Ich kann und kann theoretisch einige Eigenschaften ableiten, aber es reicht nicht für alles aus.)

Die spezifischen Szenarien, die ich für das Benchmarking verwenden möchte, haben zwei Parameter: die Komplexität  des Problems und einen zufälligen Startwert  r, der das detaillierte Problem bestimmt. Hauptsächlich möchte ich die Abhängigkeit von  n zeigen . Nach vorläufigen Untersuchungen und der Theorie ist der Einfluss von r auf die Laufzeit gering oder vernachlässigbar. Eine einzelne Aufgabe dauert höchstens zehn Minuten.nrnr

Aktuelle Frage

Ich suche nach einem allgemein akzeptierten oder veröffentlichten Verfahren zur Durchführung solcher Experimente oder zumindest nach einer Liste häufiger Fallstricke (idealerweise veröffentlicht).

Was ich bisher gefunden habe

Nichts. Internet-Suchen ergeben alle möglichen nicht zusammenhängenden Ergebnisse, aber dann verwende ich möglicherweise nicht die richtige Terminologie. Das Einfügen des Keyword- Minimums, von dem ich weiß, dass es ein guter Standard ist (siehe unten), hat auch nicht geholfen.

Wie würde ich das machen?

  • Führen Sie alle Experimente auf demselben Computer mit möglicherweise störender Software wie einer GUI aus, die so weit wie möglich deaktiviert ist.

  • Unterwerfen Sie alle Module derselben Auswahl von Szenarien, dh demselben und  r .nr

  • Testen Sie für jedes Szenario die verschiedenen Module direkt nacheinander in zufälliger Reihenfolge. Mit anderen Worten, die Schleife über die verschiedenen Module ist die innerste. Dies sollte eine Verzerrung der verschiedenen Module aufgrund langsamer Schwankungen der Maschinenleistung (z. B. aufgrund von Temperaturänderungen) vermeiden. Die zufällige Reihenfolge sollte eine Verzerrung durch Effekte wie Caching oder ein Modul vermeiden, das immer nach demselben getestet wird.

  • n

algorithm-analysis reference-request runtime-analysis experimental-analysis Wrzlprmft
quelle
Es könnte hilfreich sein, Ihre Argumentation zu erklären, warum Sie denken, "in meinem Fall führt kein Weg daran vorbei". Aber natürlich, wahrscheinlich als separate Frage und Link, da diese Frage so gut fokussiert ist, wie sie ist.
Apiwat Chantawibul
@ Billiska: Ich bin mir nicht ganz sicher, was ich tun soll. Warum sollte ich meine Argumentation für einen experimentellen Ansatz in einer separaten Frage erläutern? Ich habe keine Frage dazu.
Wrzlprmft
Ich muss nicht zustimmen, dass Sie die Mindestlaufzeit für wiederholte Experimente verwenden. Sie scheinen zu glauben, dass es nur nach oben einen Outliner geben könnte. Könnte es möglich sein, auch einen Outliner nach unten zu haben? Es ist typischer, mehrere Statistiken gleichzeitig zu untersuchen, z. B. Mittelwert, Median, max. Wer weiß, dass sie etwas zeigen können, was Sie nicht erwartet haben. Es ist schließlich ein empirisches Experiment.
Apiwat Chantawibul
2
Das ist sehr breit; Zu diesem Thema können Bücher geschrieben werden, z. B. McGeochs "A Guide to Experimental Algorithmics". Man könnte sogar sagen, Sie fragen: "Gibt es einen Standard für die Wissenschaft?". Ich bin mir also nicht sicher, ob dies einen angemessenen Umfang hat. Haben Sie spezifischere Fragen?
Raphael
2
Locker verwandt: cs.stackexchange.com/q/39597/755 , cs.stackexchange.com/q/29854/755 , cs.stackexchange.com/q/74178/755 .
DW

Antworten:

2

CC McGeochs "A Guide to Experimental Algorithmics" ist eine gute Referenz für

  • wie man Experimente mit Algorithmen aufbaut,
  • wie man Ergebnisse interpretiert und verwendet, und
  • wie man bei Bedarf zu aussagekräftigeren Ergebnissen iteriert.
Raphael
quelle
2

Geben Sie zusätzlich zur verstrichenen Zeit für jeden Lauf Sekunden des Benutzer- und Systemmodus sowie die Gesamtzahl der IP-Pakete und die Gesamtzahl der Festplatten-E / A an, um zu überprüfen, ob einige Zahlen durchweg "niedrig" sind und die verstrichene Zeit vernachlässigbar beeinflussen.

Auf https://wiki.freebsd.org/BenchmarkAdvice bieten PHK und andere gute Ratschläge an, einschließlich

Verwenden Sie ministat, um festzustellen, ob Ihre Zahlen signifikant sind. Erwägen Sie den Kauf von "Cartoon Guide to Statistics"

J_H
quelle