Какой из следующих 2 теоретически быстрее

Question

Скажем, у вас есть массив двухмерных точек, и вы хотите найти ограничивающую рамку мин / макс.

Что будет быстрее, ручной подход:

float min_x = min_y = highest, max_x = max_y = lowest;
for(auto p: points) {
    max_x = max(max_x, p.x);
    max_y = max(max_y, p.y);
    min_x = min(min_x, p.x);
    min_y = min(min_y, p.y);

}

Или с использованием C ++инструменты:

auto[min_x, max_x] =
        minmax_element(values.begin(), values.end(), [](auto p1, auto p2) { return p1.x < p2.x; });
auto[min_y, max_y] =
        minmax_element(values.begin(), values.end(), [](auto p1, auto p2) { return p1.y < p2.y; });

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

Answer 1

В очень крутом повороте алгоритмической судьбы можно найти минимальный и максимальный элементы массива вместе быстрее, чем каждый из них в отдельности.Один из возможных алгоритмов для этого - объединить элементы друг с другом, сравнить их, а затем переместить более крупные элементы в один отборочный турнир, чтобы найти самый большой элемент, а более мелкие элементы - в другой отборочный турнир, чтобы найти наименьший элемент.Вы можете показать, что при этом будет использовано около 3n / 2 сравнений, в отличие от вычисления max и min каждый независимо, что потребует 2n сравнений.Таким образом, в этом смысле вычисление минимального и максимального значений должно потребовать примерно на 25% меньше сравнений.

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

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

Answer 2

Я бы поставил на первый вариант, предполагая, что четыре оператора вида aN += bN сначала независимы, а во-вторых, они могут быть распараллелены, объединены и автоматически векторизованы.И это, конечно, помогает, когда существует единственный код операции для min / max, как в архитектуре x64 / simd.В этом контексте условный пропуск другого сравнения может быть примером преждевременной оптимизации.Более того, обход массива только один раз должен иметь значение для больших массивов из-за того, что доступ к памяти обычно стоит больше, чем операции ALU.

Answer 3

Всегда использовать функцию из стандартной библиотеки C ++:

1. Поскольку она чрезвычайно хорошо определена и привязана к конкретному компилятору, этот компилятор может распознавать функцию стандартной библиотеки C ++ и выполнятьоптимизаций.Возможно, функция даже жестко запрограммирована в компиляторе?

2. minmax_element была введена, поскольку ее результат можно найти в одном обходе данных.(На самом деле стандарт не позволяет делать два отдельных обхода.)