From jan@swi.psy.uva.nl Fri Nov 16 16:18:15 2001
Received: from gollem.swi.psy.uva.nl (root@gollem [145.18.152.30])
	by swi.psy.uva.nl (8.11.2/8.11.2) with ESMTP id fAGFIFt06297;
	Fri, 16 Nov 2001 16:18:15 +0100 (MET)
Received: from localhost (localhost [[UNIX: localhost]])
	by gollem.swi.psy.uva.nl (8.11.3/8.11.3/SuSE Linux 8.11.1-0.5) id fAGFIFx08821;
	Fri, 16 Nov 2001 16:18:15 +0100
From: Jan Wielemaker <jan@swi.psy.uva.nl>
Organization: SWI, University of Amsterdam
To: Sebastian John <sebc@cs.tu-berlin.de>, prolog@swi.psy.uva.nl
Subject: Re: [SWIPL]
Date: Fri, 16 Nov 2001 16:00:17 +0100
X-Mailer: KMail [version 1.0.29.2]
Content-Type: text/plain
References: <200111161442.PAA00813@toffees.cs.tu-berlin.de>
In-Reply-To: <200111161442.PAA00813@toffees.cs.tu-berlin.de>
MIME-Version: 1.0
Message-Id: <01111616181402.07839@gollem>
Content-Transfer-Encoding: 8bit

On Fri, 16 Nov 2001, Sebastian John wrote:
>Hi,
>
>thanks for your interests and your emails. But there is still a
>problem.
>
>> It is often possible to get huge speedups in Prolog code by
>> rewriting the code to use better data structures or algorithms while
>> remaining entirely in Prolog.
>
>I can not fasten my problem by using minor prolog optimizations,
>because the best theoretical known solution is exponential. I think
>some tricks on the CPU cache would do it. 
>
>To make the problem transparent: I use a predicate equiv(+A,+B). For
>simplicity I assume A and B are lists. It is not necessary to know the
>elements if there are of the kind atom, string, integer etc pp or
>compound. The only thing is to know how much elements are in the lists
>and which elements of A are part of B. So I want to use such things
>like an array of the elements representing the lists A or B on which I
>can efficiently compute, ie to test if the terms a identical. 
>
>And I thought prolog use unique representations for all data
>structures. I know prolog use unique representations for atoms. And
>the only thing is to use them. Eg by getting the pointer to this
>representations. Ie different pointers means different terms/atom/...
>identical pointers means identical term/atom/... So I would save time
>and code to explore the terms without to use PL_is_compound,
>PL_is_atom, PL_is_string, PL_is_integer ... and PL_get_compound,
>PL_get_atom, PL_get_string, PL_get_integer ..., and all the
>PL_new_term_ref() for each substructure.

PL_*_pointer() aren't meant for that (and are completely unusable for
this too).  For the problem statement, the trivial solution is to sort
both lists and then walk along the sorted lists.  The order of this
is 2*N*log(N)+N (or simply N*log(N)).

If you insist doing it in C, you can do better using PL_term_type() and
switch on the result thereof instead of repeating PL_is_*().  If you
want to get to the real bottom, you can hack using direct pointers
by integrating your code in the Prolog kernel only.  You're basically
on your own there.

	Regards --- Jan

