Concurrent Set-Warteschlange
Vielleicht ist das eine dumme Frage, aber ich kann nicht scheinen zu finden, eine offensichtliche Antwort.
Ich brauche eine gleichzeitige FIFO-Warteschlange enthält nur eindeutige Werte. Versuch, einen Wert hinzuzufügen, der bereits in der Warteschlange einfach ignoriert diesen Wert. Die, wenn Sie nicht für die thread-Sicherheit wäre trivial. Gibt es eine Datenstruktur in Java oder vielleicht ein code snipit auf der interwebs, die dieses Verhalten aufweist?
Kommentar zu dem Problem
Leider ist der Begriff "Warteschleife" ist mehrdeutig, da einige Leser es implizit bedeutet "FIFO-queue", während auf anderen es hat die Allgemeine
java.util.Warteschlange
Bedeutung, was im Grunde bedeutet jede Sammlung etwas Konzept einer "Kopf-element", egal, ob dieses element ist das erste-in oder nicht. So! Welche ist es? FIFO, sorry für die Unterlassung =)
InformationsquelleAutor der Frage Steve Skrla | 2010-06-25
Du musst angemeldet sein, um einen Kommentar abzugeben.
Wenn Sie wollen eine bessere Parallelität als die vollständige Synchronisation, es gibt eine Möglichkeit, die ich kenne, es zu tun, mit einer ConcurrentHashMap als backing-Karte. Das folgende ist eine Skizze nur.
Ist nicht alles Sonnenschein bei diesem Ansatz. Wir haben keinen anständigen Weg zu wählen Sie ein head-element zu verwenden, mit der backing-Karte
entrySet().iterator().next()
, mit der Folge, dass die Karte bekommt mehr und mehr unausgeglichen, wie die Zeit vergeht. Dieses unbalancing ist ein problem, sowohl wegen der größeren Eimer Kollisionen und größer segment Streit.Hinweis: dieser code verwendet Guave an ein paar stellen.
InformationsquelleAutor der Antwort Kevin Bourrillion
Gibt es nicht eine built-in-Sammlung, die diese unterstützt. Es gibt einige gleichzeitige
Set
Implementierungen, die verwendet werden könnten, zusammen mit einer gleichzeitigenQueue
.Zum Beispiel, wird ein Element der Warteschlange Hinzugefügt, erst nachdem es erfolgreich Hinzugefügt wurde der Satz, und jedes Element aus der Warteschlange entfernt wird entfernt. In diesem Fall wird der Inhalt der Warteschlange, die logisch sind, wirklich alles, was in den Satz, und die Warteschlange wird nur verwendet, um nachzuverfolgen, die Bestellung und bieten eine effiziente
take()
undpoll()
Operationen nur auf eineBlockingQueue
.InformationsquelleAutor der Antwort erickson
Einen java.util.gleichzeitige.ConcurrentLinkedQueue bekommt Sie die meisten der Weg dorthin.
Wickeln Sie die ConcurrentLinkedQueue mit Ihrer eigenen Klasse, der prüft, für die Einmaligkeit eines hinzufügen. Ihr code muss thread-sicher.
InformationsquelleAutor der Antwort Gilbert Le Blanc
Ich würde eine synchronisierte LinkedHashSet, bis es war genug Rechtfertigung alternativen in Betracht ziehen. Der primäre Vorteil, dass eine gleichzeitige Lösung anbieten könnte, ist lock-splitting).
Einfachsten gleichzeitige Ansatz wäre eine ConcurrentHashMap (als ein Satz) und eine ConcurrentLinkedQueue. Die Reihenfolge der Operationen würde die gewünschte Einschränkung. Ein Angebot (), zuerst führen Sie eine CHM - #putIfAbsent() und bei Erfolg einfügen in der CLQ. Ein poll() nehmen würde, aus der CLQ und entfernen Sie Sie dann aus dem CHM. Dies bedeutet, dass wir überlegen, einen Eintrag in unsere Warteschlange, wenn es in der Karte und der CLQ bietet die Bestellung. Die Leistung könnte dann angepasst werden, durch die Erhöhung der map concurrencyLevel. Wenn Sie tolerant sind, um zusätzliche rassig-ness, dann ein Billig-CHM - #get() könnte als eine angemessene Voraussetzung (aber es leiden kann durch eine etwas veraltete Ansicht).
InformationsquelleAutor der Antwort Ben Manes
Was meinst du mit einer gleichzeitigen Warteschlange mit Set-Semantik? Wenn du meinst das wirklich gleichzeitige Struktur (im Gegensatz zu einer thread-safe-Struktur), dann würde ich behaupten, dass Sie Fragen für ein pony.
Was passiert zum Beispiel, wenn Sie anrufen
put(element)
und erkennen, dass etwas schon da ist, die sofort entfernt wird? Zum Beispiel, was bedeutet es in Ihrem Fall, wennoffer(element) || queue.contains(element)
zurückfalse
?Diese Dinge müssen oft Gedanken über etwas anders in einer gleichzeitigen Welt so oft ist nichts so, wie es scheint, es sei denn, Sie beenden die Welt (lock it down). Ansonsten sind Sie in der Regel suchen zu, etwas in der Vergangenheit. Also, was du eigentlich machen willst?
InformationsquelleAutor der Antwort Jed Wesley-Smith
Vielleicht verlängern ArrayBlockingQueue. Um Zugang zu den (Paket-Zugang) Schloss, hatte ich, um meiner sub-Klasse innerhalb des gleichen Pakets. Nachteil: habe ich noch nicht getestet.
InformationsquelleAutor der Antwort Chris
Eine einfache Antwort für eine Warteschlange mit einzigartigen Objekten wie folgt:
InformationsquelleAutor der Antwort omid gholami