> < ^ From:

> < ^ Subject:

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

> < [top]