Наиболее эффективный алгоритм для поиска максимума значений двойной точности

Question

Какой самый эффективный способ найти максимальное значение в наборе переменных?

Я видел решения, такие как

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

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

Но что будет наиболее эффективным алгоритмом для этого?

Answer 1

Вы не можете уменьшить сложность ниже O(n) если список не отсортирован... но вы можете значительно улучшить постоянный коэффициент. Используйте SIMD. Например, в SSE вы бы использовали MAXSS инструкция для выполнения 4-х операций сравнения + выбора за один цикл. Немного разверните цикл, чтобы снизить стоимость логики управления циклом. А затем вне цикла найдите максимальное значение из четырех значений, захваченных в вашем регистре SSE.

Это дает преимущество для любого размера списка... также использование многопоточности имеет смысл для действительно больших списков.

Answer 2

РЕДАКТИРОВАТЬ: Это была моя попытка ответить, но, пожалуйста, посмотрите на комментарии, где @BenVoigt предлагает лучший способ оптимизировать выражение

---

• Вы должны пройти весь список хотя бы один раз
• так что это было бы вопросом поиска более эффективного выражения для if (d>max) max=dесли есть.

Предполагая, что нам нужен общий случай, когда список не отсортирован (если мы сохраним его отсортированным, мы просто выберем последний элемент как @IgnacioVazquez, указываемый в комментариях), и немного исследуем прогноз ветвления ( почему быстрее обрабатывать отсортированный массив, чем несортированный массив? см. 4-й ответ), выглядит как

 if (d>max) max=d;

может быть более эффективно переписан как

 max=d>max?d:max; 

Причина в том, что первый оператор обычно переводится в ветвь (хотя он полностью зависит от компилятора и языка, но, по крайней мере, в C и C++, и даже в языке на основе VM, как Java, происходит), тогда как второй переводится в условный ход.

Современные процессоры имеют большой штраф в ветвях, если прогноз не оправдывается (конвейеры выполнения должны быть сброшены), в то время как условное перемещение - это атомарная операция, которая не влияет на конвейеры.

Случайный характер элементов в списке (один из которых может быть больше или меньше текущего максимума с равной вероятностью) приведет к тому, что многие предсказания ветвей окажутся неверными.

Пожалуйста, обратитесь к связанному вопросу для хорошего обсуждения всего этого, вместе с оценками.

Answer 3

Предполагая, что в списке нет элементов в каком-либо определенном порядке, алгоритм, который вы упомянули в своем вопросе, является оптимальным. Он должен смотреть на каждый элемент один раз, поэтому требуется время, прямо пропорциональное размеру списка, O(n),

Не существует алгоритма для нахождения максимума, который имеет нижнюю верхнюю границу, чем O(n) ,

Доказательство. Предположим для противоречия, что существует алгоритм, который находит максимум списка менее чем за O(n) время. Тогда должен быть хотя бы один элемент, который он не проверяет. Если алгоритм выбирает этот элемент в качестве максимума, злоумышленник может выбрать значение для элемента таким образом, чтобы оно было меньше, чем один из рассмотренных элементов. Если алгоритм выбирает любой другой элемент в качестве максимума, злоумышленник может выбрать значение для элемента таким образом, чтобы оно было больше, чем другие элементы. В любом случае алгоритм не сможет найти максимум.