Restzeitberechnung

[BAGZZlash]

Ich habe ein kleines Programm geschrieben, das eine ziemlich aufwendige Berechnung durchführt (rechnet mehrere Tage). Ich weiß, wie viele Iterationen insgesamt durchzuführen sind und ich weiß auch stets, bei der wievielten Iteration ich gerade bin. Ich kann also ohne Weiteres eine prozentuale Fortschrittsanzeige ausgeben.

Zusätzlich würde ich gerne die Restzeit prognostizieren. Dazu fallen mir spontan einige Methoden ein:


Ich schaue, wie viele Iterationen in der letzten Sekunde berechnet wurden. Beispielsweise 10 Stück. Wenn ich noch 100 Iterationen vor mir habe, weiß ich, dass es noch 10 * 10 = 100 Sekunden dauern wird. Die Methode ist einfach, hat aber den Nachteil, dass die Anzahl an berechneten Iterationen pro Sekunde deutlich schwanken kann, die Restzeitberechnung ist also ungenau.
Ich denke, die berüchtigte Fortschrittsanzeige beim Kopieren von Dateien älterer Windowsversionen verwendete diese Methode. Alternativ kann man auch auf die letzte Minute oder die letzten zehn Minuten zurückblicken, dadurch werden kurzfristige Schwankungen geglättet.
Oder man bezieht die gesamte Vergangenheit ein. Beispielsweise bin ich bei 10%, seit dem Start ist eine Stunde vergangen. Also brauche ich für die restlichen 90% noch 9 Stunden. Diese Methode hat den Vorteil, mit der Zeit immer genauer zu werden. Allerdings ist der Nachteil, dass die Prognose zumindest am Anfang ziemlich ungenau sein wird. Ich sehe öfers, dass diese Methode verwendet wird, beispielsweise bei CoolEdit.
Natürlich könnte man versuchen, diese beiden Methode zu kombinieren. Oder man ergänzt Methode 1 um ein gleitendes Mittel, aber wäre das nicht mit Kanonen auf Spatzen geschossen?


Kurzum: Wie macht Ihr's?

[Monger]

Klassische Fortschrittsbalken sind so n bissl außer Mode gekommen. Viele Programme zeigen nur noch einen bewegten Balken, und sparen sich die Prognose.

Die Grundannahme hier ist ja, dass jede Aktion gleichberechtigt ist, und zumindest mal ähnlich lange dauert. Der Fortschritt von 1 auf 2% sollte ähnlich lange dauern wie von 95 auf 96%.
Genau daran scheitern sehr, SEHR viele Programme. Diese Grundannahme stimmt eben oft genug nicht. Wenn das so wäre, spricht eigentlich nichts dagegen, einfach die Zeit eines einzelnen Durchlaufs zu nehmen, und von da aus zu interpolieren. Ist wahrscheinlich sogar präziser als die Vergangenheit mit zu berücksichtigen, denn was immer auch deine aktuelle Aktion langsam macht, macht wahrscheinlich auch die zukünftigen Aktionen langsam.

[samm]

Weshalb nicht den Fortschrittsbalken entsprechend kennzeichnen - nicht die Zeit schätzen, sondern iterations completed / iterations total? ;)

[Shink]

Klassische Fortschrittsbalken sind so n bissl außer Mode gekommen. Viele Programme zeigen nur noch einen bewegten Balken, und sparen sich die Prognose.
Sobald IO dabei ist oder gar ein fremder Rechner kann man das ohnehin vergessen. Merkt man gut beim Download-Fortschritt: Was es heißt 98 von 100MB heruntergeladen zu haben sollte klar sein. Aber dann kann immer noch die Verbindung abbrechen, der Fortschrittsbalken zeigt 3 Tage an und bringt genau gar nichts, egal ob man ihn nun aus der aktuellen Geschwindigkeit oder der berechnet.

So gesehen würde ich z.B. einfach die abgearbeiteten Iterationen anzeigen und x/y dazuschreiben.

[Trap]

Man könnte auch die aktuelle Geschwindigkeit zusätzlich im Balkendiagramm anzeigen (in Iterationen pro Sekunde/Minute/Stunde/Tag je nachdem was eine sinnvolle Balkenlänge ergibt).

Damit kann man als Nutzer die verbleibende Zeit einschätzen, ohne dass man irritierende verbleibende Zeiten anzeigt.

[elianda]

Wenn Du nur die Startzeit und aktuelle Zeit hast und die aktuelle Iteration bleiben nicht viele Möglichkeiten sinnvoll eine Endzeit fuer X Iterationen zu extrapolieren.

Geschickter waere es, wenn Du nach jeder abgeschlossenen Iteration die aktuelle Zeit mitloggst.
Dann kannst Du diese Zeitpunkte mit einer Funktion anfitten und somit für eine zukuenftige Iteration den Zeitpunkt errechnen. Da man die genaue Funktion normalerweise nicht kennt, nimmt man als Näherung einfach eine Taylorreihenentwicklung her, die man z.B. nach dem zweiten Polynom abbricht. Letztendlich also anfitten mit einer quadratischen Funktion.

[BAGZZlash]

Wenn Du nur die Startzeit und aktuelle Zeit hast und die aktuelle Iteration bleiben nicht viele Möglichkeiten sinnvoll eine Endzeit fuer X Iterationen zu extrapolieren.

Geschickter waere es, wenn Du nach jeder abgeschlossenen Iteration die aktuelle Zeit mitloggst.
Dann kannst Du diese Zeitpunkte mit einer Funktion anfitten und somit für eine zukuenftige Iteration den Zeitpunkt errechnen. Da man die genaue Funktion normalerweise nicht kennt, nimmt man als Näherung einfach eine Taylorreihenentwicklung her, die man z.B. nach dem zweiten Polynom abbricht. Letztendlich also anfitten mit einer quadratischen Funktion.
Guter Vorschlag, vielen Dank! :smile:

[airbag]

Man kann ja auch die Zeitkomplexität aller Methoden anhand des Codes berechnen und dann die auszuführende Funktionswerte dafür einsetzen. --> Wenn man zudem vom Worst Case ausgeht, kann man sich zumindestens nicht unterschätzen.:D

Die Methode mit dem mittlogen dürfte und der Taylorreihe dürfte aber praktikabler sein.

[elianda]

Die Idee würde prinzipiell auch gehen, jedoch hängt die Zeitkomplexität einer Methode meistens auch von den Eingabewerten ab. Das Berechnen der benötigten Rechenzeit ist eher noch aufwendiger als das ausführen des eigentliches Codes.

[Senior Sanchez]

Zur kleinen Aufheiterung fällt mir das hier ein: http://xkcd.com/612/

[pest]

Da man die genaue Funktion normalerweise nicht kennt, nimmt man als Näherung einfach eine Taylorreihenentwicklung her, die man z.B. nach dem zweiten Polynom abbricht. Letztendlich also anfitten mit einer quadratischen Funktion.

Wenn man eine Funktion nicht kennt, kann man auch ihre Taylorreihe nicht aufstellen

[AlecWhite]

Hab das in einem aktuellen Projekt mit Regression gelöst - Meßpunkte hat man genug und der Verlauf der Funktion ist prinzipiell meist auch klar --- meistens ist sie halt linear. Mit dem Satz von Gauß-Markow lässt sich das sogar sehr effizient berechnen.