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.