Каков наиболее эффективный способ найти максимальное значение в наборе переменных?
Я видел решения, такие как
private double findMax(double... vals) {
double max = Double.NEGATIVE_INFINITY;
for (double d : vals) {
if (d > max) max = d;
}
return max;
}
Но каков будет наиболее эффективный алгоритм для этого?
Вы не можете уменьшить сложность ниже O(n), если список не отсортирован... но вы можете значительно улучшить постоянный фактор. Используйте СИМД. Например, в SSE вы должны использовать инструкцию MAXSS для выполнения 4 операций сравнения+выбора за один цикл. Немного разверните цикл, чтобы уменьшить стоимость логики управления циклом. А затем вне цикла найдите максимальное из четырех значений, захваченных в вашем регистре SSE.
Это дает преимущество для списка любого размера... также использование многопоточности имеет смысл для действительно больших списков.
Предполагая, что в списке нет элементов в каком-либо определенном порядке, алгоритм, который вы упомянули в своем вопросе, является оптимальным. Он должен просмотреть каждый элемент один раз, поэтому это занимает время, прямо пропорциональное размеру списка, O(n).
Не существует алгоритма нахождения максимума, который имеет более низкую верхнюю границу, чем O(n).
Доказательство: предположим, что существует алгоритм, который находит максимум списка менее чем за O(n) времени. Тогда должен быть хотя бы один элемент, который он не проверяет. Если алгоритм выбирает этот элемент как максимальный, злоумышленник может выбрать такое значение для элемента, которое меньше, чем один из проверяемых элементов. Если алгоритм выбирает какой-либо другой элемент в качестве максимального, злоумышленник может выбрать значение для элемента так, чтобы оно было больше, чем другие элементы. В любом случае алгоритм не сможет найти максимум.
РЕДАКТИРОВАТЬ: это был мой ответ на попытку, но, пожалуйста, посмотрите комментарии, в которых @BenVoigt предлагает лучший способ оптимизировать выражение.
if (d>max) max=d, если таковое имеется.Предполагая, что нам нужен общий случай, где список не отсортирован (если мы оставим его отсортированным, мы просто выберем последний элемент, как указывает @IgnacioVazquez в комментариях), и немного изучим ветвь предсказание (Почему это быстрее обрабатывать отсортированный массив, чем несортированный массив?, см. 4-й ответ), выглядит так
if (d>max) max=d;
можно более эффективно переписать как
max=d>max?d:max;
Причина в том, что первый оператор обычно преобразуется в ветвь (хотя это полностью зависит от компилятора и языка, но, по крайней мере, в C и C++, и даже в языке на основе VM, таком как Java происходит), а второй преобразуется в условный ход.
Современные процессоры имеют большой штраф в ответвлениях, если предсказание идет не так (конвейеры выполнения должны быть сброшены), в то время как условное перемещение — это атомарная операция, которая не влияет на конвейеры.
Случайный характер элементов в списке (один из них может быть больше или меньше текущего максимума с равной вероятностью) приведет к тому, что многие предсказания ветвления будут ошибочными.
Пожалуйста, обратитесь к связанному вопросу для хорошего обсуждения всего этого вместе с тестами.
i равна 1 / (1 + i). То же, что и вероятность того, что максимум подсписка (0, i) находится в последнем слоте. Получается мало, довольно быстро (хотя и недостаточно быстро, чтобы сойтись).
- person Ben Voigt; 07.12.2014
greater = -(d > max); max = d&greater | max&~greater; Удобно, это очень хорошо работает с SIMD... в конце цикла ваш регистр SIMD содержит максимальные значения каждого столбца, а затем вам нужно начать пролистывать и объединение столбцов. Но, вероятно, лучшим подходом будет использование арифметики с насыщением: max += saturate(d - max);
- person Ben Voigt; 07.12.2014
if (d>max) max=d- person rupps schedule 07.12.2014#pragma omp parallel for reduction(max : max)перед цикломfor. Здесь второй максимум относится кdouble max. Он автоматически пересекает трубы. - person Thomas schedule 07.12.2014