Thanks again for your help! Other issue is curious for me. Is a computational complexity in forward and backward chaining mode the same? I have attached an example source code. It contains 4 rules about hierarchy of concepts. Every rule has some actions to perform. I am using need-facts to fire appropriate rule or rules. In this simple example I wonder if I can calculate the backward chaining complexity of run() function with formula O(RPAF) where R – the number of all rules which have been fired (not all rules in the working memory) P – average number of patterns per rule A – the number of all actions which have been executed F – the number of all need-facts which have been appeared during reasoning Thanks!
> On Feb 17, 2009, at 4:44 AM, Ksawi wrote: >> Thank you very much! >> Currently, I understand that I have not discovered the better way of >> querying :) >> So does it mean that the computational complexity of querying Jess >> in such way is O(FP), where P is the number of patterns in the query >> (is test also treated as a pattern?), and F is the number of facts? > The worst-case complexity of a naive pattern-matching algorithm is > O(F^P) -- the number of facts raised to the power of the number of > patterns in a rule. The Rete algorithm in general, and Jess > specifically, are designed to avoid this worst case. Because of the > intensive use of hash tables and caching, in the best case, Jess' > performance is O(P) and doesn't depend on the number of facts at all. > The reality is always somewhere between these extremes, and it depends > on the exact nature of the rules you write. >> I have another question. Is there any way to calculate the >> computational complexity of run() function? > It's certainly not simple. If none of your rules make any changes to > working memory (silly, I know) then for small numbers of rules, > performance is just going to be linear in the number of actions > executed -- i.e., O(RA), where R is the number of rules and A is the > number of actions per rule. Under the same conditions, if there are a > very large number of rules activated at the same time, then the > performance will eventually be dominated by the priority queue used to > order the activations -- O(N ln N), where N is the number of > simultaneously activated rules. > If your rules change working memory, then all bets are off. Whether > the priority queue or the pattern matching dominates is completely > problem-specific. >> Thanks a lot! >> -- >> Best regards! >> Jarek Bak >> > Jess is certainly designed for this last mode of operation: you >> define >> > the "program" (the rules and queries), populate the data, and then >> run >> > the program. In general, you'll get the most efficient operation if >> > you do things that way. >> > Remember that pattern matching is done during working memory >> changes; >> > if you define your rules first, the load-facts itself is going to >> take >> > longer. On the other hand, rules are more efficient than queries >> > because issuing a query involves asserting a "probe fact" that >> > specifies the query parameters. >> > On Feb 16, 2009, at 7:45 AM, Ksawi wrote: >> >> Dear all, >> >> I figured out some interesting behavior of Jess when I was querying >> >> it. I try to use Jess in forward chaining mode as a query >> machine. I >> >> query Jess from Java (I use runQueryStar function). >> >> For example: I have a file with 10540 facts and Jess script with >> >> only 7 deftemplates. The script does not contain any rule or other >> >> elements. >> >> When I load facts (using load-facts function) and then I query the >> >> Jess (query contains 20 patterns with about 25 tests, so it is the >> >> big query I think :)) the querying time is 31719 ms. >> >> But I think I found out better way to query the engine. I load >> facts >> >> and then I add the same query as a rule to the engine (for example >> >> (defrule name query =>)). Then I get activations (listActivations() >> >> function) and all the tokens in activations are the answer for the >> >> query. The querying time is 20969 ms. >> >> But then I found out much better way: First, I add the query as a >> >> rule and then I load all facts. Then I get activations and tokens >> >> are the answer. The time is 12390ms. >> >> In every case the number of results is the same (14892). >> >> So I have a question – is that normal behavior or am I doing >> >> something wrong? What is the reason of querying Jess even 3 times >> >> faster? >> >> Is there any way to calculate the computational complexity of >> >> querying the Jess engine in forward chaining mode? >> >> -- >> >> Best regards! >> >> Jarek Bak >> > --------------------------------------------------------- >> > Ernest Friedman-Hill >> > Informatics & Decision Sciences Phone: (925) 294-2154 >> > Sandia National Labs >> > PO Box 969, MS 9012 [email protected] >> > Livermore, CA 94550 http://www.jessrules.com >> > -------------------------------------------------------------------- >> > To unsubscribe, send the words 'unsubscribe jess-users [email protected] >> ' >> > in the BODY of a message to [email protected], NOT to the list >> > (use your own address!) List problems? Notify [email protected] >> . >> > -------------------------------------------------------------------- > --------------------------------------------------------- > Ernest Friedman-Hill > Informatics & Decision Sciences Phone: (925) 294-2154 > Sandia National Labs > PO Box 969, MS 9012 [email protected] > Livermore, CA 94550 http://www.jessrules.com > -------------------------------------------------------------------- > To unsubscribe, send the words 'unsubscribe jess-users [email protected]' > in the BODY of a message to [email protected], NOT to the list > (use your own address!) List problems? Notify [email protected]. > -------------------------------------------------------------------- -- Best regards! Jarek Bak
BackwardComplexity.clp
Description: Binary data
