Subject: Re: Inserting clauses

From: Jan Wielemaker <[email-masked]>
Date: Thu, 6 Apr 2000 11:45:35 +0200

On Wed, 05 Apr 2000, Robert van Engelen wrote:
>> >I use pattern matching to determine the position of the new clause in the
>> >clauses. The pattern matching technique is comparable to the techniques
>> >applied in functional programming languages to order function definitions.
>> 
>> This is clear.
>> 
>> Time to run profile/3 and see where the time is spend.  If updating is
>> not (almost) linear with the number of clauses you might have hit some
>> implementation error.  In that case, send the program with instructions.
>
>Each update is almost linear. The time complexity of the algorithm
>to retract and assert for each insertion is linear in the number of clauses.
>It just seems very odd that the only way to insert a clause is to retract
>the first clauses, store them in a list (or in my case store them in the local
>variables of the recursive predicate instantiation that inserts a clause)
>and put them back later. The algorithm may scale in time, because each clause
>before the inserted one needs to be analysed anyway, but doesn't the algorithms
>have overhead in the temporary storage of clauses? (Your suggestion below
>alleviates this problem, but is not applicable in my case because clauses may
>be permanently removed later leaving some other clauses that are never used.)
>
>Here are some statistics for 300 clauses:
>
>/home/faculty/engelen/Ctadel2/lib/simplify.pl compiled into simplify, 11.34 sec, 1,776 bytes.
>2,815,095 inferences in 11.34 seconds (248245 Lips)
>Predicate                   Box Entries =     Calls+Redos = Exits+Fails
>Time
>===============================================================================
>$clause/3                        89,893 =       89,878+15 = 89,854+39     21.8%
>asserta/1                        44,921 =        44,921+0 = 44,921+0       8.6%
>numbervars/4                    179,362 =       179,362+0 = 179,362+0      7.1%
>mp:mp_compare1/3                180,809 =   92,134+88,675 = 92,134+88,675  5.1%

It appears you are using a version older then 3.3.  3.3 is quite a bit
faster on clause/[2,3]!

The odd thing is of course, how can you do almost 45,000 asserts to
rearrange 300 clauses?

It appears you are sorting them.  I expect this should be written as:

	retract all clauses into a list
	sort them
	re-assert them.

If possible, generate a `key' for each clause and use keysort/2 instead
comparing them directly.  It also appears mp:mp_compare1/3 is
non-deterministic and could be made deterministic (#redos == #fails).

I would be surprised if it should take longer then a second and worse
then order N*log(N), which appears more then good enough for your
purposes.

	Regards --- Jan