Most effective Algorithm to find maximum of double-precision values

Question

What is the most effective way of finding a maximum value in a set of variables?

I have seen solutions, such as

private double findMax(double... vals) {
double max = Double.NEGATIVE_INFINITY;

for (double d : vals) {
   if (d > max) max = d;
}
    return max;
}

But, what would be the most effective algorithm for doing this?

Answer 1

Assuming the list does not have elements in any particular order, the algorithm you mentioned in your question is optimal. It must look at every element once, thus it takes time directly proportional to the to the size of the list, O(n).

There is no algorithm for finding the maximum that has a lower upper bound than O(n).

Proof: Suppose for a contradiction that there is an algorithm that finds the maximum of a list in less than O(n) time. Then there must be at least one element that it does not examine. If the algorithm selects this element as the maximum, an adversary may choose a value for the element such that it is smaller than one of the examined elements. If the algorithm selects any other element as the maximum, an adversary may choose a value for the element such that it is larger than the other elements. In either case, the algorithm will fail to find the maximum.

Answer 2

EDIT: This was my attempt answer, but please look at the coments where @BenVoigt proposes a better way to optimize the expression

---

• You need to traverse the whole list at least once
• so it'd be a matter of finding a more efficient expression for if (d>max) max=d, if any.

Assuming we need the general case where the list is unsorted (if we keep it sorted we'd just pick the last item as @IgnacioVazquez points in the comments), and researching a little about branch prediction (Why is it faster to process a sorted array than an unsorted array? , see 4th answer) , looks like

 if (d>max) max=d;

can be more efficiently rewritten as

 max=d>max?d:max; 

The reason is, the first statement is normally translated into a branch (though it's totally compiler and language dependent, but at least in C and C++, and even in a VM-based language like Java happens) while the second one is translated into a conditional move.

Modern processors have a big penalty in branches if the prediction goes wrong (the execution pipelines have to be reset), while a conditional move is an atomic operation that doesn't affect the pipelines.

The random nature of the elements in the list (one can be greater or lesser than the current maximum with equal probability) will cause many branch predictions to go wrong.

Please refer to the linked question for a nice discussion of all this, together with benchmarks.

Answer 3

You can't reduce the complexity below O(n) if the list is unsorted... but you can improve the constant factor by a lot. Use SIMD. For example, in SSE you would use the MAXSS instruction to perform 4-ish compare+select operations in a single cycle. Unroll the loop a bit to reduce the cost of loop control logic. And then outside the loop, find the max out of the four values trapped in your SSE register.

This gives a benefit for any size list... also using multithreading makes sense for really large lists.