Welche Datenstruktur oder Mischung von Datenstrukturen würde ich für eine gleichzeitige Warteschlange verwenden, die Massen- und spezifische Löschungen zulässt?

9

Hier ist mein Problem, ich brauche eine Datenstruktur, die sich wie ein queue verhält, aber einige andere Eigenschaften hat:

  • Ich sollte in der Lage sein, Elemente mit tag einfach zu löschen (jedes Element in dieser Warteschlange hat ein tag , das sie gruppiert)
  • Ich muss auch in der Lage sein, einen Gegenstand mit einem key zu löschen (alle Gegenstände, die der Sammlung hinzugefügt werden, haben einen solchen eindeutigen Schlüssel). Hier, wenn es Dinge vereinfacht, könnte ich per tag und key entfernen, wenn es schneller wäre.
  • Diese Sammlung wird in einer gleichzeitigen Umgebung verwendet, so dass es so toll wäre, so wenig wie möglich zu sperren
  • Es sollte die üblichen FIFO-Eigenschaften einer Warteschlange haben. Ich muss nicht auf Objekte zugreifen, die sich nicht im Kopf befinden, aber ich brauche das Löschen oben, um zu funktionieren.

Ich verwende C #, um diese Lösung zu erstellen, aber ich wäre viel mehr an Definitionen von Algorithmen und Datenstrukturen interessiert, da ich kaum glaube, dass eine der verfügbaren Sammlungen meine Anforderungen erfüllt.

Papers, Bücher, Blog-Posts und jede andere Art von Hinweis darauf sind wirklich willkommen.

    
Maurício Linhares 28.08.2012, 20:54
quelle

2 Antworten

3

Klingt so, als ob Sie eine simultan verknüpfte Liste für den Warteschlangenteil verwenden können. Für den delete-by-key-Teil könnten Sie eine gleichzeitige Hash-Tabelle behalten (Stripeset-Locks sind leicht zu machen), die auf Knoten in der Warteschlange zeigt.

Wenn dieser Ansatz fehlschlägt, sehen Sie sich an, wie Datenbanksysteme dies tun. Sie können alles gleichzeitig tun, was Sie wollen. Sie pflegen eine Primärkopie der Daten in einem B-Baum und behalten sekundäre B-Baum-Indizes bei. Zum Sperren verwenden sie eine gleichzeitige Hash-Tabelle. B-Bäume haben gute Nebenläufigkeitseigenschaften, weil Sie die oberen Teile von ihnen leicht teilen können, selbst wenn Sie die Blätter unter einer exklusiven Sperre aktualisieren.

    
usr 28.08.2012 22:28
quelle
1

Ich denke, Sie können doppelt doppelt verknüpfte Listen und zwei Hashtabellen verwenden.

  • Ein Teil der Liste für die Warteschlange
  • Ein weiterer Teil zum Gruppieren von Knoten nach Tag
  • Eine Hashtabelle für den Zugriff auf einen Knoten über den Schlüssel
  • Eine weitere Hashtabelle für den Zugriff auf Knoten durch ein Tag

Beispiele in Python (Es tut mir leid ...)

Einfügen eines Elements:

%Vor%

Entfernen eines Elements nach Schlüssel:

%Vor%

Entfernen eines Elements nach Tag:

%Vor%

So ähnlich. Hoffe es hilft.

    
tcurvelo 29.08.2012 01:48
quelle