Una cola rápida en Java

Question

Estoy buscando una implementación rápida queue en Java. Veo que LinkedList implementa la interfaz Queue, pero solo será tan rápido como LinkedList ¿verdad? ¿Hay alguna manera de tener una cola que sea más rápida, especialmente para add (solo necesito poll, add y verificar empty). También podría necesitar un PriorityQueue pero todavía no.

Answer 1

Veo que LinkedList implementa la interfaz Queue, pero solo será tan rápido como una LinkedList ¿verdad?

Observando el código fuente, LinkedList es O (1) para las operaciones Queue.add, Queue.poll y Queue.peek.

Espero que sea lo suficientemente rápido.

Answer 2

Si varios hilos van a acceder a la cola, considere usar un ArrayBlockingQueue. De lo contrario, eche un vistazo al ArrayDeque. Desde el ArrayDeque API: es probable que sea más rápido que pila cuando se utiliza como una pila, y más rápido de lo ListaEnlazada

Esta clase cuando se utiliza como una cola.

Específicamente una implementación cola basada en matrices reduce la necesidad de cambiar el tamaño de la matriz subyacente si la matriz existente tiene capacidad suficiente, haciendo así adiciones a la cola generalmente más rápido que LinkedList. Tenga en cuenta que ArrayBlockingQueue es una implementación limitada, mientras que ArrayDeque cambiará de tamaño según sea necesario.

La otra cara es que LinkedList generalmente proporcionará una representación mucho más compacta, especialmente en los casos en que su cola crece y se reduce en una gran cantidad. Por ejemplo, si agregó 10,000,000 de elementos a un ArrayDeque y luego eliminó 9,999,999 elementos, el conjunto subyacente aún sería de una longitud de 10,000,000 mientras que un LinkedList no sufriría este problema.

En realidad, para el acceso de un solo subproceso a una cola sin bloqueo tiendo a favorecer LinkedList. Imagino que las diferencias de rendimiento son tan insignificantes que de todos modos no notarías la diferencia.

Answer 3

Si el rendimiento de una lista vinculada era realmente un problema, una alternativa sería implementar una "cola circular" en una matriz, es decir, una cola donde el punto inicial y final se mueven cuando las entradas se agregan y eliminan. Puedo dar más detalles si te importa. Cuando usaba idiomas que no tenían una biblioteca de colecciones, así era como siempre implementaba las colas porque era más fácil de escribir que una lista vinculada y era más rápido. Pero con las colecciones integradas, el esfuerzo de escribir y depurar mi propia colección para un caso especial no vale la pena el 99% del tiempo: cuando ya está escrito, el hecho de que podía escribirlo de una manera diferente más rápido de lo que podía volver a escribirlo como lo hace Java es casi un hecho irrelevante. Y es probable que cualquier ganancia de rendimiento sea demasiado pequeña para que valga la pena. Subtipo las colecciones existentes para obtener un comportamiento especial que necesito de vez en cuando, pero estoy en apuros para pensar en la última vez que escribí uno desde cero.

Answer 4

Es posible que desee echar un vistazo a http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list que introduce GapList. Esta nueva implementación de lista combina los puntos fuertes de ArrayList y LinkedList.

Por lo tanto, implementa la interfaz Deque, pero también se puede preconfigurar como la mencionada ArrayDeque. Además, también obtiene todas las posibilidades de la interfaz List de forma gratuita.

Answer 5

Comience con una implementación de Cola realmente simplista y giratoria con una actitud "C/C++ like" y un tamaño fijo.

class SimpleQueue<E> 
{ 

int index = 0; 
int head = 0; 
int size = 100; 
int counter = 0; 
E[] data ; 


@SuppressWarnings("unchecked") 
SimpleQueue() 
{ 
    data = (E[]) new Object[size]; 
} 

public void add(E e) 
{ 
    data[index]=e; 
    index=(index+1)%size; 
    counter++; 
} 

public E poll() 
{ 
    E value = data[head]; 
    head=(head+1)%size; 
    counter--; 
    return value; 
} 

public boolean empty() 
{ return counter==0; } 

//Test 
public static void main(String[] args) 
{ 
    SimpleQueue<Integer> s = new SimpleQueue<Integer>(); 

    System.out.println(s.empty()); 

    for(int i=0; i< 10; i++) 
     s.add(i); 

    System.out.println(s.empty()); 

    for(int i=0; i<10; i++) 
     System.out.print(s.poll()+","); 

    System.out.println("\n"+s.empty()); 

} 
} 

Y luego mejorarlo.