CODEWITHSUNDEEP
java
Kayla0x41
Kayla0x41

Reputation: 105

Java Compute Average Execution Time

I want to compute the average execution time of x number of runs (i.e. 10)... I can easily execute 10 times using the loop in the main method, but how can I store the execution times & compute the average? I'm thinking this is something really simple, but I'm drawing a blank at the moment... Thanks in advanced!

import java.util.Arrays;
import java.util.Random;

public class OptQSort1 {

static boolean insertionSortCalled = false;
private static final Random random = new Random();
private static final int RANDOM_INT_RANGE = 9999;

private static int[] randomArray(int size) {

    // Randomize data (array)
    final int[] arr = new int[size];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = random.nextInt(RANDOM_INT_RANGE);
    }
    return arr;
}

// Sort
private static void sort(int[] arr) {
    if (arr.length > 0)
        sortInPlace(arr, 0, arr.length - 1);
}

private static void sortInPlace(int[] arr, int left, int right) {



    // OptQSort1:
    int size = right - left + 1;
    if (size < 10 && !insertionSortCalled) {
        insertionSortCalled = true;
        insertionSort(arr, 0, arr.length - 1);
    }

    if (left >= right)
        return; // sorted

    final int range = right - left + 1;
    int pivot = random.nextInt(range) + left;

    int newPivot = partition(arr, left, right, pivot);

    sortInPlace(arr, left, newPivot - 1);
    sortInPlace(arr, newPivot + 1, right);

}

private static int partition(int[] arr, int left, int right, int pivot) {

    int pivotVal = arr[pivot];
    swapArrayVals(arr, pivot, right);

    int storeIndex = left;
    for (int i = left; i <= (right - 1); i++) {
        if (arr[i] < pivotVal) {
            swapArrayVals(arr, i, storeIndex);
            storeIndex++;
        }
    }

    swapArrayVals(arr, storeIndex, right);

    return storeIndex;
}

private static void swapArrayVals(int[] arr, int from, int to) {
    int fromVal = arr[from];
    int toVal = arr[to];
    arr[from] = toVal;
    arr[to] = fromVal;
}

public static void insertionSort(int[] arr, int left, int right) {
    int in, out;

    for (out = left + 1; out <= right; out++) {
        int temp = arr[out];
        in = out;

        while (in > left && arr[in - 1] >= temp) {
            arr[in] = arr[in - 1];
            --in;
        }
        arr[in] = temp;
    }

}

public static void main(String[] args) {

    long StartTime = System.nanoTime();

    int runCount = 0;

    // Array size
    int[] arr = randomArray(1000);
    int[] copy = Arrays.copyOf(arr, arr.length);

    // Print original data (array)
    System.out.println("The starting/unsorted array: \n"
            + Arrays.toString(arr));

    sort(arr);

    do {
    // check the result
    Arrays.sort(copy);
    if (Arrays.equals(arr, copy)) {
        System.out.println("The ending/sorted array: \n"
                + Arrays.toString(arr));


        // print time
        long TotalTime = System.nanoTime() - StartTime;
        System.out.println("Total elapsed time (milliseconds) " + "is: "
                + TotalTime + "\n");

        runCount++;
    } 
    }   while (runCount < 10);
}

}

Upvotes: 0

Views: 10461

Answers (5)

Jon Egeland
Jon Egeland

Reputation: 12623

before the execution:

long start = System.currentTimeMillis();

after the execution:

long end = System.currentTimeMillis();

add each time in an ArrayList like this:

times.add(end-start);

get the average time:

Long total = 0;
for(Long l : times)
    total += l;

System.out.println("Average Time: "+(total/times.size()));

Be careful the unit of time of the return value is a millisecond.

Upvotes: 1

Cameron Skinner
Cameron Skinner

Reputation: 54376

You can compute the average by just measuring the total time for 10 iterations of your code, then divide that by 10.

e.g:

public static void main(String[] args) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < 10; ++i) {
        doSort();
    }
    long elapsed = System.currentTimeMillis() - start;
    long average = elapsed / 10;
}

As a helpful tip, use a named constant rather than a literal value for the number of iterations:

private final static int ITERATIONS = 10;
public static void main(String[] args) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < ITERATIONS; ++i) {
        doSort();
    }
    long elapsed = System.currentTimeMillis() - start;
    long average = elapsed / ITERATIONS;
}

This means you only have to change the number in one place if you want to run, say, 50 or 100 iterations.

You should also be aware that it is very difficult to get accurate timing results from this kind of experiment. It's a good idea to include a "warm-up" phase to allow the JIT to evaluate and optimize the code, and to have a much larger number of iterations:

private static final int WARMUP_ITERATIONS = 10000;
private static final int RUN_ITERATIONS = 100000;
public static void main(String[] args) {
    // Warmup with no timing
    for (int i = 0; i < WARMUP_ITERATIONS; ++i) {
        doSort();
    }

    // Now the real test
    long start = System.currentTimeMillis();
    for (int i = 0; i < RUN_ITERATIONS; ++i) {
        doSort();
    }
    long elapsed = System.currentTimeMillis() - start;
    long average = elapsed / RUN_ITERATIONS;
}

Upvotes: 4

Peter Lawrey
Peter Lawrey

Reputation: 533660

To calculate the average time, you need the sum of the times. The sum of the times is the total time, so you don't even need to know the individual times or record them. Just take the end-to-end time and divide by the count.

int count = ...
long start = System.nanoTime();
for(int i=0;i<count;i++) {
    // do something
}
long time = System.nanoTime() - start;
long averageTime = time/count;

The JIT doesn't fully warmup until you have done at least 10,000 iterations, so you might ignore the first 11,000 if this is practical.

A simple way to do this is

int count = ...
long start = 0;
for(int i=-11000;i<count;i++) {
    if(i == 0) start = System.nanoTime();

    // do something
}
long time = System.nanoTime() - start;
long averageTime = time/count;

BTW: Only include in the test time the things you want to time. Generating random numbers , for example, could take longer than the sort itself which could give misleading results.

EDIT: The compile threshold which determines when a method or loop is compiled is controlled with -XX:CompileThresholed= which defaults to 10000 on the server JVM and 1500 on the client JVM. http://www.oracle.com/technetwork/java/javase/tech/vmoptions-jsp-140102.html

-XX:CompileThreshold=10000 Number of method invocations/branches before 
                           compiling [-client: 1,500]

Upvotes: 4

dbf
dbf

Reputation: 6499

You can use a list of integers to store the result for each run, but you don't need it to calculate average, just divide totaltime by number of runs. Btw, your measurements are not very good: 1) Generation of random arrays is included there 2) 10 runs is not enought

Upvotes: 1

Ted Hopp
Ted Hopp

Reputation: 234847

Just keep a second long value that is a running total of the Totaltime values. When the loop exits, just divide by runCount.

Alternatively, create an ArrayList<Long> to store the times. Each time you do one run, add Totaltime to the array. After the loop exits, you can average the values and also compute other statistics (min/max, standard deviation, etc.).

Upvotes: 0

Related Questions