[Java] Priority Queue

[Tuberload]

Well this is what I came up with. I have been focusing on using arrays lately, so it does not use any collection classes. I think it is pretty straight forward, clean code. I have done some testing and it all seems to be working correctly, but there could be errors lurking somewhere.

Now my question is this: is this a very effective way to create a priority queue? I haven't seen a whole lot of discussions relating to this sort of thing so I came up with the most efficient solution I could. It is still pretty bare bones as far as features are concerned so it could be enhanced a bit, but it gets the job done.

The only timed test I have done involved adding 50 items of each priority to the queue, retrieving 25 of them (which only removes 25 of the high priority items), and then adding another 50 of each priority. The initial queue size is set to 50 items. During the second addition of 50 items of each priority, the queue has to clean and increment itself to make room. It had an overall average time of about 460ms. Upping the initial queue size and bypassing the queue clean/increment functions has very little effect on the speed of the test dropping it to about an average of 440ms.

Addition: After remembering to remove the put/get/clean/increment notifications I built into the queue the time for the first test dropped down to 0ms. Test 2 below put/gets a much higher amount of items.

The test code is as follows:

Code Select Expand

import tuberload.phuzionbot.PriorityQueue;
import tuberload.phuzionbot.PriorityQueueException;

public class AFTest
{
   private PriorityQueue pq = new PriorityQueue (true);

   public static void main (String[] args)
   {
      AFTest test = new AFTest();
      test.test1();
   }
   
   public void test1()
   {
      byte[] tmpHigh = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
      byte[] tmp;
      
      try
      {
         long start = System.currentTimeMillis();
         
         for (int j = 0; j < 3; j++)
            for (int i = 0; i < 50; i++)
               pq.put (tmpHigh, j);
               
         for (int i = 0; i < 25; i++)
            tmp = pq.get();
            
         for (int j = 0; j < 3; j++)
            for (int i = 0; i < 50; i++)
               pq.put (tmpHigh, j);
         
         long end = System.currentTimeMillis();
         System.out.println (end-start);
         
      } catch (PriorityQueueException exc) {}
   }
}

Test#2 incremented the put loops to 5000, and the get loop to 2500. The resulting time came out to about 65ms. This test was performed leaving the initial queue capacity at 50 so a lot of queue clean/increment operations took place. Upping the initial queue capacity to 500 dropped the time down to about 30ms.

Test#2:

Code Select Expand

         long start = System.currentTimeMillis();
         
         for (int j = 0; j < 3; j++)
            for (int i = 0; i < 5000; i++)
               pq.put (tmpHigh, j);
               
         for (int i = 0; i < 2500; i++)
            tmp = pq.get();
            
         for (int j = 0; j < 3; j++)
            for (int i = 0; i < 5000; i++)
               pq.put (tmpHigh, j);
         
         long end = System.currentTimeMillis();
         System.out.println (end-start);

PriorityQueue.java

Code Select Expand

package tuberload.phuzionbot;
/**
*   The priority queue allows items to be retrieved based on there priority
*   compared to other items in the queue.
*/
public class PriorityQueue
{
   public static final int HIGH_PRIORITY = 0;
   public static final int NORM_PRIORITY = 1;
   public static final int LOW_PRIORITY = 2;
   public static final int INITIAL_CAPACITY = 100;   // buffer size
   // Packet length set to 67 based off of anti-flood discussions on
   // vL forums.
   public static final int PACKET_LENGTH = 67;      // allowed packet length
   
   private byte[][][] priority_queue;
   private int[] put_pos;
   private int[] get_pos;
   
