¿Alguna biblioteca de Java proporciona una implementación de cola de acceso aleatorio?

Question

Estoy implementando una ventana deslizante sobre una secuencia de eventos, en Java. así que quiero una estructura de datos que me permite hacer lo siguiente:

1. añadir al final de la estructura de datos cuando se producen nuevos eventos;

2. eliminar desde el principio de la estructura de datos cuando se procesan eventos antiguos;

3. obtienen acceso aleatorio estándar (size(), get(i)) a los elementos de la estructura de datos; en general, operaciones típicas de "lectura" List;

4. es eficiente para todas las operaciones anteriores;

5. no tiene límites.

No se requiere otro acceso. Y no se requiere seguridad de hilo.

Actualmente estoy haciendo esto con un ArrayList, para poner todo en funcionamiento. Pero quiero algo más eficiente; el método remove(0) (2. arriba) es ineficiente con un ArrayList.

Los números 1. y 2. son operaciones estándar de estilo Queue. Sin embargo, las implementaciones de Queue en el JDK (como ArrayDeque) no permiten get(i) en 3.

Por lo tanto, me pregunto si hay algún bibliotecas por ahí que tienen este tipo de implementación, y son adecuado para uso comercial.

Si no es así, creo que voy a recurro a escribir mi propia ...

Answer 1

La única biblioteca que puedo pensar que implementaría una interfaz de este tipo sería un LinkedList pero francamente no estoy seguro de lo que el las características de rendimiento son

Answer 2

Parece una tarea para un Circular Buffer - mientras esté bien si la cola tiene una capacidad fija. Aunque no sé de ninguna implementación estándar. Pero aquí está a nice recipe to roll your own.

Answer 3

Si tiene una matriz lo suficientemente grande, puede implementar una cola con una matriz básica, y simplemente use un índice como el encabezado de la lista, y use el operador de mod para que pueda envolver si es necesario.

Por lo tanto, básicamente tiene una matriz circular que admite las funciones de inserción y eliminación.

UPDATE:

Es una operación rápida para copiar una matriz a una matriz más grande, por lo que sólo se duplique en tamaño, tal vez, al conseguir cerca del final, y simplemente copiar la matriz, como un paso haciendo insertar. En general, todavía tendrá acceso muy rápido, ya que la norma no debería ser aumentar y copiar.

Answer 4

¿Qué tan rápido entran y salen los eventos de esta cola?

Por un lado, puede tener un búfer circular "suficientemente grande".

Si bien técnicamente es "limitado", puede hacerlo "ilimitado" cultivándolo según sea necesario.

De la misma manera, puede "achicarlo" en términos de capacidad general cuando está "en silencio".

Pero, para muchas aplicaciones, una memoria intermedia circular de capacidad de 100, 1000 o incluso 10000 elementos no tiene límites.

Answer 5

Simplemente lanzando esto como alternativa a la aplicación propia, por lo que lo tomo con un grano de sal: Dependiendo de la frecuencia con la que necesite el acceso aleatorio get(i) y qué rendimiento necesita de él (y qué tan grande es el tamaño de la cola generalmente), siempre puede usar ArrayDeque.toArray()[i] cuando necesite acceder a un elemento. El toArray() usa System.arraycopy() debajo de las cubiertas, lo que debería ser bastante rápido para tamaños pequeños de cola y uso ocasional. Ayudaría a comprender por qué necesita acceso aleatorio a una cola y con qué frecuencia es necesaria, posiblemente haya una manera diferente de implementar su algoritmo sin ella.

Answer 6

Un montón binomial puede tener O (1) inserto amortizado y O (log n) amortizado delete min; Creo que también puede tener O (log ** 2 n) acceso aleatorio amortizado. Queue-push insertaría el elemento en el montón, con números enteros sucesivos como claves.

Con un rbtree, puede hacer queue-push con O (log n) pesimista para todo el acceso insert, delete min y random. Esto se debe a que el árbol tendrá un conjunto contiguo de enteros como las claves, y el elemento k-ésimo de la cola será el elemento en el árbol con la clave k-ésima.

Answer 7

Si realmente debe ser ilimitado, algo así como ConcurrentSkipListMap puede ser útil, si asigna una secuencia de incremento a cada evento para utilizar como la clave en el mapa. Proporcionó métodos como pollFirst/LastEntry. Si puede sacrificar la naturaleza ilimitada, entonces un búfer en anillo puede ser lo que necesita.

Answer 8

Tengo este problema y trataron de resolverlo mediante la copia del código fuente de ArrayDeque y añadiendo algo como:

E get(index){ return elements[(head + index) % size];}