Нулы и слюни

Я был действительно счастлив увидеть движок правил в Node, а также изучал Drools в мире Java и во время чтения документации (в частности: http://docs.jboss.org/drools/release/6.1.0.Final/drools-docs/html_single/index.html#PHREAK)found, что Drools 6.0 эволюционировал и теперь использует метод PHREAK для сопоставления правил. Конкретный параграф, который представляет интерес:

Каждая успешная попытка соединения в RETE создает кортеж (или токен, или частичное совпадение), который будет распространен на дочерние узлы. По этой причине он характеризуется как алгоритм, ориентированный на кортежи. Для каждого дочернего узла, которого он достигает, он будет пытаться соединиться с другой стороной узла, и снова каждая успешная попытка соединения будет распространяться немедленно. Это создает эффект рекурсии спуска. Разбивая сеть узлов, когда она колеблется вверх и вниз, влево и вправо от точки входа в бета-сеть ко всем доступным конечным узлам.

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

Поскольку nools основан на алгоритме Rete, действительно ли вышесказанное? Есть ли какие-нибудь оптимизации, похожие на PHREAK? Любые сравнения, сделанные с Drools?


node.js rule-engine drools
person user1749672    schedule 26.09.2014    source источник

Ответы (1)


arrow_upward
8
arrow_downward

Перегрузка сети является проблемой только тогда, когда вы хотите попробовать применить параллелизм и параллелизм, что требует блокировки областей. Поскольку NodeJS является однопоточным, это не будет проблемой. Мы еще не пытались решить эту проблему в Drools, но работа над Phreak была подготовкой с учетом этого, изучая проблемы, которые мы обнаружили в нашей реализации Rete. Отдельно стоит отметить, что в прошлом Rete использовал алгоритмы секционирования для параллелизма, и эта работа относится к той же области, что и проблема, которую он пытается решить.

Для однопоточных машин гораздо интереснее ленивое вычисление правил. Однако, как отмечается в документе, одно правило объединения не будет отличаться по производительности между Phreak и Rete. Когда вы добавляете множество правил, ленивый характер избегает потенциальной работы, тем самым экономя общие циклы процессора. Алгоритм также более снисходителен к большому количеству плохо написанных правил и должен меньше снижать производительность. Например, ему не нужен традиционный объект Rete root "Context", который используется для управления выбором правил и коротким замыканием излишне расточительного сопоставления - это будет рассматриваться как анти-шаблон в Phreak и может фактически замедлить его, когда вы сдуваете совпадения, которые он может использовать снова в будущем. http://www.dzone.com/links/rip_rete_time_to_get_phreaky.html

Также распространение, ориентированное на коллекцию, актуально, когда в правилах используется несколько подсетей, например, с несколькими накоплениями. http://blog.athico.com/2014/02/drools-6-performance-with-phreak.html

Я также изучил инфраструктуру обратной цепочки и оценки стека: http://blog.athico.com/2014/01/drools-phreak-stack-based-evaluations.html

Марк (создатель Phreak)

person Mark Proctor    schedule 19.10.2014
comment
Марк, спасибо за ваш вклад. Я углублюсь в предоставленные вами ссылки. Что касается производительности, можете ли вы указать на разницу между реализациями RETE и PHREAK? - person user1749672; 21.10.2014
comment
Нет единой дельты, очень сложно проводить прямые сравнения. Дело не в том, что ленивый алгоритм работает быстрее, он просто делает меньше, что во многих случаях приводит к более быстрому выполнению приложения. Первый предоставляет ссылку для одной такой дельты по использованию накоплений и подсетей, которая показывает лучший алгоритм на порядки. В других приложениях может наблюдаться только 10% прирост, а в некоторых других - 10% замедление. Хотя я надеюсь, что в последнем случае это просто вопрос профилирования и настройки, чтобы решить эту проблему. - person Mark Proctor; 21.10.2014
comment
Спасибо, Марк. Цените ваше понимание и ответ. - person user1749672; 23.10.2014