Effiziente Prioritätsliste

Question

Ich bin auf der Suche nach einer effizienten Datenstruktur, um eine Prioritätenliste darzustellen. Speziell muss ich einer Menge von Gegenständen eine Priorität zuweisen und nur die besten Punkte zurückgeben. Ich habe Prioritätswarteschlangen untersucht, die auf großen Haufen operieren, aber sie scheinen meinen Bedürfnissen nicht wirklich zu entsprechen. Sie werden die Heap-Struktur reorganisieren, sobald ich das Top-Rating-Element aus der Warteschlange abfragen werde.

Die einfachste Lösung wäre natürlich eine verkettete Liste, die im schlimmsten Fall für die Einfügeoperation ziemlich lange dauern würde.

Hat jemand eine bessere Lösung?

Answer 1

Heaps scheinen sehr geeignet, und es scheint, als ob Sie falsch verfahren.

Sagen Sie bitte die oben x Elemente wollte (wie funktioniert x dies n zu vergleichen, btw?)

Was Sie tun, ist alles in einem max-Heap setzen und die Top-x zu bekommen.

Ich schlage stattdessen vor, Sie verwenden einen Min-Heap von genau x Elementen.

Erste x Elemente, die Sie in Heap einfügen.

Als nächstes einkommendes Element vergleichen Sie mit dem min, das sehr schnell (O (1) mal) im Heap erledigt werden kann. Wenn Sie kleiner sind, ignorieren Sie einfach das eingehende Element.

Wenn das eingehende Element größer als min ist, erhöhen Sie die min auf das eingehende Element und sieben es im Heap auf. Dies sollte schlimmstenfalls die logarithmische Zeit sein.

Sobald Sie fertig sind (in nlogx Zeit), können Sie die Elemente aus dem Heap in sortierter Reihenfolge in O (xlogx) Zeit abrufen.

Je nachdem, wie Ihre Daten sind (und wie klein x ist), kann die Verwendung dieser Min-Heap-Lösung sehr schnell sein.

---

Wenn Sie wirklich wollen wirklich die Einsätze super-schnell zu sein und kümmern sich nicht viel über das Retrieval, dann können Sie auch Folgendes tun.

Fügen Sie die Elemente in der angegebenen Reihenfolge in einen Vektor (Array mit amortisierter O (1) Einfügezeit) ein.

Verwenden Sie den Auswahlalgorithmus, um das x-te größte Element zu finden (in O (n) -Zeit, aber die Konstanten könnten groß sein). Sagen Sie, dass Zahl S.

nun das Array gehen jedes Element mit S zu vergleichen und wählen Sie die, die so groß ist wie S.

Wenn x eine vernünftige Größe und vergleichbar mit n (wie n/2 oder etwas) diese mag gut funktionieren, aber wenn x im Vergleich zu n klein ist, würde ich vorschlagen, mit dem Min-Heap zu gehen.

Answer 2

Hmm. Skip lists? Sie sollten O (log n) -Einfügung (als Heap-basierte Queue) haben, aber das oberste Element sollte O (1) sein [einschließlich Entfernen]. Sie könnten sogar mit Lock-Free-Algorithmus implementiert werden.

Answer 3

Das JDK hat eine integrierte PQ-Klasse (java.util.PriorityQueue), die auf einem Heap-Algorithmus basiert.

Entschuldigung, ich habe nur ein bisschen über Haufen gesehen, die nicht Ihren Bedürfnissen entsprechen. Kannst du erklären warum? Sie können einen benutzerdefinierten Komparator schreiben (oder Ihre Artikel vergleichbar machen) und die PriorityQueue wird Ihre Artikel entsprechend bestellen.

Answer 4

Wenn Sie nur die k Top-Artikel und Sie nie Notwendigkeit, eine, die anderen zu suchen, können Sie eine einfache verknüpfte Liste oder Array verwenden nur die aktuellen Top-k Speichern von Elementen, sowie eine Reihe (die schlechteste Punktzahl der Elemente in der Liste).

In der Add() Operation vergleichen Sie einfach den Artikel mit dem schlechtesten Wert in der Liste und, wenn es besser ist, tauschen Sie den aktuell schlechtesten mit dem hinzugefügten Artikel. Dies dauert O (k) Zeit in der worst case für die Einfügung, weil Sie das Element finden müssen, die derzeit die schlechteste Punktzahl hat. Der durchschnittliche Fall ist jedoch O (1), da, wenn Sie der Liste bessere Elemente hinzufügen, die Wahrscheinlichkeit, einen Swap durchzuführen, zu 0 tendiert (das heißt, Sie fügen keine Elemente hinzu). .

Also, wenn Sie Elemente zufällig generieren, wird Ihre Leistung wahrscheinlich sehr gut sein. Selbst wenn Sie bestellte Artikel generieren (im schlimmsten Fall), könnte es für Ihren Wert von k schnell genug sein.