Title: Performance Algorithms
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

Performance: Algorithms

Algorithms and datastructures are inter-related. Often our choice of algorithms and data structures is driven by the relative performance of the options.

In computer science we often want to know how the execution time of our algorithm scales with the size of the problem. If the size of the problem can be specified by N, then we often talk about the function:

Big O-notation which gets expressed as a function of N

To illustrate, I am going to compare 3 sort routines:
- Collections.sort (standard java sort routine)
- SelectionSort.sort - simple sort routine often demo'ed in cps161
- QuickSort.sort - known to be a good sort routine

For these tests, we will be using the following utility class:

Timer.java

The following program will test out the performance of the above 3 sort routines:

SortPerformance.java


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class SortPerformance {

    Integer nextNum()
    {
        return (int)(Math.random() * 1000);
    }
    void endBuild(List<Integer> list, int n)
    {
        Timer timeIt = new Timer();
        timeIt.start();

        for (int i=0; i < n; i++)
        {
            list.add(nextNum());
        }
        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }
    void sort(List<Integer> list)
    {
        Timer timeIt = new Timer();
        timeIt.start();

        Collections.sort(list);

        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }

    void selectionSort(List<Integer> list)
    {
        Timer timeIt = new Timer();
        timeIt.start();

        SelectionSort.sort(list);

        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }

    void quickSort(List<Integer> list)
    {
        Timer timeIt = new Timer();
        timeIt.start();

        QuickSort.sort(list);

        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }



    public static void main(String[] args) {
        System.out.println("Enter in N");
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();

        SortPerformance sp = new SortPerformance();

        List<Integer> list = new ArrayList<Integer>();


        System.out.println("endBuild");
        sp.endBuild(list, n);

        System.out.println("Collections.sort");
        sp.sort(list);

        System.out.println("QuickSort.sort");
        sp.quickSort(list);

        System.out.println("SelectionSort.sort");
        sp.selectionSort(list);

        keyboard.close();

    }

}



I have a summarized Spreadsheet of all of the numbers that I collected:

AlgorithmPerformance.xls

- Focus on SelectionSort and note that every time we doubled N, the execution time went up by about 4.
- SelectionSort is a good example of an O(N^2) algorithm. Many simple sort algorithms go as O(N^2)
- Note the line under the SelectionSort execution times, I am computing:
N*N/execution_time
- Note that this computation stays reasonably constant for the measurements that I took between 20,000 and 80,000.
- This is what we would expect from SelectionSort if you took a look at the code.

Now take a look at the QuickSort numbers.

- Focus on QuickSort and note that every time we double N, the execution time went up a little more than a factor of 2.
- It turns out that it can be shown that QuickSort execution time increases with N by N * log (N)
- It doesn't really matter which base you use for the log function (2, 10, or E).
- log(N) is a slowly growing function
- Note the line under the QuickSort execution numbers where I am computing:
N * log(N)/execution_time
- Note that this computation stays reasonably constant for the measurements that I took between 20,000 and 80,000.
- Notice that the bigger N gets, the more QuickSort becomes a better choice than SelectionSort

Collections.sort

- I happen to know that QuickSort.sort is a fast sort algorithm, so I am amazed at how much faster Collections.sort is than QuickSort
- Perhaps Collections.sort is running almost native code here.
- Note that Collections.sort is also an O(N * log(N)) algorithm, and it is consistently faster than QuickSort.

I have summarized a few of the other typical O-functions in the table in the spreadsheet

Collections: sort, binSearch and shuffle

We have pointed out the existence of the methods available in the Collections class.

I would like to look at the performance of a few of these important methods: sort, binSearch, and shuffle. All of these require a List based data structure.

Algorithm Performance


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class AlgorithmPerformance {

    Integer nextNum()
    {
        return (int)(Math.random() * 1000);
    }
    void endBuild(List<Integer> list, int n)
    {
        Timer timeIt = new Timer();
        timeIt.start();

        for (int i=0; i < n; i++)
        {
            list.add(nextNum());
        }
        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }
    void sort(List<Integer> list)
    {
        Timer timeIt = new Timer();
        timeIt.start();

        Collections.sort(list);

        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }

    void binSearch(List<Integer> list)
    {
        // Assumes that list is sorted
        Timer timeIt = new Timer();
        timeIt.start();

        int n = list.size();
        for (int i=0; i < n; i++)
        {
            Integer i2 = nextNum();
            Collections.binarySearch(list, i2);
        }
        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }

    void shuffle(List<Integer> list)
    {
        Timer timeIt = new Timer();
        timeIt.start();

        Collections.shuffle(list);

        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }

    public static void main(String[] args) {
        System.out.println("Enter in N");
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();

        AlgorithmPerformance sp = new AlgorithmPerformance();

        List<Integer> list = new ArrayList<Integer>();


        System.out.println("endBuild");
        sp.endBuild(list, n);

        System.out.println("shuffle");
        sp.shuffle(list);

        System.out.println("sort");
        sp.sort(list);

        System.out.println("binsearch");
        sp.binSearch(list);

        keyboard.close();

    }


}



Comments on the data from this test:

- With ArrayList, shuffle, sort seems to run as O(N*log(N)).
- The ArrayList test for BinSearch runs as O(N * log(N). However, we are doing N BinSearch calls. So you could say that each BinSearch call executes as O(log(N)).
- With BinarySearch we can find something from a List of over 16 million with 24 comparisons.
- LinkedList runs similar to ArrayList but a little slower.
- Note that we ran out of memory with N=6 million for LinkedList
- BinarySearch should not be done with a LinkedList ... see the numbers.
- Remember that the method get(int index) performs poorly with a LinkedList

Final Comments on Performance Analysis

There are other factors that can keep you from having perfect performance analysis, such as:

- Too small of a sample
- When heavy memory usage occurs, we can be hit with Garbage collection needing to be done.
- When our memory foot print is large, other factors can enter in such as virtual memory swapping issues.

Last Updated:

July 22, 2014 9:55 PM