Hearing of a problem with the PriorityQueue class in Python's
module, I wrote this short program to test the class.
The Python priority queue is modeled here by a list, which is sorted so
as to match the queue's ascending order. The queue data structure
differs from a list in having its size fixed at creation time, making
full() method, which lists do not have. Queues also differ
from lists in that they can be blocked or have a timeout value applied
to their methods, since they are intended for use with threads.
Otherwise, lists have a much larger inventory of functionality.
In the this program, the two objects created are filled with random
numbers, using both
get() so that the queue contracts as
well as expands, and then subjected to four tests:
- The queue should be full (meaning that
full()returns True) after being created and populated.
- The sizes of the objects are compared (using
qsize()for the queue and
len()for the list).
- The objects are compared item by item (using
get()for the queue and indexing for the list).
- After all the values in the queue have been dequeued, it should in
fact be empty, meaning that
This test is repeated in an endless loop which can be terminated with
^C, after which the program reports the number of item-comparisons and
errors found. Failure of either tests 1 or 4, however, will terminate
The user is offered the chance to supply the size of the queue and list, as well as the upper value of the range of random numbers (the lower value is 1). Default values are 10000 for both variables if the user does not enter values.
Note that blocking and timeout is not tested here. The
get_nowait() methods were tested manually but then removed from
Conclusion: No problems have been found in
Queue.PriorityQueue as of
Update, 20111130: I've more recently discussed a more interesting conclusion about this problem: see Lack of Stable Sort in Python's Priority Queue and Apparent Error in Python's Priority Queue.