CS 231: Lab #4

Title image Spring 2020

Sorting and Runtime

The goal of this lab period is to explore how to analyze the performance of our own code.


Timing Code

Timing code accurately is extremely challenging. Read through some of the challenges before continuing with the lab exercises.

Tasks

  1. Power Versus Squaring

    For the first test, we want to compare the following two methods of squaring two numbers.

    a = x * x;          // method 1, simple multiplication
    a = Math.pow(x, 2); // method 2, using the built-in pow function

    Because both operations are very fast, we will have to execute them many times to get an accurate measurement. Therefore, we also have to account for the infrastructure code.

    Create a class Timing. Then implement the following methods.

    • public static double just_adding(int N) - using nanoTime, use a loop to calculate the sum of the numbers 0 to N-1. Do all of the calculations as doubles. The interior of the loop will need to convert the loop variable (which should be an integer) to a double, then add the double value to the summation variable. Declare all of your variables, including your loop variable, at the start of the method. The function should return the time taken expressed in milliseconds (ms). To convert the result of nanoTime to ms, divide by one million (1000000.0).
    • public static double square_mult(int N) - Make this function identical to just_adding, but sum the squares of the values from 0 to N-1 using regular multiplication to generate the squares.
    • public static double square_pow(int N) - Make this function identical to just_adding, but sum the squares of the values from 0 to N-1 using the Math.pow() function to generate the squares.
    • public static double robust_avg(ArrayList<Double> data) - this function should compute a robust average of the values in data. It should not time anything.

      The function should sort the data array (use Collections.sort()) and then compute the average of the values in the ArrayList except the lowest and highest. Making this function static makes it easier to use in other classes, and it doesn't use any object fields.

    Write a main function that calls each function three times with values of 1000, 10000, and 100000 for N. Print out the timing results and make sure the times increase linearly with N (roughly a factor of 10). Use the -Xint flag when running your code

    java -Xint Timing

    Compare the two methods. Add a new function to your timing class.

    • public static void square_test(int N) - for each of the timing functions--just_adding, square_mult, and square_pow--execute the function at least five times and store the results in an ArrayList. Use your robust_avg function to compute the time estimate. Print the add result, the multiplication result, and the power result. Then print the ratio: pow_result / mult_result. Finally, print the ratio: (pow_result - add_result) / (mult_result - add_result).

    Edit your main function so it calls square_test function multiple times with values like 100, 1000, 10000, and 100000. Remember to use the -Xint flag.

    Is there a difference in performance if you do not use the -Xint flag?

    Do the results change much if you run your program for even larger N?

    Include the results of your analysis in your report.

  2. Insert Sort

    For the second test, create a new class Sorter. Then write a method that implements insert sort for an array of type long. Your implementation should sort the array in place without allocating a new array.

    • public static void insert_sort( long[] data ) - sorts the values in data in ascending order using insert sort. After executing the function, the values in data should be in sorted order.

    The idea for insert sort is as follows.

    Given: an array of integers
    
    Initial situation: assume the first element in the array is a sorted list
    
    for i from the second element to the end
       let j be i
       while j is greater than 0 and element j-1 is greater than element j
           swap the element j-1 and the element j
           decrement j

    Note, it is possible to implement the above as two for loops.

    Write a main function for the Sorter class that does the following.

    1. Create an array of size N, where N is given by a command line parameter.
    2. Initializes the array to random values between 0 and 2N
    3. Times how long it takes to call insert_sort using nanoTime.
    4. Prints out the time taken in milliseconds.
  3. Run your program for the following N: 1000, 5000, 10000, 50000, 100000, and 500000. Remember to use the -Xint flag.

    Use Google Sheets, Numbers, or Excel to create a simple plot of your data (or write a quick python program and use matplotlib). How do the times change with increasing N?

    Try running your program without the -Xint flag and plot the values. Is there a difference?

    Modify your program so it initializes the array with ascending values (e.g. assign the loop variable to each array entry). Run your program again and plot the values. Did anything change? Is this worst case or best case?

    Modify your program so it initializes the array with descending values (e.g. assign (N - the loop variable) to each entry in the array). Run your program again and plot the values. How does it compare to the prior two cases? Is this worst case or best case?

    Include the results of your analysis on insert sort in your report.


When you are done with the lab, go ahead and get started on the current project.