Je cherche une collection qui:
- c'est-à-dire qu'il prend en charge l'insertion d'éléments au "TOP" (les articles les plus récents vont au sommet) - deque.addfirst (.. ) / list.add (0, ..) . Il pourrait s'agir d'une queue , mais l'ordre d'itération doit être inverse - c'est-à-dire que les articles les plus récemment ajoutés devraient venir en premier.
- est limité - c'est-à-dire une limite de 20 articles
- rejette automatiquement les articles les plus anciens (ceux "en bas", ajoutés en premier) lorsque la capacité est atteinte
- Non-blocage - Si la dent est vide, les récupérations ne doivent pas bloquer. Il ne devrait pas non plus bloquer / retourner une exception fausse / nul / jet d'exception est la deque est pleine.
- Concurrent - Les threads multiples doivent pouvoir fonctionner sur celui-ci
Je peux prendre linkedblockingdeque et envelopper dans ma collection personnalisée qui, sur ajouter les opérations vérifie la taille et défait le dernier élément. Y a-t-il une meilleure option?
5 Réponses :
Je crois ce que vous recherchez est une pile délimitée. Il n'y a pas de classe de bibliothèque principale qui fait cela, donc je pense que la meilleure façon de procéder est de prendre une pile non synchronisée (liaison linkedlist) et de l'envelopper dans une collection synchronisée qui fait l'auto-défausse et le retournant NULL sur vide pop. Quelque chose comme ceci: ... ajout de méthodes telles que indisponible selon les besoins, si vous voulez qu'il applique par exemple la liste.
Vous devriez envisager d'utiliser un nouveau mot-clé synchronisé, de sorte que votre objet de verrouillage ne soit pas disponible publiquement.
J'ai fait cette image simple:
public class AutoDiscardingDeque<E> extends LinkedBlockingDeque<E> {
public AutoDiscardingDeque() {
super();
}
public AutoDiscardingDeque(int capacity) {
super(capacity);
}
@Override
public synchronized boolean offerFirst(E e) {
if (remainingCapacity() == 0) {
removeLast();
}
super.offerFirst(e);
return true;
}
}
Vous devez synchroniser les méthodes que vous utilisez, sinon le résultat n'est pas threadsafe - plusieurs threads pourraient exécuter une offreFirst simultanément, entraînant des résultats étranges.
La solution la plus simple et classique est un tampon à anneau délimité qui remplace les éléments les plus anciens.
La mise en œuvre est plutôt facile. Vous avez besoin d'un atomicinteger / long pour Index + AtomicreferenceArray et vous avez une pile à usage gratuit de verrouillage avec 2 méthodes uniquement quelque chose sur les lignes de: Dernière note:
Avoir une opération MOD est une capacité coûteuse et la puissance-de-2 est de préférer, via Offre / Sondage , Aucun Taille () . Les structures les plus concurrentes / sans verrouillage ont des difficultés avec la taille (). Une pile non primordiale peut avoir O (1) mais avec une allocation sur Met. et de longueur () - 1 (également gardes vs débordement long).
Super! (8 de plus à partir ...)
Voici une implémentation qui gère la concurrence et ne retourne jamais NULL.
import com.google.common.base.Optional;
import java.util.Deque;
import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.locks.ReentrantLock;
import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
public class BoundedStack<T> {
private final Deque<T> list = new ConcurrentLinkedDeque<>();
private final int maxEntries;
private final ReentrantLock lock = new ReentrantLock();
public BoundedStack(final int maxEntries) {
checkArgument(maxEntries > 0, "maxEntries must be greater than zero");
this.maxEntries = maxEntries;
}
public void push(final T item) {
checkNotNull(item, "item must not be null");
lock.lock();
try {
list.push(item);
if (list.size() > maxEntries) {
list.removeLast();
}
} finally {
lock.unlock();
}
}
public Optional<T> pop() {
lock.lock();
try {
return Optional.ofNullable(list.poll());
} finally {
lock.unlock();
}
}
public Optional<T> peek() {
return Optional.fromNullable(list.peekFirst());
}
public boolean empty() {
return list.isEmpty();
}
}
Personne n'a rien dit à propos de cette solution, mais c'est le plus moderne de tous: il utilise ConcurentLinkedDequet qui est thread-coffre-fort et il ne renvoie pas null mais un En option . Peut-être que la seule suggestion que je puisse faire 5 ans plus tard est de remplacer les options de Guava pour Java 8. Bon produit!
pour la solution @remery a donné, pourriez-vous ne pas courir dans une condition de course où après Pour la solution @bozho a donné, je penserais qu'un scénario similaire pourrait être possible? La synchronisation se passe sur le si (list.size (liste.Size ()> maxentries) Vous pouvez supprimer à tort le dernier élément si un autre thread exécute POP () Dans cette période et la liste est maintenant à la capacité. Étant donné qu'il n'y a pas de synchronisation de fil sur POP () et Public Void Push (Article T Final T) .
autodiscardingdeque reentrantlock Intérieur LinkedBlockingDequage Ainsi, après avoir exécuté RestantCapacity () Un autre fil pourrait supprimer certains objets de la liste et le removelast () supprimerait un objet supplémentaire?
Je conviens qu'il y a une condition de race potentielle. POP doit également être protégé par le verrou.
"Non-blocage - Si la dent est vide, les récupérations ne doivent pas bloquer. Il ne devrait pas non plus retourner une exception nul / jette. La deque est pleine." - Que devriez-vous arriver alors lors de la récupération d'articles d'une liste vide? Ni exception, ni blocage, ni retourner
null ?Sur récupération
null peut être retourné. Si la drique est pleine , l'élément doit être ajouté et les articles plus anciens - abandonnésJuste une note liéeBlockingDequue n'est pas simultanée.
Vous parlez d'une file d'attente non pas une dentque que je pense.