Priority Queues/Timing and Performance - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:45:00Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:45, 9 October 2019
Line 15:		Line 15:
	==Builtin Timing==		==Builtin Timing==

	Note: code is at git.charlesreid1.com: https://charlesreid1.com~~:3000~~/cs/java/src/master/priority-queues/BuiltinTiming.java		Note: code is at git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/priority-queues/BuiltinTiming.java

	To time built-in priority queue objects I used the following script:		To time built-in priority queue objects I used the following script:

Admin: /* Builtin Timing */

2017-06-26T08:49:41Z

Builtin Timing

← Older revision		Revision as of 08:49, 26 June 2017
Line 14:		Line 14:

	==Builtin Timing==		==Builtin Timing==

			Note: code is at git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/BuiltinTiming.java

	To time built-in priority queue objects I used the following script:		To time built-in priority queue objects I used the following script:
Line 95:		Line 97:
	}		}
	</pre>		</pre>






	==Flags==		==Flags==

Admin at 04:33, 25 June 2017

2017-06-25T04:33:15Z

← Older revision		Revision as of 04:33, 25 June 2017
Line 1:		Line 1:
	~~#REDIRECT~~ [[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.

			This page contains results of timing and performance measurement of priority queues.

			Will start with the note that I spent (wasted) a lot of time trying to implement my own priority queue, only to finally finish and get results that showed it was 2-3 orders of magnitude slower than the built-in priority queue type and horribly slow for anything bigger than 1,000 elements.

			I'm looking to scale to a hundred million.

			==Timing==

			To time, used a simple timing object that wraps the system timer, called Tim the Timer. See [[Tim the Timer]].

			==Builtin Timing==

			To time built-in priority queue objects I used the following script:

			<pre>
			import java.util.LinkedList;
			import java.util.Random;
			import java.util.PriorityQueue;

			/** Timing of Builtin Priority Queue in Java.
			*/
			public class BuiltinTiming {

			// We will perform and time Nops add operations.
			static int Nops = 100;

			// We will do that Ntrials times.
			static int Ntrials = 10000;

			// We will add to a container of size N.
			static int[] Ns = { 1000,2000,3000,4000,5000,
			6000,7000,8000,9000,
			10000,20000,30000,40000,50000,60000,70000,80000,90000,100000};



			/** Run tests */
			public static void main(String[] args) {
			PriorityQueue<Integer> builtin = new PriorityQueue<Integer>();
			System.out.println("---------------------------");
			System.out.println("Add Test: Built-in PriorityQueue");
			add(builtin);
			}



			/** Add test for built-in priority queue. */
			public static void add(PriorityQueue<Integer> q) {

			Random r = new Random();

			System.out.println("N\t\tWalltime Add Tot (ms)\t\tWalltime Add Per 1k (ms)");

			// Gathering stats on each size
			for(int i = 0; i<Ns.length; i++) {

			// set N
			int N = Ns[i];

			// set timer
			Tim tim = new Tim();

			for(int k=0; k<Ntrials; k++) {

			// Start by initializing the container
			q.clear();
			for(int j = 0; j < N; j++) {
			q.add(r.nextInt());
			}

			// Now time adding
			tim.tic();

			for(int m=0; m<Nops; m++) {
			q.add(r.nextInt());
			}

			tim.toc();

			}

			// Now printing out N, total walltime, time per 1k add ops
			double per_op = tim.elapsedms()/(1.0NtrialsNops);
			double per_1kop = (tim.elapsedms()/(1.0NtrialsNops))*1000;

			// done with timing trials, now print out
			// N, add total, ad per 1k operation
			System.out.printf("%d\t\t\t%.4f\t\t\t%.4f\n", N, tim.elapsedms(), per_1kop);
			}
			}
			}
			</pre>






			==Flags==

			{{StacksQueuesFlag}}
			[[Category:Queues]]
			[[Category:Priority Queues]]
			[[Category:Java]]
			[[Category:CS]]
			[[Category:Data Structures]]
			[[Category:Timing]]
			[[Category:Performance]]

Admin: Admin moved page Priority Queues/Timing and Performance to Priority Queues/Timing and Performance/Old

2017-06-25T04:28:56Z

Admin moved page Priority Queues/Timing and Performance to Priority Queues/Timing and Performance/Old

New page

#REDIRECT [[Priority Queues/Timing and Performance/Old]]