Begrenzte, automatisch verwerfende, nicht blockierende, gleichzeitige Sammlung

Question

Begrenzte, automatisch verwerfende, nicht blockierende, gleichzeitige Sammlung

8

Ich suche nach einer Sammlung, die:

ist ein Deque / List - d. h. unterstützt das Einfügen von Elementen an der "Spitze" (die neuesten Elemente gehen an die Spitze) - deque.addFirst(..) / list.add(0, ..) . Es könnte ein Queue sein, aber die Iterationsreihenfolge sollte umgekehrt sein - d. H. Die zuletzt hinzugefügten Elemente sollten zuerst kommen.
ist beschränkt - d. h. hat eine Grenze von 20 Elementen
löscht automatisch die ältesten Elemente (die "am unteren Rand", zuerst hinzugefügt), wenn die Kapazität erreicht ist
nicht blockierend - Wenn die Deque leer ist, sollten Retrievals nicht blockiert werden. Es sollte auch nicht blockieren / return false / null / throw Ausnahme ist die Deque ist voll.
gleichzeitig - mehrere Threads sollten darauf operieren können

Ich kann LinkedBlockingDeque übernehmen und in meine benutzerdefinierte Sammlung einbinden, die bei add operations die Größe überprüft und die letzten Elemente verwirft. Gibt es eine bessere Option?

java collections

Bozho 23.10.2010, 08:59

quelle

4 Antworten

4

Ich glaube, was Sie suchen, ist ein begrenzter Stapel. Es gibt keine Core-Bibliotheksklasse, die dies tut, daher denke ich, dass dies am besten einen nicht synchronisierten Stapel (LinkedList) macht und ihn in eine synchronisierte Sammlung umwandelt, die das automatische Verwerfen und Zurückgeben von null bei leer liefert Pop. Etwas wie das:

%Vor%

... Methoden wie isEmpty nach Bedarf hinzufügen, wenn Sie zB List implementieren möchten.

Zarkonnen 23.10.2010 09:55

quelle

3

Die einfachste und klassische Lösung ist ein beschränkter Ringpuffer, der die ältesten Elemente außer Kraft setzt.

Die Implementierung ist ziemlich einfach. Sie benötigen einen AtomicInteger / Long für index + AtomicReferenceArray und Sie haben einen lockfreien Allzweck-Stack mit nur 2 Methoden offer/poll , no size() . Die meisten simultanen / lock-free Strukturen haben Schwierigkeiten mit / size (). Nicht überschreibender Stapel kann O (1) haben, aber mit Zuweisung auf put.

Etwas in der Art von:

%Vor%

Letzte Anmerkung: Mod-Operation zu haben ist eine teure und Power-of-2-Kapazität ist vorzuziehen, über &length()-1 (auch Wächter gegen langen Überlauf).

bestsss 06.12.2011 19:06

quelle

2

Hier ist eine Implementierung, die Parallelität behandelt und nie Null zurückgibt.

%Vor%

remery 27.11.2013 14:59

quelle

Tags und Links java collections

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Wie kann ich die Attribute eines Widgets in der __init __ () -Methode von ModelForm ändern?

score 8 · Accepted Answer

Ich habe diese einfache Implementierung gemacht:

%Vor%

Für meine Bedürfnisse ist das ausreichend, aber es sollten gut dokumentierte Methoden sein, die anders sind als addFirst / offerFirst folgen immer noch der Semantik einer blockierenden Deque.