Как переупорядочить булеву логику для короткого замыкания быстрее? - PullRequest
Новая
       5

Как переупорядочить булеву логику для короткого замыкания быстрее?

2 голосов
/ 28 марта 2012

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

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

def q():
    print "q"
    return False

def r():
    print "r"
    return False

def s():
    print "s"
    return False

def a():
    print "a"
    return False

def b():
    print "b"
    return False

def c():
    print "c"
    return False


def d():
    print "d"
    return False

def i():
    print "i"
    return False

def j():
    print "j"
    return False


(q() or r() or s()) and (a() and b() and c() and (i() or j()))

В этом случае вы видите напечатанный qrs.Все Ложь, так что это короткие замыкания.В этом случае, однако, ab или c должны быть оценены первыми, так как, если какой-либо из них является False, все выражение является False.Предположим, что выражение в конце генерируется пользователем так, что я не могу жестко закодировать наилучший возможный порядок.Я думаю, что есть довольно простой алгоритм, который мне не хватает.

Две другие вещи:

1.) Что если я разрешу другую логику, например, "нет"?2.) Могу ли я присвоить каждой функции балл в зависимости от того, сколько времени потребуется для ее запуска, а затем рассчитать это в?

Ответы [ 2 ]

2 голосов
/ 28 марта 2012

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

def evaluate_or(argument_evaluation_list):
    total_cost = 0.0
    probability_of_reaching = 1.0
    for cost, probability_of_true in argument_evaluation_list:
        total_cost += probability_of_reaching * cost
        probability_of_reaching *= 1.0 - probability_of_true
    return total_cost, 1.0 - probability_of_reaching

def evaluate_and(argument_evaluation_list):
    total_cost = 0.0
    probability_of_reaching = 1.0
    for cost, probability_of_true in argument_evaluation_list:
        total_cost += probability_of_reaching * cost
        probability_of_reaching *= probability_of_true
    return total_cost, probability_of_reaching

def evaluate_not(argument_evaluation)
    cost, probability_of_true = argument_evaluation
    return cost, 1.0 - probability_of_true
1 голос
/ 28 марта 2012

Ваша формула в CNF (кстати, вам не нужны эти круглые скобки вокруг верхнего уровня or с), что очень удобно для сложности вычислений, это действительно простая формула.Поскольку у вас нет not на данный момент, я действительно не знаю, нужно ли искать какие-то сложные алгоритмы, ваша формула уже достаточно проста, я бы сказал.Но вы определенно можете попробовать какую-то эвристику (например, начать с оценки предложений, имеющих как можно меньше литералов, чтобы вы потерпели неудачу как можно быстрее ... проблема в том, что даже если вы начинаете с предложения, имеющего только один литерал,вычисление функции может оказаться более дорогим, чем вычисление более крупных предложений, поэтому да, имеет смысл не сортировать их по размеру, а по ожидаемой вычислительной сложности).

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

...