2013-06-20 3 views
7

Может ли кто-нибудь помочь мне относительно быстрого метода оценки трех условий в минимальных шагах? У меня есть три условия, и если какой-либо из двух будет правдивым, тогда целое выражение станет true еще false.Какой самый быстрый алгоритм для перестановок трех условий?

Я попробовал два метода:

if ((condition1 && condition2) || 
    (condition1 && condition3) || 
    (condition2 && condition3)) 

Другой способ путем введения переменной i и

i = 0; 
if (condition1) i++; 
if (condition2) i++; 
if (condition3) i++; 
if (i >= 2) 
    //do something 

Я хочу любой другой эффективный метод лучше, чем выше двух.

Я работаю в памяти условиях ограниченности (Atmeta8 с 8 Кбайт флэш-памяти) и необходимо решение, которое работает в С.

+1

Итак, мы уверены, что это C, а не, например. Java, C++, C# или какой-либо другой C-подобный язык, который на самом деле не C? –

+1

@ MichaelKjörling: да, OP прокомментировал ответ PHP. – geoffspear

+0

@Wooble А, я вижу это сейчас. Итак, продолжайте движение. :) –

ответ

4

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

Вы можете ввести эту переменную, которую вы предлагаете, и использовать ее, чтобы уменьшить условия до простого состояния, отличного от того, как только будет известен ответ. Меньше, чем условия тривиально переводят на две команды машинного кода на большинстве архитектур (например, CMP (ср.), А затем JL (прыжок, если меньше) или JNL (скачок, если не меньше) на Intel IA-32). С небольшой удачей компилятор заметит (или вы можете сделать это самостоятельно, но я предпочитаю ясность, которая приходит с одинаковым рисунком повсюду), что trues < 2 будет всегда быть истинным в первых двух операциях if() и оптимизировать его ,

int trues = 0; 
if (trues < 2 && condition1) trues++; 
if (trues < 2 && condition2) trues++; 
if (trues < 2 && condition3) trues++; 
// ... 
if (trues >= 2) 
{ 
    // do something 
} 

Это после того, как ответ известен, уменьшает возможности комплексной оценки conditionN к простой менее чем сравнение, из-за булево короткое замыкание поведения большинства языков.

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

if((int)(condition1) 
    + (int)(condition2) 
    + (int)(condition3) 
    >= 2) 
{ 
    // do something 
} 

Это работает на основе предположения, что лить логическое ЛОЖЬ значения в целом приводит к 0, и литью ИСТИНЫ результаты в 1. Вы можете также использовать условный оператор для того же эффект, хотя следует помнить, что ему может ввести дополнительное разветвление.

if(((condition1) ? 1 : 0) 
    + ((condition2) ? 1 : 0) 
    + ((condition3) ? 1 : 0) 
    >= 2) 
{ 
    // do something 
} 

В зависимости от того, как смарт-optimzer компилятора, оно может быть в состоянии определить, что когда любые два условия оценены для истинного состояния всего всегда будет оценивать истинно, и оптимизировать его основе.

  • Обратите внимание, что , если вы не на самом деле профилированный код и определил, что это преступник, это, вероятно, случай преждевременной оптимизации. Всегда стремиться к тому, чтобы код, который должен был быть прочитан человеческими программистами вначале, и быстрый, чтобы выполнить компьютер вторым, если вы не можете показать окончательное доказательство того, что в частности фрагмент кода, который вы смотрите, является актуальным узким местом производительности. Узнайте, как этот профилировщик работает и положит его в хорошее использование. Имейте в виду, что в большинстве случаев время программиста намного дороже, чем время процессора, а умные методы занимают больше времени, чтобы программист по обслуживанию выполнял синтаксический анализ.
  • Кроме того, составители - действительно умные части программного обеспечения; иногда они на самом деле обнаруживают намерение написанного кода и могут использовать конкретные конструкции, предназначенные для ускорения этих операций, но полагающиеся на то, что они могут определить, что вы пытаетесь сделать. Прекрасным примером этого является замена двух переменных с использованием промежуточной переменной, которая на IA-32 может быть выполнена с использованием XCHG, исключая промежуточную переменную, но компилятор должен иметь возможность определить, что вы на самом деле делаете это, а не something clever which may give another result in some cases.
  • Поскольку подавляющее большинство написанных неявно-отложенных программ тратит большую часть своей жизни в режиме обслуживания (и много написанного программного обеспечения, написанное живым и хорошо прошлогоднее его намерение лучше всего до даты), имеет смысл оптимизируйте для ремонтопригодности, если это не принесет неприемлемых затрат в других отношениях. Конечно, если вы оцениваете эти условия на триллион раз в жесткой петле, целевая оптимизация очень хорошо может иметь смысл. Но профилировщик точно скажет вам, какие части вашего кода нужно тщательно изучать с точки зрения производительности, а это означает, что вы избегаете излишнего усложнения кода.

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

+0

Уважаемый @Michael, что я имел в виду, лучше в исполнении ваш второй подход заслуживает благодарности , но также, как и вы сказали, что код должен быть читаемым человеком, тогда он не должен, потому что мы кодируем машину не для человека, а вместо комментариев предназначенный для понимания кода – shafeeq

