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

Question

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.

algorithm language-agnostic c# concurrency data-structures

Maurício Linhares 28.08.2012, 20:54

quelle

2 Antworten

Tags und Links algorithm language-agnostic c# concurrency data-structures

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Deaktivierung von iPad Erstellen von Ortsmarken in Google Map

score 3 · Answer 1

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.

score 1 · Answer 2

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.