Path: utzoo!attcan!uunet!samsung!munnari.oz.au!bruce!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Why is bagof so slow?
Keywords: bagof, setof
Message-ID: <3081@goanna.cs.rmit.oz.au>
Date: 27 May 90 12:02:08 GMT
References: <2556@randvax.UUCP>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 30

In article <2556@randvax.UUCP>, narain@randvax.UUCP (Sanjai Narain) writes:
> In the following program, there is one fact about f, namely f(1). 
> Running times of two queries ... are compared:
> 	f(X).			%   25 micro-seconds each
> 	bagof(X, f(X), S). 	% 1200 micro-seconds each
> Why a 40-fold difference in speed?

bagof/3 has to put the answers *somewhere*.  Some Prologs have a special
'setof stack' or a "bubble" in the heap.  Quintus Prolog basically does
a special cheap assert and a special cheap retract, so it's faster than
what you could write directly, but it's still an assert and a retract,
and the old rule of thumb "1 data base change per millisecond" still holds
good.  The cost is likely to go down, but for large solution sets the cost of
sorting to find solutions with the same bindings for free variables
(or of sorting to eliminate duplicate solutions if you use setof/3, which
is almost always the right thing to do) is O(NlgN) and is going to swamp
O(N), and for small solution sets the cost of finding the answers usually
dominates.  I can imagine a 4-fold speed-up for this bagof/3 call (relative
to other operations) with the aid of a special "setof stack" and special
support code.  Is this a very big problem?  How many more copies of Quintus
Prolog could be sold for each x% speedup of bagof/3?

> Are there ways to speed up computation of sets?

Depends on what the computation is doing.  Tell me more about your real
problem.

-- 
"A 7th class of programs, correct in every way, is believed to exist by a
few computer scientists.  However, no example could be found to include here."