Dlaczego funkcja PriorityQueue nie zachowuje się jak kolejka?

Question

Używam PriorityBlockingQueue z polem priorytetu. W moim teście używam System#currentTime() dla priorytetów - te same priorytety są uzyskiwane przez komputer będący tak szybki, że milisekundy są takie same (lub bardziej podobne do milisekund na komputerze ma margines błędu).

Gdy priorytety są takie same, kolejka działa tak, jakby była stosem, co wydaje się dziwne. Czy istnieje alternatywa, aby kolejka działała tak, jakby była normalną kolejką (czyli raczej FIFO niż zachowanie LIFO), gdy priorytety elementów są takie same?

Answer 1

Operacje na tej klasie nie gwarantują uporządkowania elementów o jednakowym priorytecie. Jeśli chcesz wymusić zamówienie, możesz zdefiniować niestandardowe klasy lub komparatory, które używają klucza drugorzędnego, aby zerwać więzy w priorytetach podstawowych.

The PriorityBlockingQueue docs themselves powiedzieć ci to, i jak się z nim obejść, jeśli musisz.

Answer 2

Nie sądzę, że kolejka priorytetowa gwarantuje kolejność uzyskiwania równych elementów. Jedną z opcji jest uelastycznienie priorytetu - wypychanie ujemnego rozmiaru kolejki podczas przesuwania elementu wraz z jego priorytetem i porównywanie tych wartości dla elementów o równym priorytecie.

Answer 3

Wystarczy utworzyć PriorityBlockingQueue z własnym Komparatorem, który uwzględnia czas utworzenia (patrz http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/PriorityBlockingQueue.html#PriorityBlockingQueue(int, java.util.Comparator)). Może zajść potrzeba zmiany kluczy z prostej daty na klasę Data i licznik, gdzie ta ostatnia otrzyma globalnie inkrementację przy każdym utworzeniu (pole statyczne nowej klasy klucza); to nie jest tak naprawdę FIFO, ale raczej First Created First Out.

Lub po prostu zaimplementuj własną klasę PriorityQueueFifo.

Answer 4

Innym rozwiązaniem jest utrzymanie licznika w testach, których używasz dla priorytetu, i które zwiększasz przy każdym wstawieniu. W ten sposób kolejka priorytetowa będzie miała w testach kolejność FIFO, ale będzie wyglądała jak dowolna kolejka priorytetów.