Calculating the maximum/minimum value off an Array most efficiently in java

Question

I consider two approaches for calculating the maximum/minimum of an Array.

First:

public class Extrema {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    double[] arr = new double[] { -0.11112, -0.07654, -0.03902, 0.0,
            0.03902, 0.07654, 0.11112, 0.14142, 0.1663, 0.18478, 0.19616 };
    double max = Double.NEGATIVE_INFINITY;
    // Find out maximum value
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
}

}

Second approach would be to pre-sort the array and then get arr[0] as minima and the last entry of te array as maxima.

as i know the fastest sorting-algorithms are 0(n log n). The loop from the first approach will take 0(n) time. But with n comparisons and at worst n writing-operations. Since Time-messurement in java is not really trustable there is a need to formalise this question... I would prefer The first method.. am i right? aspecially if i need both extrema and thus need <=n² writeing-operations. At how many method-calls with the same Array pre-sorting makes sence? best regards, Jan

The problem with pre-sorted array is you have to sort it again after insert a new element which will again be a O(N) operation at best — sethi
– sethi, Commented Jun 12, 2013 at 13:09
The Array will never be touched after building.. Thats what i ment by "same Array" — Jan S
– Jan S, Commented Jun 12, 2013 at 13:12
Pre-sorting means getting the min/max is O(1), and that is of course better than O(N), but you're still paying for the sort. I'm not sure what you're asking here. — CPerkins
– CPerkins, Commented Jun 12, 2013 at 13:13
sorry maybe i did some mistake in thinking.. its totaly senceless to call a method several times from the same class.. then the question can be reduced to whats in general better.. presorting or not.. is the loop over the whole array still better than sorting if you want to calculate both maximum and minimum? if you can not calculating both in the same loop.. — Jan S
– Jan S, Commented Jun 12, 2013 at 13:22
If the array is not going to change why do even want to pre sort .. you can calculate the min/max once and keep returning it everytime — sethi
– sethi, Commented Jun 12, 2013 at 13:36

b.buchhold · Accepted Answer · 2013-06-12 13:16:48Z

2

First of all, giving sufficiently large input, time measurement is realible enough.

Second, in your example code, neither comparisons nor write operations matter at all. Most time will be spend accessing the large array (the whole question is only relevant for large arrays, containing many millions of elements) in memory and moving it to the CPUs cache.

Third, if you want both extrema it will be best to get them while going through your array only once. This corresponds to 2*n comparision (nothing to do with n^2) and is still vastly dominated by accessing the array's data in memory.

If you need the max/min of the same array many times, just store it and dont compute it every time. Unless you need a sorted veriant of your array in another place (or you can presort it once and resue that every thime the program is run), there is no point in sorting to get min/max.

answered Jun 12, 2013 at 13:16

b.buchhold

3,9062 gold badges29 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

selig Over a year ago

+1 for note about cache locality. Sorting the array will cause cache lines to be loaded many times. Whereas a simple iteration means each line is only loaded once.

Jan S Over a year ago

Then for very large Arrays the loop over the unsorted array is obviously much better. Thank you

Ivaylo Strandjev · Accepted Answer · 2013-06-12 13:12:31Z

The first approach has computational complexity O(n) and the second has O(n*log(n)) just as you say. Keep in mind though, that assymptotic complexity ignores constant factors so it can easily be the case that a linear algorithm is in fact slower than an n*log(n) one. In your particular case, however you can not go better than the simple iteration and this is in fact the best solution.

Still it may be interesting that there is a linear algorithm to find the k-th element in a sequence that is based on qsort partitioning. This algorithm is built-in in C++'s stl. If interested you may take a look here.

If the array never changes and you have many queries first approach can be at least as fast as the second one - simply cache the values found on the first queries.

abhi · Accepted Answer · 2013-06-13 08:46:16Z

0

Just a thought ..

Whatever searching algorithm you are opting, you can always take advantage of multi threading. Say for example array size = 10 , you can spawn two threads 1. thread-1 would do the searching in first half of the array , 2. Thread-2 would do the searching in 2nd half of the array 3. and then finally you compare results of those two threads to decide on result.

If you are choosing to consider multithreading to speed up the search , you would have to consider couple factors like optimum number of threads ( cause high number of threads would result in most time being spent in context switches ), stack availability etc.

answered Jun 13, 2013 at 8:46

abhi

1611 silver badge10 bronze badges

Collectives™ on Stack Overflow

Calculating the maximum/minimum value off an Array most efficiently in java

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related