How to improve the speed of my class?

Question

I'm running this and I am being told it would not run fast enough. What is a good way to increase the speed of this running class? I am guessing I would need to change my nested while loops. That is the only thing I can think of. The if statements should all be linear...

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class QSortLab {

    static int findpivot(Comparable[] A, int i, int j) {
        return (i + j) / 2;
    }

    static <E> void swap(E[] A, int p1, int p2) {
        E temp = A[p1];
        A[p1] = A[p2];
        A[p2] = temp;
    }

    static void quicksort(Comparable[] A, int i, int j) { // Quicksort
        int pivotindex = findpivot(A, i, j);  // Pick a pivot
        swap(A, pivotindex, j);               // Stick pivot at end
        int k = partition(A, i, j-1, A[j]);
        swap(A, k, j);                        // Put pivot in place
        if ((k-i) > 1) quicksort(A, i, k-1);  // Sort left partition
        if ((j-k) > 1) quicksort(A, k+1, j);  // Sort right partition
    }

    static int partition(Comparable[] A, int left, int right, Comparable pivot) {
        while (left <= right) { // Move bounds inward until they meet
            while (A[left].compareTo(pivot) < 0) left++;
            while ((right >= left) && (A[right].compareTo(pivot) >= 0)) right--;
            if (right > left) swap(A, left, right); // Swap out-of-place values
        }
        return left;            // Return first position in right partition
    }
}

Never do performance optimization unless you have **verified** that there is a performance problem at all and which part of your code it is. — Timothy Truckle, Oct 27 '16 at 22:19
Have you profiled the running code to see where the bottleneck is? — bradimus, Oct 27 '16 at 22:39

score 1 · Answer 1 · edited May 23 '17 at 12:32

What do you mean you need to change your nested while loops? Quick Sort is defined by those features. Removing wouldn't function properly.

As for optimization, by default it should be known that primitives vs objects tend to be different. E.g. primitives on stack/heap to keep stack small & heap stores object with refs able to be on stack.

So let's test some stuff

primitive quick sort (from here)
Integer quick sort (same code as above, but with Integer class)
Your original posted code
Your original posted code (w/ several edits)

Here's the entire code I used.

import java.util.Random;

public class App {

    public static final int ARR_SIZE = 1000;
    public static final int TEST_ITERS = 10000;
    public static Random RANDOM = new Random();

    public static void main(String[] args) {
        int[] a = new int[ARR_SIZE];
        Integer[] b = new Integer[ARR_SIZE];
        Integer[] c = new Integer[ARR_SIZE];
        Integer[] d = new Integer[ARR_SIZE];

        long sum = 0, start = 0, end = 0;
        for (int i = 0; i < TEST_ITERS; ++i) {
            for (int j = 0; j < ARR_SIZE; ++j)
                a[j] = RANDOM.nextInt();
            start = System.nanoTime();
            quickSort(a, 0, a.length - 1);
            end = System.nanoTime();
            sum += (end - start);
        }
        System.out.println((sum / TEST_ITERS) + " nano, qs avg - 'int'");

        sum = 0;
        for (int i = 0; i < TEST_ITERS; ++i) {
            for (int j = 0; j < ARR_SIZE; ++j)
                b[j] = RANDOM.nextInt();
            start = System.nanoTime();
            quickSort(b, 0, b.length - 1);
            end = System.nanoTime();
            sum += (end - start);
        }
        System.out.println((sum / TEST_ITERS) + " nano, qs avg - 'Integer'");

        sum = 0;
        for (int i = 0; i < TEST_ITERS; ++i) {
            for (int j = 0; j < ARR_SIZE; ++j)
                c[j] = RANDOM.nextInt();
            start = System.nanoTime();
            quicksort(c, 0, c.length - 1);
            end = System.nanoTime();
            sum += (end - start);
        }
        System.out.println((sum / TEST_ITERS) + " nano, qs avg - 'Comparable' (SO user code)");

        sum = 0;
        for (int i = 0; i < TEST_ITERS; ++i) {
            for (int j = 0; j < ARR_SIZE; ++j)
                d[j] = RANDOM.nextInt();
            start = System.nanoTime();
            qs_quicksort(d, 0, d.length - 1);
            end = System.nanoTime();
            sum += (end - start);
        }
        System.out.println((sum / TEST_ITERS) + " nano, qs avg - 'Comparable' (SO user code - edit)");

        for (int i = 0; i < ARR_SIZE; ++i) {
            final int n = RANDOM.nextInt();
            a[i] = n;
            b[i] = n;
            c[i] = n;
            d[i] = n;
        }
        quickSort(a, 0, a.length - 1);
        Integer[] aConv = new Integer[ARR_SIZE];
        for (int i = 0; i < ARR_SIZE; ++i)
            aConv[i] = a[i];
        quickSort(b, 0, b.length - 1);
        quicksort(c, 0, c.length - 1);
        qs_quicksort(d, 0, d.length - 1);

        isSorted(new Integer[][] { aConv, b, c, d });
        System.out.println("All properly sorted");
    }

