03 февраля 2006

Булева логика на службе программиста 2

Теперь пример поинтереснее. Буду объяснять подробно.

Допустим, имеем такой код (РНР):

<?
if($enabled)
{
if($has_property)
do_it();
}
else
do_it();
?>

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

Что можно сделать? Допустим, переменная $enabled есть предикат А, а переменная $has_property есть предикат В (Что такое предикат? Это утверждение, которое либо ложно, либо истинно, например, "жена беременна"). Теперь нарисуем карту Карно, помним такую?

A
¦-----¦-----¦
¦ ¦ ¦
¦-----¦-----¦
¦ ¦ ¦B
¦-----¦-----¦

Здесь 4 ячейки - максимальное количество состояний, которое может быть в нашем случае, т.к. каждый предикат может быть в одном из 2 состояний (4 = количество состояний в степени количества переменных = 2 в квадрате). Теперь перебираем состояния нашего условия, и если оно истинно (т.е. если запустится функция "do_it()" ), ставим в соответствующую ячейку единичку, иначе нолик.

Итак, ячейка 1 (первый столбец, первая строка). В ней А истинно (А стоит прямо над ней), а В - нет (В стоит во второй строке). Что же даёт наша задача, если А=$enabled=да и И=$has_property=нет? Ничего: программа успешно пройдет первую строку [if($enabled)], и пропустит вторую [if($has_property)]. Значит, ставим в первую ячейку нашей таблицы 0.

Ячейка 2 (второй столбец первой строки). Здесь А=нет и В=нет. Как видно по программе, если А=нет, то запускается else, и do_it() выполнится, значит, ставим единичку.

Ячейка 3 (первый столбец, вторая строка). А=да, В=да. В итоге будет единица, так как программа пройдёт оба if и запустит do_it().

Ячейка 4 (второй стоблец, вторая строка). Здесь опять А=нет, а В=да.Как снова видно по программе, если А=нет, то запускается else, значит,ещё одна единичка.

В итоге получаем такую картину:
   A
¦-----¦-----¦
¦ 0 ¦ 1 ¦
¦-----¦-----¦
¦ 1 ¦ 1 ¦B
¦-----¦-----¦

Вот теперь начинается оптимизация. Это называется склеивание: мы в уме группируем в команду по две сначала обе нижние единицы, потом две правые. Таким образом, получаем две группы единиц, между которыми нужно поставить знак плюс (дизъюнкция, она же OR, она же ¦¦ ) - таковы правила (не было бы единицы в позиции {2,2} - нечего бы было группировать). То есть первая группа единиц - это две единички во второй строке: они обе сработают, когда В=да (потому что стоят в строке, где В=да). Вторая группа единиц стоит во втором столбце, там А=нет. Получается, что первая группа = В, вторая = !А (А=нет, "не А"или "А есть ложь").

Таким образом, наше выражение записывается так: (!А OR В).

Делая обратную расшифровку, получаем:

<?
if(!$enabled ¦¦ $has_property)
do_it();
?>

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

Желаю удачи в разборе полётов 3 переменных!

5 комментов:

Ник комментирует...

Получается изящно, действительно!

До сих пор применение сего в моих кодах ограничивалось использованием закона де Моргана:

!(А или|и В) = !(А) и|или !(В).

Помогало, когда в цикле двойное условие с операторами !=, а пишешь его изначально всегда неправильно. Например, чтение файла:

while (str!="" && feof(f)!=true)
{
str = readline(f);
}

Я ведь как думаю (не факт, правда, что и остальные так думают): пока не встречу пустую строку или не встречу конец файла, буду что-то там делать. И пишу автоматом:

while (str!="" || feof(f)!=true)
{...}

а потом не могу понять, что за борбаг такой.

А надо было рассуждать так: я выйду из цикла когда

(str=="" || feof(f)==true)

Теперь применяем отрицание ко всему выражению (ведь нам надо остаться в цикле, а не выйти) и получаем

(str!="" && feof(f)!=true)

Всё. Простите за занудство.

Dmitry Kalabin комментирует...

A стоит над первым столбцом, В стоит во второй строке - мдам... логика уже пошла курить лесом. :( Дальше можно не продолжать... ;)
............
> Желаю удачи в разборе полётов 3 переменных!

Давай лучше напиши третий выпуск на таком примере:

if($enabled)
{
if($has_property)
do_it();
if($one_more_check)
do_another();
}
else
{
do_another();
do_it();
}

A4 комментирует...

> A стоит над первым столбцом, В стоит во второй строке - мдам... логика уже пошла курить лесом

Это ты о чём? Я ошибся в рассуждениях?

Dmitry Kalabin комментирует...

> Это ты о чём? Я ошибся в рассуждениях?

это я о том что кроме булевой логики есть еще более крутое понятие - просто ЛОГИКА. Есть вещи логичные и нелогичные.
когда A в ПЕРВОМ столбце, а B во ВТОРОЙ строке - то это на мой взгляд выглядит немного странно. :) Где логика? Хотя если преположить что в дальнейшем все будет развиваться примерно так: C в третьем столбце, а D в четвертой строке... то вроде все начинает опять становиться логично.

A4 комментирует...

По-моему, я вполне последовательно объяснил, что А=да в том столбце, над которым она нарисована. То же касается В. Их можно поменять местами, ничего это не изменит в рассуждениях.

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

if(!$enabled || $has_property)
  do_it();

if(!$enabled || $one_more_check)
  do_another();

А пример из 3 переменных напишу.

Отправить комментарий