+0

Очень сложно оптимизировать * оба * для скорости выполнения * и * использования памяти. Либо одно легко, но и в то же время намного сложнее; обычно один выбирает тот или другой, и оптимизирует для этого за счет другого. Вы уверены, что не можете найти два бита для перепрофилирования? (И переменные действительно хранятся в * flash * памяти? В этом случае: ouch!) –

3

зависит от языка, я мог бы прибегнуть к чему-то вроде:

$cond = array(true, true, false); 

if (count(array_filter($cond)) >= 2) 

или

if (array_reduce($cond, function ($i, $k) { return $i + (int)$k; }) >= 2) 
+0

Мне нужен код для c – shafeeq

+1

@shafeeq Эта информация действительно должна идти прямо в вопрос, но хорошо, что она, по крайней мере, упоминалась где-то. –

9

Это может быть уменьшено до:

if((condition1 && (condition2 || condition3)) || (condition2 && condition3)) 
    //do something 

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

+0

да @wooble лучше, чем у моих двух – shafeeq

+0

* «хотя это, вероятно, будет преждевременной оптимизацией». * - Нет, это не так, поскольку это не стоит никаких усилий и не вносит существенного изменения кода. –

+2

@ChristianRau: Ну, это требует усилий, чтобы выяснить статистическую вероятность каждого условия, которое может быть или не быть тривиальным. – geoffspear

1

Нет абсолютного ответа на этот вопрос. Это сильно зависит от базовой архитектуры. Например. если вы программируете в VHDL или Verilog какую-то аппаратную схему, то наверняка первый даст вам самый быстрый результат. Я предполагаю, что ваша цель - какой-то процессор, но даже здесь очень многое будет зависеть от целевого процессора, инструкции, которую он поддерживает, и в какое время они будут принимать. Кроме того, вы не укажете свой целевой язык (например, ваш первый подход может быть короткозамкнутым, что может сильно повлиять на скорость).

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

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

+0

На самом деле это код для Atmega8, и это во внутреннем loop.so, учитывая коэффициент скорости, первый подход лучше. Это? – shafeeq

0

Вы можете рассмотреть возможность добавления simpy. Если вы используете макросы от стандартного stdbool.h, то true - это 1 и (condition1 + condition2 + condition3) >= 2 - это то, что вы хотите.

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

+0

Обратите внимание, что это в значительной степени точно (за вычетом явного приведения) - один из тех методов, которые я предложил в [моем ответе] (http://stackoverflow.com/a/17216116/486504). –

0

Вы, кажется, готовы оценить все условия, так как вы предложили такое решение самостоятельно в своем вопросе. Если условия являются очень сложными формулами, которые занимают много циклов ЦП для вычисления (например, порядка сотен миллисекунд), то вы можете рассмотреть возможность оценки всех трех условий одновременно с потоками, чтобы получить ускорение. Что-то вроде:

pthread_create(&t1, detached, eval_condition1, &status); 
pthread_create(&t2, detached, eval_condition2, &status); 
pthread_create(&t3, detached, eval_condition3, &status); 
pthread_mutex_lock(&status.lock); 
while (status.trues < 2 && status.falses < 2) { 
    pthread_cond_wait(&status.cond, &status.lock); 
} 
pthread_mutex_unlock(&status.lock); 
if (status.trues > 1) { 
    /* do something */ 
} 

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

0

Попробуйте это:

unsigned char i; 

i = condition1; 
i += condition2; 
i += condition3; 
if (i & (unsigned char)0x02) 
{ 
    /* 
    At least 2 conditions are True 
    0b00 - 0 conditions are true 
    0b01 - 1 conditions are true 
    0b11 - 3 conditions are true 
    0b10 - 2 conditions are true 
    So, Checking 2nd LS bit is good enough. 
    */ 
} 
+0

Как вводить * дополнительную * операцию (побитовое выражение 'и') после того, как все условия были оценены, помогает уменьшить количество условий, которые необходимо оценить? Этот метод вряд ли устранит необходимость сравнения, поэтому добавляет только код. Проблема OP основана на необходимости оценивать все составляющие условия, а не время, необходимое для выяснения того, являются ли по крайней мере два из них истинными. Кроме того, ваш пример работает * только *, если этот бит установлен в счете; что, если есть, скажем, пять условий? 5 (основание 10) = 101 (основание 2); 101 (основание 2) & 2 (основание 16) == 0. Ошибка. –

1

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

Если вы идете:

if ((condition1 && (condition2 || condition3)) || (condition2 && condition3)) 

, то вы, вероятно, есть лучший шанс, вне зависимости от какой-либо дополнительной информации, получения лучшего машинного кода из компилятора. В сборке можно делать такие вещи, как вторая оценка condition2, отнести к первой оценке condition3, чтобы уменьшить размер кода, но нет надежного способа выразить это в C.

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

if ((rare1 || rare2) && (common3 || (rare1 && rare2))) 

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

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

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

Например, если тесты просты, то в сборке вы почти наверняка можете сделать некоторые основные обманки с переносом, чтобы быстро скопировать условия. Портирование обратно на C иногда жизнеспособное.