Checking Runtimes of Algorithms

[Max Brown]

Hi,

I'm currently doing a sorting project where we have to implement random arrays for 10, 100, 1000, 10000, and 100000 elements per sorting algorithm. I've created a method to generate the arrays and I've done some of the sorting methods in order to calculate clock times, array access times, and comparison times. I'm running into a problem with a few of my algorithms. For the one method algorithms like bubble sort and selection sort, I was fine. But when I got into merge sort and quick sort, I see some issues popping up. Can someone please take a look at what I've done wrong?

Generate array

	public int[] generate(int n) {
		int[] arr = new int[n];
		for(int i=0; i < n; i++) {
			arr[i] = rand.nextInt(100);
		}

		return arr;
	}

Analysis

	public void analysis() {
		System.out.println("Clock Times: " + (clockTimeEnd - clockTimeStart));
		System.out.println("Comparison Times: " + (comparisonEnd - comparisonStart));
		System.out.println("Array Access Times: " + (comparisonEnd - comparisonStart));
	}

mergesort

	public void mergeSort(int[] a) {
		if(a.length >= 2) {
			int[] left = Arrays.copyOfRange(a, 0, a.length/2);
			int[] right = Arrays.copyOfRange(a, a.length/2, a.length);

			mergeSort(left);
			mergeSort(right);

			merge(left, right, a);
		}
	}

	public void merge(int[] left, int[] right, int[] a) {
		clockTimeStart = System.currentTimeMillis();
		int i1 = 0, i2 = 0;
		for( int i=0; i < a.length; i++ ) {
			comparisonStart = System.currentTimeMillis();
			if(i2 >= right.length || (i1 < left.length && left[i1] < right[i2] )) {
				a[i] = left[i1];
				i1++;
			}

			else {
				arrayAccessStart = System.currentTimeMillis();
				a[i] = right[i2];
				arrayAccessEnd = System.currentTimeMillis();
				i2++;
			}
			comparisonEnd = System.currentTimeMillis();
		}
		clockTimeEnd = System.currentTimeMillis();
		analysis();
	}

quicksort with insertion sort

	
	private void quicksort(int[] a, int low, int high) {
	    clockTimeStart = System.currentTimeMillis();
		int size = (high + 1) - low;
		comparisonStart = System.currentTimeMillis();
		if(low < high) {
			if( size <= 1024 ) {
				insertionsort2(a, low, high);
			} else {
				int pivot = partition(a, low, high);
				arrayAccessStart = System.currentTimeMillis();
				quicksort(a, low, pivot);
				quicksort(a, pivot+1, high);
				arrayAccessEnd = System.currentTimeMillis();
			}
		}
		comparisonEnd = System.currentTimeMillis();
		clockTimeEnd = System.currentTimeMillis();
		analysis();
	}
	private static void insertionsort2(int[] a, int low, int high) {
		for (int i = low+1; i <= high; ++i) {
			int temp = a[i], j = i-1;          // Save the current element
			while (j >= low && a[j] > temp) {  // Shift all elements greater than it to the right
				a[j+1] = a[j];
				--j;
			}
			a[j+1] = temp;                     // Insert the current element into the correct spot
		}
	}

	/* This function takes last element as pivot, 
    places the pivot element at its correct 
    position in sorted array, and places all 
    smaller (smaller than pivot) to left of 
    pivot and all greater elements to right 
    of pivot */
	int partition(int arr[], int low, int high) 
	{ 
		int pivot = arr[high];  
		int i = (low-1); // index of smaller element 
		for (int j=low; j<high; j++) 
		{ 
			// If current element is smaller than or 
			// equal to pivot 
			comparisonStart = System.currentTimeMillis();
			if (arr[j] <= pivot) 
			{ 
				i++; 

				// swap arr[i] and arr[j] 
				int temp = arr[i]; 
				arr[i] = arr[j]; 
				arr[j] = temp; 
			} 
			comparisonEnd = System.currentTimeMillis();
		} 

		// swap arr[i+1] and arr[high] (or pivot) 
		arrayAccessStart = System.currentTimeMillis();
		int temp = arr[i+1]; 
		arr[i+1] = arr[high-1]; 
		arr[high-1] = temp; 
		arrayAccessEnd = System.currentTimeMillis();

		return i+1; 
	} 

The issue popped up with QuickSort alone as well.
This is how I'm calling it in the main method

	public static void main(String[] args) {
		Project1 p = new Project1();
		int[] arr1 = p.generate(100000);
		//p.mergeSort(arr1);
		//p.bubbleSort(arr1);
		//p.selectionSort(arr1);
		//p.insertionsort(arr1);
		p.quicksort(arr1, 0, arr1.length-1);
	}

Thank you for your help!

[Carey Brown]

