Perché un PriorityQueue non si comporta come una coda?

Question

Sto usando lo PriorityBlockingQueue con un campo prioritario. Nel mio test io uso System#currentTime() per le priorità: le stesse priorità sono ottenute dal fatto che il computer è così veloce che i millisecondi sono uguali (o più come i millisecondi su un PC ha un margine di errore).

Quando le priorità sono le stesse, la coda si comporta come se fosse una pila, il che sembra strano. Esiste un'alternativa per fare in modo che la coda agisca come se fosse una coda normale (cioè FIFO piuttosto che il comportamento LIFO) quando le priorità degli elementi sono le stesse?

Answer 1

Le operazioni su questa classe non garantiscono l'ordine degli elementi con uguale priorità. Se è necessario imporre un ordine, è possibile definire classi o comparatori personalizzati che utilizzano una chiave secondaria per interrompere i legami in valori di priorità primari.

I PriorityBlockingQueue documenti themselves vi dico questo, e come ottenere intorno ad esso se è necessario.

Answer 2

Non penso che la coda di priorità garantisca l'ordine di ottenere elementi uguali. Un'opzione è avere la priorità più complessa: spingere il negativo della dimensione della coda quando si spinge l'elemento insieme alla sua priorità e confrontare questi valori con gli stessi elementi di priorità.

Answer 3

Basta creare un PriorityBlockingQueue con il proprio comparatore che tiene conto del tempo di creazione (vedere http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/PriorityBlockingQueue.html#PriorityBlockingQueue(int, java.util.Comparator)). Potrebbe essere necessario cambiare le chiavi da Data semplice a una classe di Data e contatore, in cui quest'ultimo verrà incrementato globalmente con ogni creazione (campo statico della nuova classe chiave); non è veramente FIFO, ma piuttosto Primo creato.

Oppure implementare la propria classe PriorityQueueFifo.

Answer 4

Un'altra soluzione è mantenere un contatore nei test che si utilizzano per la priorità e aumentare su ogni inserimento. In questo modo la tua coda di priorità avrà l'ordinamento FIFO nei tuoi test, ma sembrerà una coda di priorità arbitraria.