No, Thomas is correct. He's not talking about Rete memories, but about
how Fact objects work.
Unordered facts are basically arrays where each slot has a known
name at a fixed index. During pattern-matching, the names aren't used;
the fixed indexes are known and the individual slots are accessed at
their known offsets. This is possible because the rule compiler does
all the loopkups during rule compilation.
But when you assert an unordered fact, the individual slots of the
fact have to be looked up -- i.e., you know the name of the slot, and
need the index. There are two possibilities here: 1) you can do a
linear search through a table to find the name, and thus the offset,
or 2) you can use some kind of fancy indexing -- i.e., a hash
table. Populating every slot of a fact does, indeed, scale like s^2
if you use the first technique -- s being the number of slots in the
deftemplate. If you use 2), then the lookup can happen more or less
constant time.
Now, remember, s is the size of one fact, not the size of the problem
-- i.e., not the number of facts. Therefore all we're talking about
is the relative time it takes to load one fact.
Nevertheless, Jess uses 1), not 2). Why? Well, basically on the theory
that for small facts -- i.e., 5 slots or so -- 1) is faster than 2)
because the constant of proportionality C is large. i.e., s^2 <
C. Now, I have to admit that I've never actually tested this
theory. I've never profiled a Jess program where the time taken by
this lookup even appeared, so I've never been confronted with the need
to do anything different.
Perhaps the time has come to do the experiment, though.
----------------------------------------------------------------------
Anyway, Norman -- there is another thing you can try that may have a
dramatic impact. By default Jess checks for fact duplication and only
asserts a fact if an identical one doesn't already exist. Many people
depend on this for program correctness. But this check will take more
and more time as more facts are asserted. In the worst case -- only
one deftemplate -- it takes time proportional to n^2, the square of
the number of facts. If your facts are known to be unique, or if your
rules won't care about duplication, you can turn this off by using
(set-fact-duplication TRUE) . Give this a try and let me know if it
helps.
----------------------------------------------------------------------
I think Satish boggavarapu wrote:
[Charset iso-8859-1 unsupported, filtering to ASCII...]
> If Jess used unsorted Linear lists it would be O(s^2), but it uses some kind
> of Hashtables. So it should be O(s)...
>
>
>
> -----Original Message-----
> From: Thomas Barnekow [mailto:[EMAIL PROTECTED]]
> Look at the Fact class. Setting a single slot value has a
> runtime
> complexity of O(s) (an average of s/2 steps), where s is the number of
> slots. This is because a slot index has to be looked up in an unsorted
> linear list
> of slots. Setting all slot values then requires s^2 / 2 steps, which is
> O(s^2).
>
---------------------------------------------------------
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]
---------------------------------------------------------------------