You'll be wanting to do the start/end time gathering and analysis outside of any of your sort methods, i.e. in main().

[Carey Brown]

Your array access and comparison times are far below the granularity of milliseconds. I don't think you can capture this with nano seconds. In general, to measure the performance of something that something must be run many times and the overall difference in time calculated and divided by the number of times run. In your setup you can do this for any sort method but not the array times within the methods.

[Max Brown]

So I moved out the clock time calculation and analysis to the main method. So far, its been working for everything but when I bring up the 100000 element arrays, I get errors
Main Method

		p.clockTimeStart = System.currentTimeMillis();
		p.quicksort(arr1, 0, arr1.length);

		//p.quicksorthybrid(arr1, 0, arr1.length-1);
		p.clockTimeEnd = System.currentTimeMillis();
		
		//p.mergeSort(arr1);
		//p.bubbleSort(arr1);
		//p.selectionSort(arr1);
		//p.insertionsort(arr1);
		p.analysis();
	}

quicksort regular

 void quicksort(int arr[], int low, int high) 
    { 
        if (low < high) 
        { 
            /* pi is partitioning index, arr[pi] is  
              now at right place */
            int pi = partition(arr, low, high); 
  
            // Recursively sort elements before 
            // partition and after partition 
            quicksort(arr, low, pi-1); 
            quicksort(arr, pi+1, high); 
        } 
    } 

partition

	int partition(int arr[], int low, int high) 
	{ 
		int pivot = arr[high];  
		int i = (low-1); // index of smaller element 
		for (int j=low; j<high; j++) 
		{ 
			// If current element is smaller than or 
			// equal to pivot 
			comparisonStart = System.currentTimeMillis();
			if (arr[j] <= pivot) 
			{ 
				i++; 

				// swap arr[i] and arr[j] 
				int temp = arr[i]; 
				arr[i] = arr[j]; 
				arr[j] = temp; 
			} 
			comparisonEnd = System.currentTimeMillis();
		} 

		// swap arr[i+1] and arr[high] (or pivot) 
		arrayAccessStart = System.currentTimeMillis();
		int temp = arr[i+1]; 
		arr[i+1] = arr[high-1]; 
		arr[high-1] = temp; 
		arrayAccessEnd = System.currentTimeMillis();

		return i+1; 
	} 

Error:

Exception in thread "main" java.lang.StackOverflowError
	at project1.Project1.quicksort(Project1.java:43)
	at project1.Project1.quicksort(Project1.java:47)
	at project1.Project1.quicksort(Project1.java:47)
	at project1.Project1.quicksort(Project1.java:47)
	at project1.Project1.quicksort(Project1.java:47)
	at project1.Project1.quicksort(Project1.java:47)
	at project1.Project1.quicksort(Project1.java:47)
	at project1.Project1.quicksort(Project1.java:47)
	at project1.Project1.quicksort(Project1.java:47)

So where would I place the array access checks?

[Norm Radder]

Exception in thread "main" java.lang.StackOverflowError
   at project1.Project1.quicksort(Project1.java:43)
   at project1.Project1.quicksort(Project1.java:47)

Looks like there is a recursive call at line 47.  Can you post the code that shows lines 43 and 47

[Max Brown]

This is where the error is

            quicksort(arr, low, pi-1); 
            quicksort(arr, pi+1, high); 

it only shows up for 100000 elements. works otherwise

[Jim Venolia]

If you really want to get tangled up in your underwear take a look at the Time Stamp Register.  It's a 64 bit register that counts clock ticks.  Back in the day it was a great way to get nanosecond resolution.  Then some perverted boffins invented stuff like multiple cores, threads, and CPUs that could adjust their clock frequency based on demand.  If you're clever you can work around these, I'm not that clever.

If you want I might still have some C++ code I wrote about 20 years ago that uses the register, I'd just have to dig around to find it.

Then again, I have no idea how you could read a hardware register in Java.

Caveat:  I haven't looked at this register in 20 years, I'm not even sure it still exists in modern CPUs.  It may also be Intel specific.

Edit:  Looky what I found.

[Campbell Ritchie]

Can you actually reach that register from Java®?

I would suggest a few things for simple performance testing:-

1: If you are doing anything beyond the most basic and simplest timings, get yourself a profiler program.

2: You have an optimising compiler and runtime. Before you try any timings, be sure to run all the code you are going to test, so you get > 10,000 iterations. For example, sort a few 1,000,000 element arrays before you test anything. That will encourage the JVM to implement all the optimisations.

3: Timings are not exact, and vary. I have found cses where alorithm A runs 10% faster than algorithm B 75% of the time, and the other 25% of the time alorithm B is 10% faster! Ignore any differences that small.

4: Try the System#nanoTime() method for timings.

I am adding this disucssion to our preformance forum.