Una coda veloce in Java

Question

Sto cercando un'implementazione veloce queue in Java. Vedo che l'interfaccia Queue implementa l'interfaccia LinkedList, ma sarà veloce solo come una? C'è un modo per avere una coda che sarà più veloce in particolare per add (ho solo bisogno di poll, add e controllare per empty). In fondo alla linea potrei anche aver bisogno di un PriorityQueue ma non ancora.

Answer 1

Vedo che LinkedList implementa l'interfaccia Queue, ma sarà veloce quanto una LinkedList?

Eyeballing del codice sorgente, LinkedList è O (1) per le operazioni Queue.add, Queue.poll e Queue.peek.

Spero sia abbastanza veloce.

Answer 2

Se più thread stanno per accedere alla coda, prendere in considerazione l'utilizzo di ArrayBlockingQueue. Altrimenti dai un'occhiata a ArrayDeque. Dal ArrayDeque API:

Questa classe è probabile che sia più veloce di Pila quando viene utilizzato come una pila, e più veloce rispetto ListaLinkata quando viene utilizzato come una coda.

particolare un'implementazione coda basata su array riduce la necessità di ridimensionare la matrice sottostante, se la matrice esistente ha una capacità sufficiente, rendendo così aggiunte alla coda generalmente più veloce di LinkedList. Si noti che ArrayBlockingQueue è un'implementazione limitata mentre ArrayDeque verrà ridimensionata come richiesto.

Il rovescio della medaglia è che LinkedList fornirà in genere una rappresentazione molto più compatta, in particolare nei casi in cui la coda cresce e si restringe di una grande quantità. Ad esempio, se hai aggiunto 10.000.000 elementi a ArrayDeque e quindi rimosso 9.999.999 elementi, l'array sottostante sarebbe ancora di lunghezza 10.000.000 mentre uno LinkedList non soffrirebbe di questo problema.

In realtà, per l'accesso a thread singolo a una coda non bloccante, tendo a favorire lo LinkedList. Immagino che le differenze di rendimento siano così trascurabili che non noterai comunque la differenza.

Answer 3

Se le prestazioni di un elenco collegato rappresentavano realmente un problema, un'alternativa consisteva nell'implementare una "coda circolare" in un array, ovvero una coda in cui il punto di inizio e fine si sposta mentre le voci vengono aggiunte ed eliminate. Posso dare maggiori dettagli se ti interessa. Quando usavo le lingue che non avevano una libreria di collezioni, questo era il modo in cui ho sempre implementato le code perché era più facile scrivere di una lista collegata ed era più veloce. Ma con le raccolte predefinite, lo sforzo di scrivere e debug della mia collezione per un caso speciale non vale la pena il 99% delle volte: quando è già scritto, il fatto che potrei scrivere in un modo diverso più velocemente di quanto avrei potuto ri-scriverlo come fa Java è praticamente un fatto irrilevante. E qualsiasi guadagno in termini di prestazioni è probabilmente troppo piccolo per valerne la pena. Sottotipo le raccolte esistenti per ottenere un comportamento speciale di cui ho bisogno di tanto in tanto, ma ho difficoltà a pensare all'ultima volta in cui ne ho scritto uno da zero.

Answer 4

Si consiglia di dare un'occhiata a http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list che introduce GapList. Questa nuova implementazione di elenchi combina i punti di forza di ArrayList e LinkedList.

Implementa quindi l'interfaccia Deque, ma può anche essere preimpostata come sopra menzionata ArrayDeque. Inoltre, hai anche tutte le possibilità dell'interfaccia gratuitamente.

Answer 5

Iniziare con una rotazione veramente semplicistica Implementazione della coda con atteggiamento "C/C++ come" e dimensioni fisse.

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()); 

} 
} 

E quindi migliorarlo.