Structure de données directement accessible Java

Question

J'ai la situation suivante:

1. Une structure de données qui ne peut jamais être prolongé ( je n'ai ajouter des choses dans la queue)
2. J'ai besoin d'être en mesure de garder une trace des éléments que j'ai déjà vu (j'ai un index, et, idéalement, je veux être en mesure de commencer parcourant la liste à partir de cet élément particulier)
3. Je voudrais le lit pour ne jamais bloquer, et l'ajout de le nouvel élément à ne jamais verrouiller la queue de la file d'attente plutôt que de l'ensemble de la file d'attente

C'est une structure qui est fortement modifiée par plusieurs threads.

Quelle serait la meilleure structure de données pour cela?

Liste de tableaux. Ce serait l'idéal pour être en mesure d'accéder directement au dernier élément à l'aide de l'index, mais elle conduit à des modifications simultanées des exceptions. je pourrais le faire de façon synchronisée, mais éviter de verrouillage (ou tout verrouillage à part le dernier élément, comme c'est le seul où il peut y avoir des écritures simultanées pour ajouter de nouveaux éléments)

ConcurrentLinkedQueue. Cela résoudrait mes problèmes de simultanéité, mais le problème est que je dois mémoriser la position courante de l'itération plutôt que d'un index entier. C'est le problème qu'il renvoie un faiblement cohérente itérateur qui n'est pas garanti à rendement des nouveaux objets ont été ajoutés à la liste depuis l'itérateur a été créé (source: javadoc)

ConcurrentHashMap avec l'indice de touches. Ceci a l'avantage que je peux accéder à des données correspondant à l'index correct directement, mais a la question qu'il n'y a pas un getNext opérateur qui me permettra de faire efficacement parcourir les éléments de l'index, index + 1, etc

Vecteurs Cela permettrait de résoudre la plupart de mes problèmes en permettant à quelque chose qui ne va pas faire les modifications simultanées des exceptions et permettre l'accès direct. Toutefois, compte tenu de toutes les méthodes sont synchronisés, le rendement est médiocre par rapport à arraylists. Étant donné que je ne veux plus jamais d'étendre la structure, et de ne pas insérer des enregistrements dans le milieu, je suis réticent à aller pour ce poids lourd de la solution, où se lit aussi souffrir de performances (alors que, compte tenu de mon cas d'utilisation, l'index d'un élément jamais fait de changements, donc il n'y a pas besoin de synchroniser les lectures qui ne sont pas la queue)

Personnalisé structure de données: tenir un tableau des objets que je veux stocker un pointeur sur la queue de ce tableau (le dernier élément de jeu), lors de l'insertion d'un nouvel objet, verrouillage de la queue et de l'objet pointé par la queue. Lorsque l'objet dépasse sa taille actuelle, à un verrouillage opération de redimensionnement.

Quelle serait la meilleure stratégie ou toute autre application plus efficace?

Answer 1

Le CopyOnWriteArrayList structure pourrait résoudre votre problème (java.util.en même temps).

• CopyOnWriteArrayLists est thread-safe, car tous les mutative des opérations sont mis en œuvre par la création d'une copie de la liste.

• Le problème de la ConcurrentModificationException est à éviter car le tableau ne change pas itéré. Le soi-disant snapshot style iterator utilise une référence à l'état de la matrice au moment de l'itérateur a été créé.

• Si vous avez beaucoup plus de lectures que les écritures, utilisez CopyOnWriteArrayList, sinon utilisez Vector.

• Vector introduit un retard de synchronisation pour chaque opération, lors de l' CopyOnWriteArrayList a un délai plus long pour l'écrire (en raison de la copie), mais aucun délai pour la lecture.

• Vector explicite de synchronisation lorsque vous êtes à l'itération (pour les opérations d'écriture ne peut pas être exécuté en même temps), CopyOnWriteArrayList ne le fait pas.

Answer 2

Beaucoup cela sonne comme vous avez besoin d'une distruptor ou dans des mots simples, lock gratuit file d'attente. Je souhaite que je pourrais ajouter un exemple ici, mais j'ai seulement commencé à travailler sur elle hier. Je pourrais aussi vous dire comment il fonctionne, ou vous pouvez lire une bien meilleure explication ici:

L'idée générale est que c'est complètement lock gratuit, il utilise uniquement le CAS des registres (en java AtomicXXX). Je suis simplement tombé en amour avec l'idée.

LMAX

Answer 3

En regardant cela, je suis arrivé à la même solution que @MissingNumber.

Utilisez un ConcurrentHashMap en tant que structure de données de sauvegarde:

• lectures non bloquantes
• ajout de thread-safe

Pour ajouter l'accès aléatoire par index, utilisez un AtomicInteger pour gérer l'index et le définir comme clé pour récupérer les valeurs de la carte.

 public class ConcurrentListMap {

  private final ConcurrentHashMap<Integer, Object> backingMap;
  private final AtomicInteger index;

  public ConcurrentListMap() {
    backingMap = new ConcurrentHashMap();
    index = new AtomicInteger(0);
  }

  public int append(final Object value) {
    final int newIndex = index.incrementAndGet();
    backingMap.put(newIndex, value);
    return newIndex;
  }

  public Object get(final int entry) {
    return backingMap.get(entry);
  }

  public int getTailIndex() {
    return index.get();
  }
}
 

Answer 4

Comme sk2212 dit, je pense qu' java.util.Vector répond à vos trois points.

1. Les vecteurs peuvent être étendues à l'aide de la méthode de add, qui ajoute des éléments à la fin de la liste.
2. Les vecteurs ont la méthode get(index) pour récupérer un élément en béton à l'index spécifique.
3. Les vecteurs sont thread-safe: java Vecteur et le fil de sécurité http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html

Answer 5

ConcurrentHashMap avec l'indice de clés pourrait résoudre votre problème , mais vous devez le faire litte plus de travail à faire ..

Comme le Pseudo-Code suivant .

Map<Integer , ConfiguredObject > myMap = new ConcurrentHashMap<Integer,ConfiguredObject >();

class ConfiguredObject 
{
   YourObject Object;// the object which you want to map for map[key];
   ConfiguredObject Next;//the object which you want to map for map[key+1];
   ConfiguredObject Previous;//the object which you want to map for map[key-1];
   YourObject NextObject;
   YourObject PrevObject;
}

Donc, ce qui devrait résoudre tous vos problèmes.

La simultanéité Framework prend soin .

L'indexation des Touches sont vos index .

Itération , avec ce code, si vous avez d'index vous pouvez utiliser

myMap.get(key).Next ;
myMap.get(key).Previous ;

Tout ce que vous devez faire est de définir configurable à l'objet et à écrire constructeur en conséquence avec soin .

Espérons que cette aide vous.