    public static void isSorted(Integer[][] arrays) {
        if (arrays.length != 4) {
            System.out.println("error sorting, input arr len");
            return;
        }
        for (int i = 0; i < ARR_SIZE; ++i) {
            int val1 = arrays[0][i].compareTo(arrays[1][i]);
            int val2 = arrays[1][i].compareTo(arrays[2][i]);
            int val3 = arrays[2][i].compareTo(arrays[3][i]);
            if (val1 != 0 || val2 != 0 || val3 != 00) {
                System.out.printf("Error [i = %d]: a = %d, b = %d, c = %d", i, arrays[0][i], arrays[1][i], arrays[2][i], arrays[3][i]);
                break;
            }
        }
    }

    public static int partition(int arr[], int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];
        while (i <= j) {
            while (arr[i] < pivot)
                i++;
            while (arr[j] > pivot)
                j--;
            if (i <= j) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

    public static void quickSort(int arr[], int left, int right) {
        int index = partition(arr, left, right);
        if (left < index - 1)
            quickSort(arr, left, index - 1);
        if (index < right)
            quickSort(arr, index, right);
    }

    public static int partition(Integer[] arr, int left, int right) {
        int i = left, j = right;
        Integer pivot = arr[(left + right) / 2];
        while (i <= j) {
            while (arr[i].compareTo(pivot) < 0)
                i++;
            while (arr[j].compareTo(pivot) > 0)
                j--;
            if (i <= j) {
                Integer temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
        return i;
    }

    public static void quickSort(Integer[] arr, int left, int right) {
        int index = partition(arr, left, right);
        if (left < index - 1)
            quickSort(arr, left, index - 1);
        if (index < right)
            quickSort(arr, index, right);
    }

    static int findpivot(Comparable[] A, int i, int j)
    {
        return (i+j)/2;
    }

    static <E> void swap(E[] A, int p1, int p2) {
        E temp = A[p1];
        A[p1] = A[p2];
        A[p2] = temp;
    }


    static void quicksort(Comparable[] A, int i, int j) { // Quicksort
        int pivotindex = findpivot(A, i, j);  // Pick a pivot
        swap(A, pivotindex, j);               // Stick pivot at end
        int k = partition(A, i, j-1, A[j]);
        swap(A, k, j);                        // Put pivot in place
        if ((k-i) > 1) quicksort(A, i, k-1);  // Sort left partition
        if ((j-k) > 1) quicksort(A, k+1, j);  // Sort right partition
    }

    static int partition(Comparable[] A, int left, int right, Comparable pivot) {
        while (left <= right) { // Move bounds inward until they meet
            while (A[left].compareTo(pivot) < 0) left++;
            while ((right >= left) && (A[right].compareTo(pivot) >= 0)) right--;
            if (right > left) swap(A, left, right); // Swap out-of-place values
        }
        return left;            // Return first position in right partition
    }

    static <E> void qs_swap(E[] A, int p1, int p2) {
        E temp = A[p1];
        A[p1] = A[p2];
        A[p2] = temp;
    }

    static void qs_quicksort(Comparable[] A, int i, int j) { // Quicksort
        int pivotindex = (i+j)/2;
        qs_swap(A, pivotindex, j);               // Stick pivot at end
        int k = qs_partition(A, i, j-1, A[j]);
        qs_swap(A, k, j);                        // Put pivot in place
        if ((k-i) > 1) qs_quicksort(A, i, k-1);  // Sort left partition
        if ((j-k) > 1) qs_quicksort(A, k+1, j);  // Sort right partition
    }

    static int qs_partition(Comparable[] A, int left, int right, Comparable pivot) {
        while (left <= right) { // Move bounds inward until they meet
            while (A[left].compareTo(pivot) < 0) left++;
            while ((right >= left) && (A[right].compareTo(pivot) >= 0)) right--;
            if (right > left) { qs_swap(A, left, right); // Swap out-of-place values
            left++; right--;}
        }
        return left;            // Return first position in right partition
    }
}

This produces the output:

56910 nano, qs avg - 'int'
69498 nano, qs avg - 'Integer'
76762 nano, qs avg - 'Comparable' (SO user code)
71846 nano, qs avg - 'Comparable' (SO user code - edit)
All properly sorted

Now, breaking down the results

The 'int' vs 'Integer' shows great diff when simply using primitives vs non-primitives (I'm sure at some points in the code there may be boxing but hopefully not in critical spots ;) - please edit this if so). The 'int' vs 'Integer' uses same code with exception of 'int' 'Integer'. See the following four method signatures that are used in this comparison, 'int'

public static int partition(int arr[], int left, int right)
public static void quickSort(int arr[], int left, int right)

and 'Integer'

public static int partition(Integer[] arr, int left, int right)
public static void quickSort(Integer[] arr, int left, int right)

respectively.

Then there are the method signatures related to the original code you posted,

static int findpivot(Comparable[] A, int i, int j)
static <E> void swap(E[] A, int p1, int p2)
static void quicksort(Comparable[] A, int i, int j)
static int partition(Comparable[] A, int left, int right, Comparable pivot)

and the modified ones,

static <E> void qs_swap(E[] A, int p1, int p2)
static void qs_quicksort(Comparable[] A, int i, int j)
static int qs_partition(Comparable[] A, int left, int right, Comparable pivot)

As you can see, in the modified code, findpivot was removed directly and replaced into the calling spot in quicksort. Also, the partition method gained counters for left and right respectively. left++; right--;

And finally, to ensure these 4 variations of quicksort actually did the sole purpose, sort, I added a method, isSorted() to check the validity of the same generated content and that it's sorted accordingly based on each of the 4 different sorts.

In conclusion, I think my edits may have saved a portion of time/nanoseconds, however I wasn't able to achieve the same time as the Integer test. Hopefully I've not missed anything obvious and edits are welcome if need be. Cheers

score 0 · Answer 2 · answered Oct 28 '16 at 03:42

Well, I couldn't tell from testing whether this makes any difference at all because the timer on my machine is terrible , but I think most of the work in this algo is done with the swap function, so thinking about how to make that in particular more efficient, maybe the function call/return itself consumes cycles, and perhaps the creation of the temp variable each time the function is called also takes cycles, so maybe the code would be more efficient if the swap work was done in line. It was not obvious though when I tested on my machine as the nanotimer returned results +/- 20% each time I ran the program

public class QSort2 {

static int findpivot(Comparable[] A, int i, int j) {
    return (i + j) / 2;
}

 static Comparable temp;

static void quicksort(Comparable[] A, int i, int j) { // Quicksort
    int pivotindex = findpivot(A, i, j);  // Pick a pivot
 // swap(A, pivotindex, j);               // Stick pivot at end
    temp = A[pivotindex];
    A[pivotindex] = A[j];
    A[j] = temp;
    int k = partition(A, i, j - 1, A[j]);
    //swap(A, k, j);                        // Put pivot in place
    temp = A[k];
    A[k] = A[j];
    A[j] = temp;
    if ((k - i) > 1) quicksort(A, i, k - 1);  // Sort left partition
    if ((j - k) > 1) quicksort(A, k + 1, j);  // Sort right partition
}

static int partition(Comparable[] A, int left, int right, Comparable pivot) {
    while (left <= right) { // Move bounds inward until they meet
        while (A[left].compareTo(pivot) < 0) left++;
        while ((right >= left) && (A[right].compareTo(pivot) >= 0)) right--;
        if (right > left) {
            //swap(A, left, right);} // Swap out-of-place values
            temp = A[left];
            A[left] = A[right];
            A[right] = temp;
        }
    }
    return left;            // Return first position in right partition
}

}

How to improve the speed of my class?

2 Answers2