Erstellung einer Priority Queue

[Mad-Marty]

Hallo,

ich möchte eine PriorityQ , auch bekannt als HeapQ erstellen.

Ja ich weiss, es gibt module dafür.

Aber entweder ich verstehe nicht wie ich das Anwenden soll oder es geht nicht


Mein problem ist :
Ich Brauche eine prioritätsqueue, in der immer das item mit der höchsten priorität herausgenommen wird. Vorstellen könnte ich mir das ganze als Liste mit einem Tuple.

highest_priority_item = min ( [(2,"command"),(1,"command"),(3, "command")] )

Auserdem sollte meine PriorityQ auch die möglichkeit haben, mittels
"GetJobsWithPriority(2)" mir die commands zu geben die diese priorität haben. Also die selbe priorität soll mehrfach möglich sein.


Gibt es da schon was fertiges ? Wie würdet ihr das lösen ?
Oder Sehe ich das offensichtliche nicht ?

HeapQ sollte imo genau das anbieten, tut es aber nicht.

[modelnine]

Lies mal das Modul bisect nach, da kannst Du zumindest das einsortieren relativ leicht implementieren, indem Du eine ganz normale Queue nimmst. Soweit ich das weiß gibts auch im Python Cookbook ein entsprechendes Rezept.

Was das herausnehmen aus der Queue aller items mit einer gewissen Priorität bedeutet: das ist nicht ganz einfach. Entweder Du benutzt keine Liste (also eine Queue) als Basistyp, sondern ein Hash, oder Du mußt die Liste jedes mal durchiterieren. Ersteres würde bedeuten dass Du den Typ selbst schreiben mußt, letzteres ist sehr Laufzeitintensiv.

Liegt an Dir, würde ich mal sagen.

Wenn Du Beispiele zu den beiden Typen brauchst und die Hinweise nicht reichen, sag bescheid.

--- Heiko.

[Mad-Marty]

Hi modelnine,

stimmt, das Rezept hab ich bisher wohl völlig übersehen.


Thx für den Tip.


Jetzt überlege ich wie ich das anpassen kann ...

Ich brauche die anzahl wieviele items mit welcher priorität anliegen, um eine ressourcenverteilung vorzunehmen.

sagen wir ich habe 6 ressourcen, und 4 aufgaben, eine mit prio1, und 3 mit prio2.

Dann möchte ich das die aufgabe mit prio 1, 3 ressourcenslots bekommt, und die anderen 3 die restlichen 3.

Geht in dem beispiel schön auf.

Auserdem möchte ich bei neu anliegenden Aufgaben die ressourcenslots dynamisch umverteilen können.
Später eintreffende Aufgaben mit höherer priorität können dazu führen, dass niedrige Prioritätoperationen geparkt werden ....

[modelnine]

Kann ich nur zu sagen: schreib es selbst...

<edit>Wenn Du es so genau brauchst, nimm einen dict um für jede priority eine eigene Queue zu haben. Den Algorithmus zum einteilen mußt Du bitteschön selbst schreiben, das ist nicht trivial. Gerade wenn's um start/stop von irgendwelchen Ressourcen geht mußt Du Dir selbst ein Schema einfallen lassen, um zum Beispiel threads schlafen zu legen, oder aber die Ressource von der laufenden Aufgabe zu befreien, die wieder einzusortieren, und dann auf der Ressource eine neue Aufgabe laufen zu lassen. Wie gesagt: das ist nicht trivial, und erfordert 'ne ganze Menge Programmierarbeit.

Willst Du das wirklich?</edit>

--- Heiko.

[Mad-Marty]

Ok.
Danke

EDIT:

Ich sehe die Aufgaben als eine Art Command Pattern, soll heissen,
die Aufgaben werden "Objektiviert" und können pausiert werden.

Jeder Thread hat dann nochmal seine eigene persönliche Q, die aber nicht mehr als 1 element parken kann.

[BlackJack]

Hallo,

ich möchte eine PriorityQ , auch bekannt als HeapQ erstellen.

Ja ich weiss, es gibt module dafür.

Aber entweder ich verstehe nicht wie ich das Anwenden soll oder es geht nicht

Ich würde so etwas mit dem `heapq` Modul basteln. Das bietet nur Funktionen um eine Liste als "Heap" zu benutzen, also müsstest Du eine Klasse schreiben, welche diese Funktionen benutzt um ein PriorityQueue Objekt zu bekommen.

[Mad-Marty]

Im moment erscheinen mir Mappings mit Listen am geeignetsten dafür.

Ich glaube modelnine hat das erwähnt und später editiert.