in
>
> 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.

Is this a set of numbers, or a set of (for example) vectors?

It makes a difference, for the reason that Frank was talking about
before, namely that a vector in the set might be altered (by
assigning to one of its entries). A set of vectors can thus NOT be
guaranteed to stay sorted, even if no changes are made to the set
itself, only changes to the elements.

Steve