   /**
    *   Initialize the priority queue using default sizes.
    *
    *   @param lowPriorityQueue Enables or disables the use of the low priority
    *         queue.
    */
   public PriorityQueue (boolean lowPriorityQueue)
   {
      int numQueues = lowPriorityQueue ? 3 : 2;
      priority_queue = new byte[numQueues][INITIAL_CAPACITY][];
      
      put_pos = new int[3];
      get_pos = new int[3];
      
      resetPut();
      resetGet();
   }
   /**
    *   Initialize the priority queue with a custom initial capacity.
    *
    *   @param initCapacity The initial capacity of the queue
    *   @param lowPriorityQueue Enables or disables the use of the low priority
    *         queue.
    */
   public PriorityQueue (int initCapacity, boolean lowPriorityQueue)
   {
      int numQueues = lowPriorityQueue ? 3 : 2;
      priority_queue = new byte[numQueues][initCapacity][];
      
      put_pos = new int[3];
      get_pos = new int[3];
      
      resetPut();
      resetGet();
   }
   /**
    *   Put an item into the priority queue
    *
    *   @param data Packet data.
    *   @param priority Data priority.
    */
   public void put (byte[] data, int priority) throws PriorityQueueException
   {
      if (priority > 2 || priority < 0)
         throw new PriorityQueueException ("Invalid priority.");
      
      if (data == null)
         throw new PriorityQueueException ("byte[] data must not be null.");
      
      if (data.length > PACKET_LENGTH)
         throw new PriorityQueueException ("byte[] data is limited to 67 "
            + "bytes in length.");
      
      // handle incrementing or cleaning up of queue to make room
      if (put_pos[priority] >= priority_queue[priority].length)
      {
         int remove = checkRetrieved (priority);
         if (remove > 0)   // remove previously retrieved items
         {
            priority_queue[priority] = clean (remove, priority);
            put_pos[priority] -= remove;
            get_pos[priority] -= remove;
         }
         else // allocate more space for the queue
         {
            priority_queue[priority] = increment (priority);
         }
      }
       priority_queue[priority][put_pos[priority]++] = data;
   }
   /**
    *   Remove previously retrieved items to make space.
    */
   private byte[][] clean (int index, int priority)
   {
      byte[][] tmp = new byte[priority_queue[priority].length][];
      System.arraycopy (priority_queue[priority], index, tmp, 0,
         priority_queue[priority].length-index);
      
      return tmp;
   }
   /**
    *   Increment the size of the queue.
    */
   private byte[][] increment (int priority)
   {
      byte[][] tmp = new byte[priority_queue[priority].length
         + INITIAL_CAPACITY][];
      System.arraycopy (priority_queue[priority], 0, tmp, 0,
         priority_queue[priority].length);
      
      return tmp;
   }
   /**
    *   Check a queue for previously retrieved items.
    *   
    *   @return The number of items that can be removed from the queue.
    */
   private int checkRetrieved (int priority)
   {
      return get_pos[priority];
   }
   /**
    *  Get the next available item in the priority queue.
    *
    *   @return Returns null if no data is found in the queue.
    */
   public byte[] get()
   {
       byte[] data = null;
       
       // loop through priority queue from highest priority to the lowest
       for (int i = 0; i < 3; i++)
       {
          data = priority_queue[i][get_pos[i]];
          if (data != null)
          {
             get_pos[i]++;
             break;
          }
       }
       return data;
   }
   /**
    *   Reset the put positions.
    */
   private void resetPut()
   {
      for (int i = 0; i < 3; i++)
         put_pos[i] = 0;
   }
   /**
    *   Reset the get positions.
    */
   private void resetGet()
   {
      for (int i = 0; i < 3; i++)
         get_pos[i] = 0;
   }
}

PriorityQueueException.java:

Code Select Expand

package tuberload.phuzionbot;
/**
*   PriorityQueueException is thrown wherever a problem occurs.
*/
public class PriorityQueueException extends Exception
{
   private String detail;
   
   public PriorityQueueException (String detail)
   {
      this.detail = detail;
   }
   
   public String toString()
   {
      return "PriorityQueueException[" + detail + "]";
   }
}

[iago]

Although this doesn't answer your question, you should have a look at java.util.TreeSet or java.util.SortedSet.  

<edit> this would probably be better in Java forum than Botdev

[Tuberload]

Although this doesn't answer your question, you should have a look at java.util.TreeSet or java.util.SortedSet.  

<edit> this would probably be better in Java forum than Botdev

I know about the collection classes I was just trying to do it on my own.

I debated on whether to put it here or in the Java forum, but you are probably right.

[Yoni]

Your question is about the efficiency of the algorithm, which is not language-specific (and certainly not botdev). I think the best place for it is General Programming.

You have a small, constant amount of priorities (3). Due to this, yes, your algorithm is efficient.

If you had a larger amount (for instance, if all integers are possible priorities, or if the possible priorities are 1..N for some significantly bigger N), then this algorithm would cease to be efficient.

In that case, to efficiently implement a priority queue, you should implement a heap data structure. A binary heap is the most basic example of this; for much more complicated and heuristically faster options, there are binomial heaps and Fibonacci heaps. Consult a good computer science book (or Google if you can't find one) for more information.

[Tuberload]

Your question is about the efficiency of the algorithm, which is not language-specific (and certainly not botdev). I think the best place for it is General Programming.

You have a small, constant amount of priorities (3). Due to this, yes, your algorithm is efficient.

If you had a larger amount (for instance, if all integers are possible priorities, or if the possible priorities are 1..N for some significantly bigger N), then this algorithm would cease to be efficient.

In that case, to efficiently implement a priority queue, you should implement a heap data structure. A binary heap is the most basic example of this; for much more complicated and heuristically faster options, there are binomial heaps and Fibonacci heaps. Consult a good computer science book (or Google if you can't find one) for more information.

first in largest out

I had a different idea of how to implement a priority queue until you posted. Thanks, you gave me a lot to think about.

[iago]

A heap stored in an array is a really efficient algorithm.  We read about those in Algorithms last year, but I forget how to do it.  It's O(log(n)) for both insertions and deletions, whereas a sorted list is O(n) for either insertions or removals, and O(1) for the rest.  That makes it faster, overall.

But yeah, do what Yoni said, heaps are good stuff.  If you want to hurt your brain, find the book "Introduction to Algorithm Analysis" by Brassard. Although I hate that book, I've read it and it explains how to implement that stuff well.

[Tuberload]

A heap stored in an array is a really efficient algorithm.  We read about those in Algorithms last year, but I forget how to do it.  It's O(log(n)) for both insertions and deletions, whereas a sorted list is O(n) for either insertions or removals, and O(1) for the rest.  That makes it faster, overall.

But yeah, do what Yoni said, heaps are good stuff.  If you want to hurt your brain, find the book "Introduction to Algorithm Analysis" by Brassard. Although I hate that book, I've read it and it explains how to implement that stuff well.

I spent the good part of last night researching data structures. I also spent a good part figuring out where to start, and finaly found myself somewhere around the beginning with Linked Lists.   I am going to take this one step at a time, and try and actualy understand things. My goal is to make my own collections package over time.