How to optimize my current getMax method to retrieve the highest number in an array?

Question

What would be the best way to optimize this code below to make it more efficient while applying the 'best practices'. This is just a simple school project and it works, I've tested it. But I just feel like there's a better and more efficient way to write this method. What do you think?

1. I have an array that is pre-populated with a bunch of numbers. The getMax() method retrieves the highest number in the array. But if the array is empty it returns -1.

2. nElems is simply a variable that keep tracks of how many elements are present in the array.

3. array is the private array declared at the beginning of the class.

   public int getMax() {
   int k = 0;
   int max = array[0];
   
   
   for(int j=0; j<nElems; j++) {
       if(max < array[j])
           max = array[j];
   }
   
   
   if(k == nElems)
       return -1;
   else return max;
   } // end of method
   

Oh and what should I name my k variable to make it more readable? Its purpose is to be 0, so it could be checked against the number of elements in an array to return either -1 or highest number;

Assume all array values are positive.

Answer 1

Take a look at http://www.sorting-algorithms.com/ It has a few sorting algorithms, explanations and animations that give you a good idea of what's going on while sorting. Hope it helps.

Answer 2

You don't need to track the number of elements in the array with nElems, unless you mean that you have a partially-filled array and nElems is the number of slots in it that actually have values. More likely, you should just be using array.length to check the length of the array.

You don't need a variable k to "be 0". The literal 0 is a fine representation of 0. So if you want to return -1 if the array is empty, you can start the method with

if (array.length == 0)
  return -1;

That said, returning -1 for an empty array is kind of strange, since -1 should be a valid result for the method.

Answer 3

Its purpose is to be 0, so it could be checked against the number of elements in an array to return either -1 or highest number;

Zero doesn't need a name - if you mean 0, use the literal 0.

Your loop is fine. There are things you could do to try to optimise it, but they won't necessarily help. Almost always you may as well just leave such localised, "keyhole" optimisation to the JIT. If you just want to try a few things as a learning exercise, then you could experiment as follows:

• rather than using the array twice, set a variable to the array value, then use it twice.
• unroll the loop by different amounts. Be careful not to make the error of accessing the wrong indices if numElem isn't a multiple of the number of times you're unrolling.
• work backwards through the array instead of forwards
• return immediately if you encounter a value of Integer.MAX_VALUE. You aren't going to find anything bigger. It's difficult to define the performance effect of this, since it will speed it up for large arrays with a MAX_VALUE that isn't too near the end, but most likely slow it down for everything else. It might be interesting to see how much difference it makes, though.
• anything else you can think of.

I'm not saying any of these will make a difference, faster or slower, but they could. So run them and time how fast each goes. What you'll most likely learn, is that compared with leaving it to the JIT this stuff isn't worth your time. But you never know ;-)

The surrounding code can be cleaned up, though, to make it more comprehensible rather than to make it faster. For example:

public int getMax() {
    int max = -1;
    if (nElems > 0) {
        max = array[0];
        for(int j=1; j<nElems; j++) {
            if(max < array[j])
                max = array[j];
        }
    }
    return max;
}

This also removes the error in your code, that if the array is size 0, then you access out of bounds in the second line. ColinD's way of doing that is just as good, I'm showing something different for the sake of variety.

Here's the shorter code assuming all values are non-negative:

public int getMax() {
    int max = -1;
    for(int j=0; j<nElems; j++) {
        if(max < array[j])
            max = array[j];
    }
    return max;
}

Answer 4

In theory on a multi-processor (k processors) system, you could speed things up by dividing the list into k sublists. Spawn a process to find the maximum for each sublist and then find the maximum of the maximums.

You may or may not experience a speed up if

1. you have a multi-processor system; and
2. the list is huge.