Priority Queues/Timing and Performance/Old

Priority Queues

Priority queues are queues that keep items in the queue in a sorted order, so that the minimum (highest priority) item comes out first.

Priority queue timing hypothesis

The hypothesis is that we will see the following behavior for sorted and unsorted implementations of priority queues:

• Unsorted list - add is O(1), min/remove min is O(N)
• Sorted list - add is O(N), min/remove min is O(1)

Priority queue timing class

Basic class for measuring timing and performance of a sorted priority queue.

Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/Timing.java

Class contents:

import java.util.LinkedList;
import java.util.Random;

/** Timing class: measure big-O complexity and runtime of data structures.
 *
 * Compare algorithms, test structures, and verify expected big-O behavior.
 *
 */
public class Timing {

	// Tests
	public static void main(String[] args) {
		sorted_timing();
	}

	/** Time sorted priority queue. */
	public static void sorted_timing() {

		// This generates CSV files to verify the following information:
		// - add method is O(N)
		// - remove min method is O(1)

		StringBuffer sb = new StringBuffer();

		sb.append("N, Walltime Add (ms), Walltime Rm Min (ms)\n");

		int ntrials = 200;
		Random r = new Random();

		// Loop over values of N
		for(int N = (int)(5E3); N <= (int)(5E5); N+=2500) {

			Tim add_tim = new Tim();
			Tim rm_tim = new Tim();

			// Trials counter is always k for Kafka
			for(int k = 0; k<ntrials; k++) {
				// Each trial is a different sequence of random numbers,
				// but the sequence matches between tests of different collection types
				SortedPriorityQueue<Integer> q = new SortedPriorityQueue<Integer>();
				Integer key = new Integer( r.nextInt() );
				Integer val = new Integer( r.nextInt() );

				add_tim.tic();
        		for(int i=0; i<N; i++) {
					q.add(key,val);
				}
				add_tim.toc();

				rm_tim.tic();
        		for(int i=0; i<N; i++) {
					q.removeMin();
				}
				rm_tim.toc();
			}

			sb.append( String.format("%d, ",N) );
			sb.append( String.format("%.3f, ", add_tim.elapsedms()) );
			sb.append( String.format("%.3f  ",  rm_tim.elapsedms()) );
			sb.append("\n");
		}

		System.out.println(sb.toString());
	}
}

Priority queue timing results

Sorted priority queue

The results below are for a sorted priority queue. For a sorted priority queue, the minimum is always at the front, and so removal is an O(1) operation. When items are added to the priority queue they are added in order, so add is an O(N) operation. If you squint and look sideways, you can see a barely perceptible linear increase in the cost of add, versus the more flat curve for removal for a sorted list.