Java : Testing Array Sum Algorithm Efficiency

Question

I am taking a Java course in university and my notes give me 3 methods for calculating the sum of an ArrayList. First using iteration, second using recursion, and third using array split combine with recursion.

My question is how do I test the efficiency of these algorithms? As it is, I think the number of steps it takes for the algorithm to compute the value is what tells you the efficiency of the algorithm.

My Code for the 3 algorithms:

import java.util.ArrayList;
public class ArraySumTester {

    static int steps = 1;

    public static void main(String[] args) {

        ArrayList<Integer> numList = new ArrayList<Integer>();

        numList.add(1);
        numList.add(2);
        numList.add(3);
        numList.add(4);
        numList.add(5);


        System.out.println("------------------------------------------");
        System.out.println("Recursive array sum = " + ArraySum(numList));

        System.out.println("------------------------------------------");
        steps = 1;
        System.out.println("Iterative array sum = " + iterativeSum(numList));

        System.out.println("------------------------------------------");
        steps = 1;
        System.out.println("Array sum using recursive array split : " + sumArraySplit(numList));

    }

    static int ArraySum(ArrayList<Integer> list) {
        return sumHelper(list, 0);
    }

    static int sumHelper(ArrayList<Integer> list, int start) {
        // System.out.println("Start : " + start);
        System.out.println("Rescursive step : " + steps++);
        if (start >= list.size())
            return 0;
        else
            return list.get(start) + sumHelper(list, start + 1);

    }

    static int iterativeSum(ArrayList<Integer> list) {
        int sum = 0;
        for (Integer item : list) {
            System.out.println("Iterative step : " + steps++);
            sum += item;
        }
        return sum;
    }

    static int sumArraySplit(ArrayList<Integer> list) {

        int start = 0;
        int end = list.size();
        int mid = (start + end) / 2;

        System.out.println("Rescursive step : " + steps++);
        //System.out.println("Start : " + start + ", End : " + end + ", Mid : " + mid);
        //System.out.println(list);

        if (list.size() <= 1)
            return list.get(0);
        else
            return sumArraySplit(new ArrayList<Integer>(list.subList(0, mid)))
                    + sumArraySplit(new ArrayList<Integer>(list.subList(mid,
                            end)));

    }
}

Output:

------------------------------------------
Rescursive step : 1
Rescursive step : 2
Rescursive step : 3
Rescursive step : 4
Rescursive step : 5
Rescursive step : 6
Recursive array sum = 15
------------------------------------------
Iterative step : 1
Iterative step : 2
Iterative step : 3
Iterative step : 4
Iterative step : 5
Iterative array sum = 15
------------------------------------------
Rescursive step : 1
Rescursive step : 2
Rescursive step : 3
Rescursive step : 4
Rescursive step : 5
Rescursive step : 6
Rescursive step : 7
Rescursive step : 8
Rescursive step : 9
Array sum using recursive array split : 15

Now from the above output the recursive array split algorithm takes the most steps, however according to my notes, it is as efficient as the iterative algorithm. So which is incorrect my code or my notes?

Answer 1

Using System.currentTimeMillis() is the way to go. Define a start variable before your code and an end variable after it completes. The difference of these will be the time elapsed for your program to execute. The shortest time will be the most efficient.

long start = System.currentTimeMillis();

// Program to test

long end = System.currentTimeMillis(); long diff = end - start;

Answer 2

Do you just want to look at speed of execution? If so, you'll want to look at microbenchmarking: How do I write a correct micro-benchmark in Java?

Essentially because of how the JVM and modern processors work, you won't get consistent results by running something a million times in a FOR loop and measuring the execution speed with a system timer (EDIT).

That said, "efficiency" can also mean other things like memory consumption. For instance, any recursive method runs a risk of a stack overflow, the issue this site is named after :) Try giving that ArrayList tens of thousands of elements and see what happens.

Answer 3

I suggest that you look at the running time and space complexity (these are more computer sciencey names for efficiency) of these algorithms in the abstract. This is what the so-called Big-Oh notation is for.

To be exact, of course, after making the implementations as tight and side-effect-free as possible, you should consider writing microbenchmarks.

Since you have to be able to read the value of every element of the list in order to sum these elements up, no algorithm is going to perform better than a (linear) O(n) time, O(1) space algorithm (which is what your iterative algorithm does) in the general case (i.e. without any other assumptions). Here n is the size of the input (i.e. the number of elements in the list). Such an algorithm is said to have a linear time and constant space complexity meaning its running time increases as the size of the list increases, but it does not need any additional memory; in fact it needs some constant memory to do its job.

The other two recursive algorithms, can, at best, perform as well as this simple algorithm because the iterative algorithm does not have any complications (additional memory on the stack, for instance) that recursive algorithms suffer with.

This gets reflected into what are called the constant terms of the algorithms that have the same O(f(n)) running time. For instance, if you somehow found an algorithm which examines roughly half the elements of a list to solve a problem, whereas another algorithm must see all the elements, then, the first algorithm has better constant terms than the second and is expected to beat it in practice, although both these algorithms have a time complexity of O(n).

Now, it is quite possible to parallelize the solution to this problem by splitting the giant list into smaller lists (you can achieve the effect via indexes into a single list) and then use a parallel summing operation which may beat other algorithms if the list is sufficiently long. This is because each non-overlapping interval can be summed up in parallel (at the same time) and you'd sum the partial sums up in the end. But this is not a possibility we are considering in the current context.

Answer 4

I would say to use the Guava Google Core Libraries For Java Stopwatch. Example:

Stopwatch stopwatch = Stopwatch.createStarted();
// TODO: Your tests here
long elapsedTime = stopwatch.stop().elapsed(TimeUnit.MILLISECONDS);

You get the elapsed in whatever unit you need and plus you don't need any extra calculations.

Answer 5

If you want to consider efficiency then you really need to look at algorithm structure rather than timing.

Load the sources for the methods you are using, dive into the structure and look for looping - that will give you the correct measure of efficiency.