Momentan arbeite ich an einigen Schichtplanungssimulationen für eine Modelltaxi-Firma. Das Unternehmen betreibt 350 Kabinen und alle sind an einem bestimmten Tag in Betrieb. Die Fahrer arbeiten jeweils in 5 Schichten zu je 12 Stunden und es gibt vier überlappende Schichten pro Tag. Es gibt Schichten von 3: 00-15: 00, 15: 00-3: 00, 16: 00-4: 00 und 4: 00-16: 00. Ich habe es ursprünglich in Python entwickelt, weil ich es schnell entwickeln musste, und ich dachte, dass die Leistung akzeptabel wäre. Die ursprünglichen Parameter erforderten nur zwei Schichten pro Tag (3: 00-15: 00 und 15: 00-3: 00), und während die Leistung nicht groß war, war es gut genug für meine Zwecke. Es könnte einen wöchentlichen Zeitplan für die Fahrer in ungefähr 8 Minuten machen, unter Verwendung eines einfachen Brute-Force-Algorithmus (wertet alle möglichen Swaps aus, um zu sehen, ob die Situation verbessert werden kann).
Mit den vier überlappenden Schichten ist die Performance absolut miserabel. Es dauert etwas über eine Stunde, um einen Wochenplan zu machen. Ich habe einige Profilerstellung mit cProfile gemacht, und es sieht so aus, als ob die Haupttäter zwei Methoden sind. Eine ist eine Methode, um festzustellen, ob ein Konflikt vorliegt, wenn ein Fahrer in eine Schicht versetzt wird. Es stellt sicher, dass sie nicht am selben Tag in einer Schicht dienen oder in der vorhergehenden oder folgenden Schicht dienen. Mit nur zwei Schichten pro Tag war das einfach. Man musste einfach feststellen, ob der Fahrer bereits in der Schicht direkt davor oder danach arbeiten sollte. Mit den vier überlappenden Schichten ist dies komplizierter geworden. Der zweite Täter ist die Methode, die bestimmt, ob die Schicht eine Tag- oder Nachtschicht ist. Bei den ursprünglichen zwei Schichten war dies ebenso einfach wie die Bestimmung, ob die Schichtnummer gerade oder ungerade war, wobei die Schichtnummern bei 0 beginnen. Die erste Schicht (Schicht 0) wurde als Nachtschicht bezeichnet, die nächste als Tag und und so weiter und so fort. Jetzt sind die ersten zwei Nächte, die nächsten zwei sind usw. Diese Methoden rufen sich gegenseitig an, also werde ich ihre Körper darunter stellen.
%Vor%Beachten Sie, dass get_type den Typ der Verschiebung zurückgibt, wobei 0 angibt, dass es sich um eine Nachtschicht handelt, und 1, um eine Tagschicht anzuzeigen.
Um den Schichttyp zu bestimmen, verwende ich diese Methode:
%Vor%Und hier ist die relevante Ausgabe von cProfile:
%Vor%Hat jemand irgendwelche weisen Ratschläge oder Tipps, wie ich die Leistung dieses Skripts verbessern könnte? Jede Hilfe würde sehr geschätzt werden!
Prost,
Tim
EDIT: Entschuldigung, ich hätte klarstellen sollen, dass die Daten von jeder Schicht als eine Menge gespeichert werden, d. h. shift_data [k] ist vom eingestellten Datentyp.
EDIT 2:
Hinzufügen der Hauptschleife, wie unten beschrieben, zusammen mit anderen Methoden genannt. Es ist ein bisschen durcheinander, und ich entschuldige mich dafür.
%Vor%Es gibt nichts, was diese Funktionen offensichtlich verlangsamen würde, und tatsächlich sind sie nicht langsam. Sie werden nur sehr oft angerufen. Sie sagen, Sie verwenden einen Brute-Force-Algorithmus - können Sie einen Algorithmus schreiben, der nicht jede mögliche Kombination ausprobiert? Oder gibt es einen effizienteren Weg, die Daten nach Treiber anstatt nach Schicht zu speichern?
Natürlich, wenn Sie sofortige Beschleunigungen benötigen, könnte es von Vorteil sein, in einem Interpreter wie PyPy zu laufen oder Cython zu benutzen, um kritische Teile in C umzuwandeln.
Hmm. Interessantes und spaßiges Problem. Ich werde es mehr sehen müssen. Für jetzt habe ich das zu bieten: Warum stellen Sie Schwimmer vor? Ich würde get_stype () wie folgt tun:
%Vor% Es ist keine massive Beschleunigung, aber es ist schneller (und einfacher). Außerdem musst du den Mod 28 nicht jedes Mal füttern, wenn du get_stype fütterst, denn das wird bereits von der Mod 4 in get_stype erledigt.
Wenn signifikante Verbesserungen zu erwarten sind, werden sie in Form eines besseren Algorithmus zur Verfügung stehen. (Ich sage nicht, dass Ihr Algorithmus schlecht ist oder dass es einen besseren gibt. Ich habe nicht wirklich genug Zeit damit verbracht, es zu betrachten. Aber wenn es keinen besseren Algorithmus gibt, dann finden Sie signifikante Geschwindigkeitssteigerungen müssen von der Verwendung von PyPy, Cython, Shed Skin oder dem Umschreiben in einer anderen (schnelleren) Sprache ausgehen.)
Ich glaube nicht, dass Ihr Problem die Zeit ist, die es braucht, um diese beiden Funktionen auszuführen. Beachten Sie, dass der Wert percall für die Funktionen 0.000 ist. Dies bedeutet, dass jedes Mal, wenn die Funktion aufgerufen wird, weniger als 1 Millisekunde benötigt wird.
Ich denke, dein Problem ist die Häufigkeit, mit der die Funktionen aufgerufen werden. Ein Funktionsaufruf in Python ist teuer. Wenn Sie beispielsweise eine Funktion aufrufen, die 57.662.556 Mal nichts tut, dauert es auf meinem Rechner 7,15 Sekunden:
%Vor% Eine Sache, auf die ich neugierig sein könnte, ist die Variable shift_data . Sind die Werte Listen oder dicts?
Der in benötigt O(N) Zeit, wenn es eine Liste ist, aber O(1) Zeit wenn es ein dict ist.
EDIT: Da shift_data Werte Sets sind, sollte das in Ordnung sein
Ich denke also, dass Sie zunächst nur zwei Schichten planen können, Tag und Nacht, und erst danach die in die Schichten eingeteilten Fahrer in die zwei Schichten aufteilen.
Tags und Links python