I think Jack Kerkhof wrote:
> Hi all,
>
> Can anyone help me out with understanding optimization of my Rete
> network. "Chapter 10. The Rete Algorithm" briefly discusses the issues,
> and the second last paragraph is particularly tantalizing, but I'm
> unclear on some of the details:
>
> - Using (watch compilations) I have noticed in my fact/rule base that
> there are many reuses of 1 input nodes (i.e. =1 on the output), but
> almost no sharing of 2 input nodes (i.e. almost no =2). This surprises
> me since many of the rules have similar but not quite the same patterns
> on the LHS.
>
> - What are the 'rules' in the algorithm for 2 input nodes to be shared?
> Can you describe this in terms of pattern matching components?
For a two input node to be shared, the two left-hand sides have to be
identical up to and including that node, except for trivial
differences like the use of different variable names or listing slots
in a different order.
Imagine drawing a flow chart for the LHS of each rule. Nodes can only
be shared to the extent that they are 1) identical on two flow
charts, and 2) every node feeding into them is duplicated on the two
flow charts as well.
>
> - Is the node sharing algorithm sensitive to the order of facts and/or
> fact slots on the LHS?
Order of facts - yes. Order of fact slots - no. If you have a set of
patterns that are repeated in a number of rules and you want them to
be shared, be sure that the repeated group is identically ordered in
each rule and appears at the beginning of each rule in which it
appears.
>
> - There are a number of (not ...) patterns in the rulebase. Does 'not'
> logic have special implications?
Yes. "Not" nodes are never shared.
>
> - Would the use of unordered facts over ordered facts substantially
> improve efficiency?
Yes, ordered facts are implemented in terms of multislots, and
multislots by their very nature are efficiency killers. If Jess knows
that there are exactly six slots in a fact and a given pattern matches
the fourth -- as opposed to having to determine the length at runtime
- it can build a much more efficient Rete network. Look for the MTMF
nodes in the pattern network - those are the nasty ones that can be
avoided by using unordered facts. The MTELN "counting" nodes are
indeed an O(F) effect but MTMF can be as bad as O(FL) where L is the
length of a multislot.
> I notice that ordered facts require a 'count fields' node (most
> obvious from the 'view' GUI). This seems like an O(F) impact at worst -
> correct?
>
> (side note: is there any way to scroll right on the 'view' display...)
Patches gratefully accepted :)
>
> Thanks to anyone who feels like tackling this...
>
> Jack
> --
> * This email is packaged by intellectual weight, not volume. Some
> settling of contents may occur during transmission.
>
>
> ---------------------------------------------------------------------
> 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
Distributed Systems Research Phone: (925) 294-2154
Sandia National Labs FAX: (925) 294-2234
Org. 8920, MS 9012 [EMAIL PROTECTED]
PO Box 969 http://herzberg.ca.sandia.gov
Livermore, CA 94550
---------------------------------------------------------------------
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]
---------------------------------------------------------------------
