Оптимизация логических / реляционных выражений

Question

Оптимизация логических / реляционных выражений

Мне нужно оптимизировать выражение формы:

(a > b) || (a > c)

Я попробовал несколько оптимизированных форм, одна из которых выглядит следующим образом:

(a * 2) > (b + c)

Оптимизация не с точки зрения компилятора. Я хотел бы уменьшить два> до одного.

Это основано на предположении, что 1 <= (а, б, в) <= 26

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

1

c++expression logical-operators relational

Решение

Другие решения

Вероятно, ответ: вы не хотите оптимизировать это. Более того, я сомневаюсь, что есть способ написать это более эффективно. Если вы говорите, что a, b и c являются значениями от 1 до 26, вам не следует использовать целые числа (вам не нужна эта точность), если вы все равно хотите быть оптимальными (по размеру).

Если a> b, выражение a> c не будет выполнено в любом случае. Таким образом, у вас есть не более 2 (и не менее 1) условных операций, которые действительно не стоят оптимизации.

4

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

 a > b || a > c

будет оценивать:

 compare a b
jump not greater
compare a c
jump not greater

где

 a * 2 > b + c

дает:

 shift a left 1 (in temp1)
add b to c (in temp2)
compare temp1 temp2
jump if not greater

Как всегда с производительностью, всегда намного лучше основывать свое решение на фактических измерениях производительности (предпочтительно на выборе архитектуры процессора).

2

Источник

Accepted Answer

Лучшее, что я могу придумать, это

char a, b, c;
std::cin >> a >> b >> c;

if (((b-a) | (c-a)) & 0x80) {
// a > b || a > c
}

С gcc -O2 это генерирует только одну условную ветвь

40072e:       29 c8                   sub    %ecx,%eax
400730:       29 ca                   sub    %ecx,%edx
400732:       09 d0                   or     %edx,%eax
400734:       a8 80                   test   $0x80,%al
400736:       74 17                   je     40074f <main+0x3f>

Это усиливает ограничения входных значений, поскольку значения не могут быть больше 26, а затем вычитаться a от b даст вам отрицательное значение, когда a > b, в два дополнения ты знаешь бит 7 будет установлен в этом случае — то же самое относится к c, После, я ИЛИ ЖЕ оба так, что немного 7 указывает ли a > b || a > cИ наконец мы немного проверяем 7 от А ТАКЖЕ с 0x80 и веткой на этом.

Обновить: Из любопытства я рассчитал 4 различных способа кодирования этого. Для генерации тестовых данных я использовал простой линейный конгруэнтный генератор псевдослучайных чисел. Я рассчитал это в цикле на 100 миллионов итераций. Для простоты я предположил, что если условие истинно, мы хотим добавить 5 к счетчику, иначе ничего не делаем. Я рассчитал это с помощью g++ (GCC) 4.6.3 20120306 (Red Hat 4.6.3-2) на Intel Xeon X5570 @ 2.93GHz с помощью -O2 уровень оптимизации.

Вот код (закомментируйте все, кроме одного из условных вариантов):

#include <iostream>
unsigned myrand() {
static unsigned x = 1;
return (x = x * 1664525 + 1013904223);
}

int main() {
size_t count = 0;
for(size_t i=0; i<100000000; ++i ) {
int a = 1 + myrand() % 26;
int b = 1 + myrand() % 26;
int c = 1 + myrand() % 26;

count += 5 & (((b-a) | (c-a)) >> 31);       // 0.635 sec
//if (((b-a) | (c-a)) & 0x80) count += 5;     // 0.660 sec
//if (a > std::max(b,c)) count += 5;          // 0.677 sec
//if ( a > b || a > c) count += 5;            // 1.164 sec
}
std::cout << count << std::endl;
return 0;
}

Самым быстрым является изменение в предложении в моем ответе, где мы используем расширение знака, чтобы сгенерировать маску, которая либо 32 1s или 32 0s в зависимости от того, является ли условие истинным для ложного, и используйте его для маскировки 5 добавляется так, что он добавляет 5 или 0. У этого варианта нет ветвей. Время указано в комментариях к каждой строке. Самым медленным было оригинальное выражение ( a > b || a > c),

1