Simple Priority Queue

Question

I am trying to implement A* search on a grid in MATLAB. I am currently using a priority queue class I found here, but it's a bit slow. I tried to write this simple priority queue class in MATLAB:

classdef PQ2 < handle
 properties
 nElements
 indx;
 priorityList;
 valueList;
 end
 methods
 function thePQueue = PQ2()
 thePQueue.nElements = 0;
 thePQueue.priorityList = NaN*ones(500,1);
 thePQueue.valueList{500} = [];
 thePQueue.indx = 1;
 thePQueue.nElements = 0;
 end
 function push(thePQueue, value, priority)
 thePQueue.priorityList(thePQueue.indx) = priority;
 thePQueue.valueList{thePQueue.indx} = value;
 thePQueue.indx = thePQueue.indx + 1;
 thePQueue.nElements = thePQueue.nElements + 1;
 end
 function minPriorityElement = pop(thePQueue)
 if ~thePQueue.isEmpty
 thePQueue.nElements = thePQueue.nElements - 1;
 [~, minPriorityIndx] = min(thePQueue.priorityList);
 minPriorityElement = thePQueue.valueList{minPriorityIndx};
 thePQueue.priorityList(minPriorityIndx) = NaN;
 else
 disp('Queue is empty');
 end
 end
 function flagIsEmpty = isEmpty(thePQueue)
 flagIsEmpty = (thePQueue.nElements == 0);
 end
 end
end

The above code is at least 3 times faster than the one I've mentioned above. I'm getting exactly the same output from these 2 classes, and therefore I believe that the code is correct, but I'm not 100% certain. How can I check it? Is there any other way I could implement the same idea and get a faster result?

Answer 1

[This answer comes a couple of years after the question was posted. The Community User keeps bumping the question because there is an answer without upvotes, not worth up-voting. It also has 2k+ views. So maybe a good review is in order.]

This priority queue implementation has an \$O(1)\$ push operation, and an \$O(n)\$ pop operation, but with \$n\$ being the size of the container (500) rather than the number of elements in the queue. However, the push complexity increases once there have been 500 elements in the queue, because the two data arrays will be reallocated when pushing more elements. Note that this is not 500 elements currently in the queue, but 500 elements having gone through the queue. Used array elements are not re-used.

Code review:

Variable names are excellent: it is clear what they mean without any comments.

The class has no documentation. Documentation on how to use a class or a function is as important (IMO) as the code working correctly.

There are a few statements that could be more concise: NaN*ones(500,1) is the same as NaN(500,1). thePQueue.valueList{500} = [] is better written as thePQueue.valueList = cell(1,500). thePQueue.nElements is set to 0 twice in the constructor.

The constructor PQ2() could take an optional input argument specifying how many elements one expects will go through the queue, to give the queue an appropriate initial size.

Timing:

This is a very fast implementation of a priority queue (as long as it is not used for too long, because performance degrades after 500 elements have been pushed. I wrote the following script to time it, and try to improve on it:

t_push = 0;
t_pop = 0;
for jj=1:100
 pq = PQ2;
 tic;
 for ii=1:500
 pq.push(ii,randi(10000));
 end
 t_push = t_push + toc;
 tic;
 for ii=1:500
 pq.pop;
 end
 t_pop = t_pop + toc;
end
t_push
t_pop

Sure, it's a little simplistic, but so be it. It pushes 500 elements, then pops 500 elements. This is repeated, with a fresh queue, 100 times. The OP's priority queue implementation gives me t_push = 0.1822 and t_pop = 0.2930. I could not make this significantly faster.

I compared this against the classical \$O(\log n)\$ priority queue as implemented in the link provided by the OP. That one gave t_push = 5.9049 and t_pop = 28.1718. No wonder OP thinks it's slow. That implementation has many problems, one is that it tries to do memory management. If we let MATLAB do the memory management (MATLAB will double the storage when appending elements to an array, and does so much more efficiently than this user's code), and store the priorities in a numeric array rather than a cell array, I get t_push = 0.5715 and t_pop = 1.8866, 10 times faster for pushing and 15 times faster for popping. But still nowhere near the speed of the code in this question.

Next, I increased the size of the queue to 5000, and changed the test code to run 10 iterations of pushing and popping 5000 elements. Push times remained similar for both queues, and pop times increased to 0.9861 for OP's code, and 2.8028 for the other implementation. Here one can see the \$O(n)\$ vs \$O(\log n)\$ characteristic of these two implementations. But it is clear that n times a small number is much less than log(n) times a large number.

For very large queues, with millions of elements, I'd stick to one of the other solutions proposed in the Stack Overflow question (the built-in Java queue or a C++ MEX-file implementation).

Answer 2

The code that you provide cannot be faster than the one here as you are using an Array as a Data Structure for implementing the priority queue while the other code uses Heap.

Heap has a worst case complexity of \$O(\log n)\$ while Array has a worst case complexity of \$O(n)\$.

You may have been lucky with your test cases. For larger values of n, Heap is way better than an Array.

• greybeard: With Ali not around for two months, it might take a while to get details just how he reached the conclusion at least 3 times faster - you should try, just the same.
• Cris Luengo: I think that, because of the way that MATLAB code runs, it's perfectly possible for this implementation to be faster than a heap for any useful value of n. Obviously the OP never had more than 500 elements in the queue. A small number times 500 is less than a large number times log2(500).