Полезно ли в C# применить теорему Деморгана для вручную оптимизировать логические выражения в условных утверждениях (например, если условия)
https://stackoverflow.com/questions/981830
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
В тот день, когда я выполнял большую часть своей работы в C и C ++ Теорема Деморгана оптимизировать любые нетривиальные логические выражения.
Полезно ли это сделать в C# или оптимизатор делает это ненужным?
Решение
На процессорах это быстро, практически невозможно переставить логические выражения, чтобы изменить какую -либо разницу в скорости. И компилятор C# очень умный, он также оптимизирует его. Оптимизируйте для читаемости и ясности!
Другие советы
Ваша первая цель должна состоять в том, чтобы оптимизировать такие заявления для понимания разработчиков и простоты обслуживания.
Теорема Деморгана может быть полезным инструментом для этого.
Оптимизация в JIT, в его текущей форме, не (из того, что я прочитал) оптимизирует это для вас. Если вам нужно оптимизировать его, вам все равно нужно принять это во внимание.
При этом, это довольно маленькая микрооптимизация. В общем, я бы предпочел написать ваши «нетривиальные логические выражения» в более выразительной форме, чтобы их легче понять. Для меня это более ценно, чем любая очень небольшая оптимизация, которую вы получите от применения теоремы Деморгана.
Я считаю, что правильный ответ на этот вопрос заключается в том, что компилятор (обычно не оптимизирует логические оценки, просто из -за логического короткого замыкания, например:
if (GetFlagA() || GetFlagB())
{
...do something
}
Порядок этого, если оценка может действительно иметь значение, если вызов getflaga изменяет то, на что полагается GetFlagb (если это действительно плохая кодовая практика, но это другая тема для другого потока.) Проблема здесь - логичная короткая цирку Возвращение правда, GetFlagb никогда не будет работать, как видно, что результат GetFlagB несущественен для оценки заявления.
А | B | знак равно
F | F | Фланг
F | T | Т
T | F | T TRUE, независимо от возвращения B Val.
T | T | T TRUE, независимо от возвращения B Val.
Таким образом, спрашивая, можете ли вы оптимизировать, используя DeMorgan's или что -то, что действительно похоже на остальные компьютерные науки и разработка программного обеспечения. "Это зависит." Если вы используете нефункциональную оценку, она, вероятно, может быть оптимизирована. Честно говоря, вы говорите о нескольких операциях на безумно быстрой платформе, вам было бы лучше потратить время на написание документации.
Надеюсь, это поможет.
Единственный раз, когда вы должны выполнять перестройку, логическая алгебра или Деморган, - это когда логика слишком сложна, чтобы сделать это по -другому. Если это не слишком сложно, продолжайте читаемым. Есть случай для упрощения логики.
Иногда, когда логика сложно, мне нужно создать Карно карта Чтобы упростить логику до чего -то, что я даже могу записать. Часто использование K-карт может помочь вам придумать более лаконичные способы выражения вашей логики. Результат может иметь смысл или не иметь смысла, но он будет эквивалентен.
И я также сказал бы, что сам Демоорган действительно не оптимизация, которая изменит ситуацию, если более половины терминов негативны (не), вы в лучшем случае получите производительность удаления некоторых, а не единственное Инструкция для процессора за нет. В худшем случае, вы можете добавить столько нефтеразиторов, сколько вы забираете, и если вам не нужно использовать DeMorgan's, вы получите больше нефте, чем в первую очередь.
Если вы собираетесь оптимизировать логику, используйте логическую алгебру или мою личную любимую K-карты Чтобы уменьшить количество терминов (если возможно). Не просто перемещайте логических операторов, это глупо.
Я думаю, компилятор уже сделает это. Вы можете сделать тест и посмотреть на скомпилированный IL через отражатель.
Оптимизируйте для читаемости и обслуживаемости. Спросите себя, поймете ли вы свою умную оптимизацию через год, и если вы думаете, код может использовать некоторые комментарии, сделать код самостоятельным документом.
Поскольку в оценке логических выражений используется семантика ярлыка, вы можете перемещать подэкспрессии, которые дешевле рассчитывать на фронт:
if (CountAllFilesOnDrive('C:\') > 7 && useFileScan) { ... }
Будет запускать дорогой звонок в любое время, когда выражение оценивается, даже если оно не нужно. Разверкание этого оператора пропускает проверку файла, если useFileScan ложь:
if (useFileScan && CountAllFilesOnDrive('C:\') > 7) { ... }
Деморган может помочь вам перейти на «ранние выходы» на фронт и, таким образом, получить лучшую среднюю производительность.
Обратите внимание, что из-за гарантии оценки слева направо, оптимизатор не имеет большой свободы для изменения выражения.
Примите во внимание читаемость и обслуживание. Если у вас есть довольно сложный набор логических выражений, которые трудно прочитать, теормор Деморгана может быть отличным подходом к снижению выражения до чего -то проще для чтения/поддержания, но все еще действителен/согласуется с исходной экспрессией.
Если, с другой стороны, более словесное выражение намного проще читать и уменьшить выражение, хотя и логически равноправное, затрудняет понимание, оставьте его как есть.
Почти во всех практических случаях, о которых я могу придумать, расположение логических операторов не оказывает заметного влияния на общую производительность. Если ваша программа ждет базы данных, сеть и т. Д. Она будет тратить там гораздо больше времени, чем в этих крошечных операциях. Если вы напишите программу, где она действительно имеет значение, лучше пропустить C# и использовать C ++.
Деморган сам по себе может быть совершенно неактуальным в присутствии оценки короткого замыкания.
return !(exp1 || exp2);
return !exp1 && !exp2;
Скомпилировать
if( exp1 ) return !(true); else return !(exp2);
if(!(!exp1)) return false; else return !(exp2);
с notS отменена и складывается константы, они идентичны.
Более важным случаем является порядок оценки; Положите Cheep Things, которые, вероятно, запускают короткие замыкания в передней части выражений. Компилятор не может оптимизировать это для вас, потому что ему трудно обнаружить семантические проблемы, такие как побочные эффекты, или если более позднее выражение делает предположения на основе более ранних:
return validState() && checkAssumuingValidState();
Я согласен с общими утверждениями, что читаемость и обслуживание наиболее важны, когда речь идет о оптимизации логических выражений в наши дни. Следовательно, теорема Деморгана, как правило, очень полезна.
Есть одно исключение из этого правила. Если логическое выражение меняет выражение теорема Деморгана, оно может быть сложнее поддерживать. Рассмотрим выражение с несколькими входами, которые были оптимизированы, чтобы показать лишь несколько булевых условий. Одно изменение в требуемой логической логике может заставить кого -то снова перечислить все возможные логические комбинации, а затем повторно оптимизируйте. Если бы выражение было оставлено в неоптимизированном формате, изменение потребовало бы меньше шагов для завершения.
Более того с анекдотической точки зрения, мне интересно, будет ли обучение команды о теореме Деморгана и картах Карно и т. Д. Возможно, если у кого -то хорошее понимание этих методов, он/она склоняется к лучшему выражению. Например, я недавно наткнулся на это логическое выражение в коде программного обеспечения, которое я поддерживаю:
if ({boolean variable} != true && false)
Оптимизатор C# не может сделать слишком много, учитывая правила короткого замыкания для оценки логического выражения. Таким образом, применение закона Деморгана не будет многое, если он не позволит вам увидеть другие полезные рефакторинг (и, конечно, это может помочь сделать ваш код более ясным).
Но есть случаи, когда вы можете добиться значительных улучшений производительности с Другой Виды оптимизации выражения. Например, эти условия должны быть заменены
if ( costly_boolean_function() && cheap_often_false_boolean_function() )
Оптимизаторы запросов SQL делают это, конечно, так как SQL не имеет короткого замыкания. Оптимизатор запроса будет агрессивно перестраивать конъюнктивные, где предикается предварительное условие (формы c1 AND c2 AND ... cn) в первую очередь поставить наименее дорогие условия, поскольку они могут оценить ложь и избежать необходимости оценить более дорогие.
Сначала дело с обслуживанием и Оптимизация высокого уровня.
Затем справиться с оптимизацией низкого уровня.
Закон де Моргана полезен для его снижения до нормальной формы, например, дизъюнктивной нормальной формы (DNF) или конъюнктивной нормальной формы (CNF). В основном это означает, что это либо
DNF: (A и B и C) или (E и F и G) ...
или же
CNF: (A или B или C) и (E или F или G) ....
Вы можете бросить не на самом низком уровне.
Я согласен с предыдущими плакатами, которые вы должны оптимизировать для читаемости и понимания.
Для всех нас, не-CS-специалистов:
Википедия по законам де Моргана:
Законы де Моргана являются правилами, связанными с логическими операторами «и" и "или" с точки зрения друг друга через отрицание, а именно:
Не (p или q) = (не p) и (не q)
Не (p и q) = (не p) или (не q)
