> < ^ Date: Thu, 13 Jan 1994 22:34:00 +1000
> < ^ From: Dmitrii Pasechnik <d.pasechnik@twi.tudelft.nl >
> < ^ Subject: Re: AddSet again

Dear Forum,
> Some time ago we noticed that the function Orbit(G,S,OnSets) can be
> hopelessly slow when |S| and in particular the length of the resulting
> orbit are big enough.
>
> if <S> is a big set the comparison between sets will be relative
> expensive, together with the fact that 'AddSet' has to check all
> elements this is taking the time. A short example: Take a set of 4000
> vectors of length 450 and sort them in reversed order. Now start with
> the first vector and build up a new set using 'AddSet'. The insertion
> process during the addition of elements is as bad as can be. On a
> NeXT this process will indeed be incredibly slow taking nearly an hour
> to complete. However, if your remove the test in 'AddSet' that the
> first argument is really a set, it will take 20sec, 10 of those - I
> would guess - being used in the insertion process. Using Trees,
> hashing or whatever will reduce this 10sec to maybe less than 1sec.
> So you have a gain of 10sec in an 1 hour procedure. If on the other
> hand you simply drop the test, you will speed up the whole thing by a
> factor of 200.

Yes, I see now that the main problem is that AddSet calls IsSet rather
than it spends lots of time for actual rewriting of the set.
However, looking at IsSet, one sees that first of all it tests
whether it is already known that the argument is a set by checking
certain flag in its record. In the best of my knowledge,
it is really fast providing this flag is set to `yes`.

Note that the sets in question are generated as the images of the
original set S. The image of S is a set, so the corresponding
function which computes the image of a set under a permutation (see the
module permutat.c) should set , I believe, the abovementioned flag to `yes`.
(In other words there might be a bug)

Otherwise I fail to understand why
the removal of the call to IsSet can improve performance of
Orbit(,,OnSets) so dramatically.

Best regards,
Dima Pasechnik


> < [top]