thread - Estructura de datos directamente accesible Java

java thread pool example

Question

Tengo la siguiente situación:

1. Una estructura de datos que solo puede extenderse (solo agrego cosas en la cola)
2. Necesito poder hacer un seguimiento de los elementos que ya he visto (tengo un índice, y lo ideal sería poder comenzar a recorrer la lista nuevamente desde este elemento en particular)
3. Me gustaría que las lecturas nunca se bloqueen, y la adición del nuevo elemento solo bloqueará el final de la cola en lugar de la cola completa.

Esta es una estructura que está muy modificada por múltiples hilos.

¿Cuál sería la mejor estructura de datos para esto?

ArrayList . Esto sería ideal para poder acceder directamente al último elemento visto usando el índice, pero conduce a excepciones de modificaciones simultáneas. podría sincronizarlo, pero me gustaría evitar el bloqueo (o cualquier bloqueo aparte del último elemento, ya que es el único donde podría haber escrituras simultáneas para agregar nuevos elementos)

ConcurrentLinkedQueue . Esto resolvería mi problema de simultaneidad, pero tiene el problema de que tendría que almacenar la posición actual de la iteración en lugar de un índice entero. Esto tiene el problema de que devuelve un iterador débilmente consistente que no garantiza devolver nuevos objetos que se han agregado a la lista desde que se creó el iterador (fuente: javadoc)

ConcurrentHashMap con índice como claves. Esto tiene la ventaja de que puedo acceder directamente a los datos correspondientes al índice correcto, pero tengo el problema de que no hay un operador "getNext" que me permita atravesar de manera eficiente los elementos del índice, al índice + 1, etc.

Vectores Esto resolvería la mayoría de mis problemas al permitir algo que no arrojará excepciones de modificación concurrentes y permitirá el acceso directo. Sin embargo, dado que todos los métodos están sincronizados, el rendimiento es pobre en comparación con las listas de arreglos. Dado que solo quiero extender la estructura y no insertar registros en el medio, soy reacio a buscar esta solución de gran peso, donde las lecturas también sufren un golpe de rendimiento (mientras que, dado mi uso, el índice de un elemento en realidad nunca cambia, por lo que no es necesario sincronizar las lecturas que no son la cola)

Estructura de datos personalizada : mantenga una matriz de los objetos que deseo almacenar y un puntero a la cola de esta matriz (el último conjunto de elementos), al insertar un nuevo objeto, bloquee la cola y el objeto al que apunta la cola. Cuando el objeto excede su tamaño actual, a una operación de cambio de tamaño de bloqueo.

¿Cuál sería la mejor estrategia / cualquier otra implementación más eficiente?

Answer 1

Lista de arreglo. Esto sería ideal para poder acceder directamente al último elemento visto usando el índice, pero conduce a excepciones de modificaciones simultáneas. podría sincronizarlo, pero me gustaría evitar el bloqueo (o cualquier bloqueo aparte del último elemento, ya que es el único donde podría haber escrituras simultáneas para agregar nuevos elementos)

Puede usar una Lista temporal para colocar los objetos que se agregarán y cuando se desbloquea, agregue el contenido de tmpList a ArrayList.

Answer 2

¿Tienes que usar una sola estructura de datos? ¿Qué sucede si utiliza dos: uno para la parte "activa" de la lista y otro para la lista "elementos que ha visto"? Puede usar un Vector para la parte "activa" y algún tipo de administrador que periódicamente mueve los elementos a la lista de "elementos que ha visto".

Answer 3

Al analizar esto, llegué a la misma solución que @MissingNumber.

Use un ConcurrentHashMap como estructura de datos de respaldo:

• lecturas sin bloqueo
• a prueba de hilos anexa

Para agregar el acceso aleatorio por índice, use un AtomicInteger para mantener el índice y ponerlo como la clave para recuperar los valores del mapa.

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

Como dijo sk2212 , creo que java.util.Vector cumple con tus tres puntos.

1. Los vectores se pueden extender utilizando el método add , que agrega elementos al final de la lista.
2. Los vectores tienen el método get(index) para recuperar un elemento concreto en un índice específico.
3. Los vectores son seguros para subprocesos: java Vector y seguridad de subprocesos http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html

Answer 5

Esto suena como si necesitaras un distribuidor o, en palabras simples, una cola libre de bloqueo. Desearía poder agregar un ejemplo aquí, pero empecé a trabajar en él ayer. También podría decirte cómo funciona, o puedes leer una explicación mucho mejor aquí:

La idea general es que esto está completamente libre de bloqueos, solo usa los registros CAS (en Java AtomicXXX). Simplemente me enamoré de la idea.

LMAX

Answer 6

La estructura CopyOnWriteArrayList podría resolver su problema (java.util.concurrent).

• CopyOnWriteArrayList s es seguro para subprocesos porque todas las operaciones mutativas se implementan creando una copia de la lista.

• Se evita el problema de ConcurrentModificationException porque la matriz no cambia mientras se itera. El llamado snapshot style iterator usa una referencia al estado de la matriz cuando se creó el iterador.

• Si tiene muchas más lecturas que escrituras, use CopyOnWriteArrayList ; de lo contrario, use Vector .

• Vector introduce un pequeño retraso de sincronización para cada operación, cuando CopyOnWriteArrayList tiene un retraso más largo para la escritura (debido a la copia) pero no demora para las lecturas.

• Vector requiere sincronización explícita cuando lo itera (por lo que las operaciones de escritura no se pueden ejecutar al mismo tiempo), CopyOnWriteArrayList no lo hace.

Answer 7

Voy a ofrecer ConcurrentSkipListSet porque:

1) Es concurrente.

2) Es un Set .

3) También es NavigableSet , por lo tanto también un SortedSet .

Esto le da mucha flexibilidad, y probablemente no necesitará muchas de ellas. Pero aparte de "No puede agregar elementos que ya existen" (que no sé si es un problema, o una bendición) parece satisfacer todos sus requisitos.

Answer 8

ConcurrentHashMap con índice como claves podría resolver su problema, pero necesita hacer más trabajo para hacerlo.

Me gusta seguir el Pseudo Código.

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;
}

Entonces esto debería resolver todos tus problemas.

Concurrency Framework se ocupa.

Las claves de indexación son sus índices.

Iteraciones , con este código si tiene índice puede usar

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

Todo lo que necesita hacer es definir el objeto configurable y escribir el constructor de acuerdo con cuidado.

Espero que esto te ayude