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].
--------------------------------------------------------------------
