[Python-de] cron-Ersatz

Henning.Ramm at mediapro-gmbh.de Henning.Ramm at mediapro-gmbh.de
Die Aug 9 20:28:57 CEST 2005


>> Kennt jemand eine Beschreibung des cron-Algorithmus'?
>Pro cron-Zeile würde ich 5 Vergleiche erwarten (wenn man
>(mon,day,wday,hour,min)-Tupel betrachtet):
>
>1. Finde pro Element den nächst-größeren Wert. Das ist
>   linear in Abhängigkeit von der Länge der Wert-Spezifikation
>   möglich, also 1,2,3-10,20-30 braucht 5 Schritte, jeder mit
>   bis zu zwei Vergleichen. Laufzeiteffizienter sind indizierte
>   Zugriffe:
>   next[0]=1, next[1]=2, next[2]=3, next[3]=10, ... next[9]=10
>   next[10]=11 usw. next[59]=1

Ich erzeuge aus dem jeweiligen Item (Minute, Stunde usw.) eine Liste aller erlaubten Werte, und errechne die minimale Differenz der jeweiligen Elemente zur Startzeit, das dürfte den gleichen Zweck erfüllen.

>2. Test, ob nmin > min. Falls ja, ist das der nächste
>   Ereigniszeitpunkt.
>3. Falls nicht, ist min übergelaufen: nhour=next[nhour]
>   Falls das auch überläuft, weiter mit wday.

Ich gehe in der Reihenfolge Monat - Tag - Wochentag - Stunde - Minute vor, das dürfte am wenigsten Iterationen brauchen.

>wday bedarf vermutlich einer Sonderbehandlung: der nächste
>Tag ist der, bei dem *entweder* day oder wday matcht.
>Also muss nextday(day) vermutlich sowohl den nächsten
>Tag als auch den nächsten Wochentag ausprobieren, und
>schaun, welcher davon früher ist.

Es müssen aber beide stimmen!

>Bei mehreren cron-Zeilen: jeweils pro Zeile den nächsten
>Ereigniszeitpunkt bestimmen, dann alle Zeilen aufsteigend
>sortieren. Wenn das nächste Ereignis eingetroffen ist,
>übernächsten Zeitpunkt für diese crontab-Zeile bestimmen,
>array der nächsten Zeitpunkte aktualisieren, Feld neu
>sortieren.

Ja, das kann die Klasse crontab schon, d.h. wenn nach dem nächsten Event gefragt wird, wird die ganze Liste neu berechnet - da gibt es auch noch Optimierungsspielraum.

Auch die Möglichkeit, rückwärts zu rechnen, bewirkt viel zu viele Verzweigungen. Entweder lasse ich es ganz weg, oder ich trenne die Funktionen für vorwärts und rückwärts.

Ich schreibe nochmal den ganzen Ablauf für eine Zeile auf, vielleicht fällt mir oder dir dabei etwas ein ;-) :

cronline.__init__:
	- ungültige Zeile (nach regex) wird abgewiesen
	- Spaceruns werden durch einzelne Leerzeichen ersetzt
	- Zeile wird an Leerzeichen gesplittet (Teile > 5 werden wieder zusammengesetzt)
	- die ersten fünf Elemente (Zeit-Elemente) werden zu einer sortierten Liste gültiger Werte expandiert
	  (Funktion expandCronEntry dürfte einigermaßen effizient sein)

cronline.getNextEvent(Startzeit):
	- Standardwert für Startzeit ist jetzt
	- WHILE not found (max. 50 Iterationen erlaubt):
		* Startzeit wird in cron-Elemente zerlegt
		* für jedes Element wird der Eintrag mit der kleinsten Differenz (minDiff) zur Startzeit ermittelt
		  (Funktion mindiff dürfte effizient sein)
		* WENN für ein Element keine minDiff existiert,
		  (d.h. der letzte gültige Zeitpunkt schon überschritten ist)
		  wird die nächstgrößere Einheit der Startzeit weitergezählt
              (Minute vorbei -> nächste Stunde)
            * SONST wird in der Reihenfolge Monat, Tag, Wochentag, Stunde, Minute geprüft,
              ob die minDiff <> 0 ist. Dann wird das Element um die minDiff erhöht, zurück zu WHILE.
		  Wenn alles 0 ist, haben wir eine gültige Zeit gefunden.
		  (Hoppla, da wurde die falsche Zeit zurückgegeben!)

Wenn ich verlange, dass ein Kalendertag auf einen bestimmten Wochentag fallen muss, die Funktion also mehrere Jahre weiterzählen muss, braucht sie ca. 25 Iterationen, sonst meist unter 10.
Die Exception wegen zu vieler Iterationen kam bei meinen Tests nur, wenn ich ungültige Daten wie den 30.2. gefordert habe oder "29.2. am Sonntag" (das wäre im Jahr 2032 -> 115 Iterationen; wer sowas braucht, kann immer noch iterationmax erhöhen).

Warum es nicht funktioniert, nur den Monat anzugeben, muss ich noch suchen.

Grüße vom Südsee!
Henning Hraban Ramm
Südkurier Medienhaus / MediaPro
Systembetreuung / Systementwicklung 
-------------- nächster Teil --------------
Ein Dateianhang mit Binärdaten wurde abgetrennt...
Dateiname   : cron.py
Dateityp    : application/octet-stream
Dateigröße  : 19833 bytes
Beschreibung: cron.py
URL         : http://starship.python.net/pipermail/python-de/attachments/20050809/856e76c2/cron-0001.obj