Priority queue nach (Wert*Zeit) sortiert halten



  • Ich hab eine Art priority queue mit vielen Millionen Einträgen und ich möchte jeweils flott den Eintrag mit der höchsten Priorität herausbekommen.
    Das Problem ist, dass sich die Priorität aus "Wichtigkeit * vergangene Zeit seit letztem Update" errechnet, sie ändert sich also jede Sekunde.
    Wie könnte man das am besten lösen, ohne die Liste per Brute-Force-Methode ständig vollständig neuzusortieren?

    Mein erster Ansatz wäre, für jede diskrete Wichtigkeit einen eigenen Bucket anzulegen, wo ich dann alle Einträge mit der entsprechenden Wichtigkeit sortiert nach letztem Update drinbehalte und ich mir dann immer die obersten Einträge aller Buckets ansehe und den mit der höchsten Priorität nehme. Erfordert allerdings, dass ich die Auflösung der Wichtigkeit kräftig reduziere, damit die Anzahl der Buckets überschaubar bleibt.

    Fällt jemandem ein besserer Ansatz ein?



  • Merke dir nicht die Zeit seit dem letzten Update sondern die Zeit des letzten Updates (diese ändert sich nicht solange das Element nicht updated wird). Wenn kein Update auftritt, dann brauchst du in der Priority-Queue nichts zu ändern, denn die Zeit läuft für alle Einträge in der Queue gleich schnell, d.h. wenn kein Update auftritt, dann ändern sich auch die relativen Prioritäten nicht.
    Wenn ein Update eintritt, dann entfernst du das Element, das updated wurde, und fügst es neu ein (je nach Implementierung geht das auch etwas cleverer aber so sollte das schon schnell genug sein). Da du für jedes Element die Zeit des letzten Updates gespeichert hast und die aktuelle Zeit kennst kannst du während des Einfügens des updateten Elements jeweils die Priorität des Elements, mit dem du gerade vergleichst, ausrechnen.

    Ich habs mir nicht im Detail überlegt aber ich denke das sollte so klappen.



  • Das Problem ist, dass die Zeit für manche Elemente eben quasi doch schneller oder langsamer vergeht, je nach Wichtigkeit eben. Dadurch "überholen" wichtige Einträge ständig Einträge mit niedriger Wichtigkeit in der queue.



  • fern schrieb:

    Das Problem ist, dass die Zeit für manche Elemente eben quasi doch schneller oder langsamer vergeht, je nach Wichtigkeit eben. Dadurch "überholen" wichtige Einträge ständig Einträge mit niedriger Wichtigkeit in der queue.

    Ach Mist, da habe ich zu ungenau gelesen. In dem Fall ist meine Antwort natürlich kompletter Müll 😃

    Ich habe leider auch nicht wirklich eine schlaue Lösung parat - aber hier vielleicht zwei Gedankenanstösse:
    1.

    Wenn ich es richtig sehe dann könntest du für Elemente mit gleicher Wichtigkeit eine Priority Queue (anstatt irgendwelchen Buckets) anlegen (innerhalb dieser P-Queues läuft die Zeit gleich schnell). Diese Priority Queues kannst du dann wieder in einer Priority Queue speichern. Dann brauchst du nur jede Sekunde die Toplevel Priority Queue zu updaten (wenn du nicht tausende Wichtigkeiten hast, dann sollte das machbar sein). Aber sowas ähnliches hast du dir ja bereits selber überlegt

    Ein weiterer Ansatz wäre die Updates nur lazy vorzunehmen, d.h. du Updatest die Priority Queue erst wenn du auf ein Element davon zugreifen möchtest (falls dann ein Update nötig ist). Diese Ansatz ist aber natürlich nur sinnvoll, wenn du in weiten Zeitabständen auf die Priority Queue zugreifst, was ich nicht annehme.



  • fern schrieb:

    Fällt jemandem ein besserer Ansatz ein?

    Mir zumindest nicht.
    Du könntest höchstens "umdefinieren". Also dir überlegen ob du nicht was anderes statt Wichtigkeit * Alter verwenden könntest.
    Wobei mir jetzt spontan auch nix einfällt - zumindest nix was die Sache nicht noch komplizierter machen würde 😃



  • log(Wichtigkeit*Updatezeitpunkt)==log(Wichtigkeit)+log(Updatezeitpunkt)
    Nee, klappt wohl auch nicht.



  • Wenn Du den Faktor vor der Zeit jeweils kennst, dann kannst Du doch vorberechnen, wann ein Eintrag in der Prioritaetswarteschlange (A) nach vorne rutscht. Du kannst beim Eintragen eines Elements in die Liste feststellen, an welchem davorstehenden Element es zuerst vorbeirutscht. Diese Zeitpunkte kannst Du dann entsprechend in eine weitere Prioritaetswarteschlange (B) eintragen und wenn Du das naechste Element aus A haben willst, guckst Du einfach, welchen Zeitpunkt Du hast und fuehrst dann mit Hilfe der Eintraege in B die Vertauschungen durch, die bis zu dem Zeitpunkt durchzufuehren waren. ...wobei dann natuerlich immer ein neues Element in B einzug haelt, wenn eine Vertauschung stattgefunden hat.

    Ob das in Deinem Fall effizient ist, ist aber sicherlich eine Frage Zahlen: Wie viele Eintraege, wie unterschiedlich sehen die Faktoren vor den Zeiten aus und so weiter.

    Generell solltest Du bedenken, dass wenn Du bei jedem Zugriff auf A neu sortierst, A vermutlich schon fast sortiert ist. Einige Sortierverfahren sind fuer derartige Situationen besonders gut geeignet, andere eher weniger. Wenn Du es schlau machst, kostet Dich das Neusortieren vielleicht nur sehr wenig. ...aber auch das ist eine Frage der Parameter Deiner Problemstellung.


Log in to reply