Оптимальный способ выбора меньшего или большего оператора перед циклом

Question

У меня есть два массива, содержащие x, y vales для y = f (x). Я хотел бы предоставить функцию, которая найдет значение x, соответствующее либо минимальному, либо максимальному выборочному значению y.

Что представляет собой эффективный способ выбора правильного оператора сравнения перед циклом над значениями в массивах?

Например, я хотел бы сделать что-то вроде следующего:

double FindExtremum(const double* x, const double* y, 
        const unsigned int n, const bool isMin) { 
    static std::less<double> lt; 
    static std::greater<double> gt; 
    std::binary_function<double,double,bool>& IsBeyond = isMin ? lt : gt; 
    double xm(*x), ym(*y); 
    for (unsigned int i=0; i<n; ++i, ++x, ++y) { 
     if (IsBeyond()(*y,ym)) { 
     ym = *y; 
     xm = *x; 
    } 
    } 
} 

К сожалению, базовый класс std::binary_function не определяет виртуального оператора().

Будет ли компилятор, как g ++ 4.8, иметь возможность оптимизировать наиболее прямолинейную реализацию?

double FindExtremum(const double* x, const double* y, 
        const unsigned int n, const bool isMin) { 
    double xm(*x), ym(*y); 
    for (unsigned int i=0; i<n; ++i, ++x, ++y) { 
     if ((isMin && (*y<ym)) || 
      (!isMin && (*y>ym))) { 
     ym = *y; 
     xm = *x; 
    } 
    } 
} 

Есть ли другой способ упорядочить работу, чтобы упростить компилятор для оптимизации? Есть ли известный алгоритм для этого?

Я бы предпочел не использовать шаблонную функцию, если это возможно.

Answer 1

Вам нужно будет передать функтор сравнения в качестве параметра функции шаблона, например.

template <typename Compare> 
double FindExtremum(const double* x, const double* y, 
        const unsigned int n, Compare compare) { 
    double xm(*x), ym(*y); 
    for (unsigned int i=0; i<n; ++i, ++x, ++y) { 
     if (compare(*y,ym)) { 
     ym = *y; 
     xm = *x; 
    } 
    } 
} 

Затем, если вам нужно выбрать во время выполнения, написать что-то вроде этого:

if (isMin) { 
    FindExtremum(x, y, n, std::less<double>()); 
} else { 
    FindExtremum(x, y, n, std::greater<double>()); 
} 

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

Answer 2

Для получения максимальной эффективности сделайте оператора сравнения или оператора сравнения параметром шаблона и не забудьте указать меру.

При стремлении к максимальной микроэффективности виртуальные вызовы не направлены в сторону цели.

Тем не менее, это, скорее всего, случай преждевременной оптимизации, что Дональд Кнут, описанной таким образом:

“ Преждевременная оптимизация является корнем всего зла ”

(я пропустил его оговорки, это звучит более сильным таким образом. :-))

Вместо того, чтобы заниматься безумием микро-оптимизации, которое получает вы мало что, и тратите свое время, я рекомендую более продуктивно пытаться сделать код максимально понятным и доказуемо правильным. Например, используйте std::vector вместо необработанных массивов и отдельно переданных размеров. И, например, не вызывайте логический оператор сравнения compare, как рекомендовано в другом ответе, поскольку это условное имя для трехзначного сравнения (например, как в std::string::compare).

Answer 3

Некоторые вопросы возникают здесь.Во-первых, я думаю, что вы преувеличиваете ситуацию. Например, было бы проще иметь две функции: одну, которая вычисляет min и другую, которая вычисляет max, а затем вызывает любой из них в зависимости от значения isMin.

Более того, обратите внимание, как в каждой итерации вы делаете тест, чтобы увидеть, если isMin верно или нет, (по крайней мере, в «оптимизированной» кода вы показываете в прошлом), и это сравнение могло бы быть сделано только один раз.

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

template<bool isMin> 
class ExtremeFinder 
{ 
static float FindExtreme(const double* x, const double* y, 
        const unsigned int n) 
{ 
    // Version that calculates when isMin is false 
} 
}; 

template<> 
class ExtremeFinder<true> 
static float FindExtreme(const double* x, const double* y, 
        const unsigned int n) 
{ 
    // Version that calculates when isMin is true 
} 
}; 

и называют его ExtremeFinder<test_to_know_isMin>::FindExtreme(...);, или, если вы не можете решить его во время компиляции, то вы всегда можете сделать:

if (isMin_should_be_true) 
    ExtremeFinder<true>::FindExtreme(...); 
else 
    ExtremeFinder<false>::FindExtreme(...); 

Answer 4

Если у вас 2 разобщенных критерии, например, < и >=, вы могли бы использовать bool less аргумент функции и использовать XOR в цикле:

if (less^(a>=b)) 

Не знаю, о производительности, но легко писать.

Или не покрывающих-все-возможности-расчлененные < и >:

if ((a!=b) && (less^(a>b))