#optimization #expression #boolean-expression #sat
Вопрос:
Я работаю над механизмом правил потоковой передачи, и у некоторых моих клиентов есть несколько сотен правил, которые они хотели бы оценивать при каждом событии, поступающем в систему. Правила являются чистыми (т. е. не влияющими на побочные эффекты) Логические выражения, и они могут быть вложены произвольно глубоко.
Клиенты создают, обновляют и удаляют правила во время выполнения, и мне нужно динамически обнаруживать и адаптироваться к совокупности правил. На данный момент оценка выражения использует интерпретатор поверх внутреннего AST, и я еще не начал думать о codegen.
Как всегда, некоторые из предикатов в дереве НАМНОГО дешевле оценить, чем другие, и я искал алгоритм или структуру данных, которые облегчали бы поиск дешевых предикатов, которые можно правильно интерпретировать как управляющие всем выражением. Мой мысленный заголовок для этого шаблона — «ИДА до самого корня», то есть любой предикат, для которого все предки являются ИДА, можно интерпретировать как управляющий.
Несмотря на несколько дней поиска литературы, чтения о ROBDDs, CNF, DNF и т. Д., Я не смог перейти от того, что может быть обычной практикой в отрасли, К моему конкретному варианту использования. Одна вещь, которую я обнаружил, кажется связанной,-это анализ и оптимизация для индексирования логических выражений, но неясно, как я мог бы применить ее, не реализуя структуру данных BE-Tree самостоятельно, поскольку, похоже, нет реализации с открытым исходным кодом.
Я продолжаю полушутя упоминать своей команде, что на днях нам понадобится решатель SAT. 😅 Я думаю, что, вероятно, было бы достаточно написать рекурсивный алгоритм, который пересекает дерево и отслеживает, является ли каждый предок «И» или «ИЛИ», но я продолжаю испытывать чувство «конечно, это решенная проблема».:)
Редактировать: Поговорив с парой друзей, я думаю, что у меня может быть набросок решения!
- Преобразуйте выражения в Конъюнктивальную Нормальную форму, в которой, по определению, каждый узел находится в допустимом положении короткого замыкания.
- Используйте алгоритм Цейтина, чтобы попытаться избежать экспоненциального увеличения размера выражения в результате преобразования CNF
- Для каждого И в дереве отсортируйте его в порядке возрастания стоимости (т. е. Самый дешевый слева).
- ???
- Прибыль!^Вевал, как обычно 🙂
Комментарии:
1. Классная проблема. Похоже, порядок правил не имеет значения (интересно). Я предполагаю, что вы хотите отложить вертикальное масштабирование, сделав сначала «дешевые». Как выглядят правила? Структурированы ли они в соответствии со схемой или это просто код (похоже на первое)?
2. @Adam Предикаты-это простая логическая логика с базовыми функциями сравнения. Ни одна из поддерживаемых функций не отслеживает состояние или побочные эффекты, но они могут использовать данные, которые генерируются или загружаются более сложными способами. Существует три источника данных в порядке увеличения стоимости: 1. Поля только в текущей записи [O(1) память и вычисления]; 2. Агрегаты по записям в сеансе (оконные и все время) [O(n) память; сложность вычисления зависит от выбранной агрегатной функции]; 3. Атрибуты, полученные из поиска [O(1) память и вычисления, но задержка…]
3. Вы преждевременно оптимизируете — я имею в виду, что произойдет, если вы просто наивно проанализируете дерево и остановитесь на первом «ложном» (предполагая, что это так работает — прекратите анализ ветви, если вы нажмете «ложное»)? Я чувствую, что кэширование/запоминание, вероятно, может пройти здесь долгий путь, прежде чем заказывать по самым дешевым путям (в любом случае невозможно сравнить O(n) и задержку, верно?)
4. Извините, это всего лишь моя интерпретация вашей проблемы, теперь, когда я смотрю на нее, я вижу, что вы спрашиваете, считает ли кто-нибудь, что это «решенная проблема» в другом месте. Если это так, то я с этим не сталкивался. Однако я провел много личных экспериментов с использованием механизмов правил, использующих доморощенные AST. Я всегда просто «начинал с самого верха» и выходил из игры, когда набирал ложь (в зависимости от правила). Однако никогда не пытался сделать что-либо подобное в очень больших масштабах.
5. Оптимизация будет применяться только при изменении набора активных правил (порядка нескольких десятков раз в день), и ее результаты будут использоваться во время выполнения для повышения эффективности обработки событий.
Ответ №1:
Вам следует серьезно подумать о составлении правил (и предикатов). Интерпретатор в 10-50 раз медленнее, чем машинный код для того же самого. Это хорошая идея, если набор правил меняется не очень часто. Это даже хорошая идея, если правила могут изменяться динамически, потому что на практике они все еще меняются не очень быстро, хотя теперь ваш компилятор правил находится в сети. Эх, просто делает приложение более масштабным, и память больше не является большой проблемой.
Оценка логического выражения с использованием отдельных машинных инструкций еще лучше. Любое сложное булево уравнение может быть составлено в виде последовательностей отдельных машинных инструкций без ветвей по конечным значениям. Никаких ветвей, никаких промахов в кэше; все работает чертовски быстро. Теперь, если у вас есть дорогие предикаты, вы, вероятно, захотите скомпилировать код с ветвями, чтобы пропустить поддеревья, которые не влияют на результат выражения, если они содержат дорогие предикаты.
В разумных пределах вы можете сгенерировать любую эквивалентную форму (я бы кричал всю ночь над идеей использования CNF, потому что это всегда взрывается на вас). То, что вам действительно нужно, — это кратчайшее логическое уравнение (самое глубокое дерево выражений), эквивалентное тому, что предоставили клиенты, потому что для выполнения этого потребуется наименьшее количество машинных инструкций. Это может показаться безумием, но вы можете подумать о создании кода исчерпывающего поиска, например, буквально попробовать каждую комбинацию, у которой есть шанс сработать, особенно если количество операторов в уравнении относительно невелико. Мир СБИС упорно работает над выполнением различных оптимизаций при синтезе булевых уравнений в элементы. Вам следует заглянуть в оптимизатор логической логики Эспрессо (https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer)
Одна вещь, которая может заставить вас оценить выражение, — это буквально стоимость предикатов. если у меня есть формулы A и B, и я знаю, что оценка A обходится дорого и обычно возвращает значение true, то ясно, что вместо этого я хочу оценить B и A.
Вам следует рассмотреть возможность оценки общего подэкспрессии, чтобы любой общий подэкспрессионный термин вычислялся только один раз. Это особенно важно, когда у вас есть дорогие предикаты; вы никогда не захотите оценивать один и тот же дорогой предикат дважды.
Я реализовал эти трюки в эмуляторе ПЛК (это в основном машины, которые оценивают блоки [например, сотни тысяч] булевых уравнений, указывающих заводским приводам, когда двигаться), используя машинные инструкции x86 для И/ИЛИ/НЕ для Rockwell Automation около 20 лет назад. Он превосходил «премьер» ПЛК Роквелла, который имел специальное оборудование, но по сути был интерпретатором.
Вы также можете рассмотреть возможность инкрементной оценки уравнений. Основная идея состоит не в том, чтобы переоценивать все уравнения снова и снова, а скорее в том, чтобы переоценивать только те уравнения, входные данные которых изменились. Подробности слишком длинны, чтобы включать их здесь, но патент, который я сделал тогда, объясняет, как это сделать. Видишь https://patents.google.com/patent/US5623401A/en?inventor=Ira Д Бакстер и ок=Ира Д Бакстер
Комментарии:
1. Эй, спасибо! Я перечитаю это несколько раз. 🙂 кстати, было бы лучше не делиться ссылками на патенты на сайте, ориентированном на разработчиков 😅
2. Все в порядке, срок действия патента давно истек.
3. Алгоритм эспрессо также был моей первой мыслью. Он очень способен значительно сократить сложные булевы функции, и после этого, если вам нужно пойти дальше, вы можете использовать что-то с большей точностью. Где-то в Интернете есть реализация на языке Си. Я не рекомендую реализовывать его самостоятельно, так как это довольно сложно.