> < ^ From:

> ^ Subject:

Forwarded message:

>From math.rwth-aachen.de!fceller Mon Jan 10 09:04:51 1994

Message-Id: <m0pJHYi-0000UKC@rowlf.Math.RWTH-Aachen.DE>

Date: Mon, 10 Jan 1994 09:00 +0100

From: Frank Celler <frank.celler@math.rwth-aachen.de>

To: J.Neubueser@math.rwth-aachen.de

In-reply-to: Dima Pasechnik's message of 7 Jan 94 20:44 WST <m0pIHQC-000LsCC@samson.Math.RWTH-Aachen.DE>

Subject: Meine Antwort

Content-Type: text

Dear Dima Pasechnik,

To be efficient, this function must involve the machinery for efficient

addition of elements in the set, e.g. AVL-trees etc.

yes, I completely agree with you on that point, unfortunately, as I

tried to explain, this is of little help with your orignal question:

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.

Once you have decided that sets are sorted lists without holes (I

explained why we didn't choose the other options, in this situation

things would have been different), your suggestion

call a function (say) Upgrade(l). One could suggest even better

ways, by taking some extra care *before* changing ....

will create dangerous traps. If one is purely thinking in the context

of orbits, I agree that

The example is rather strange, since it's more or less clear that any

set can be treated as a list with an ordering attached. The example in

question seems to violate this, i.e. make some elements of the set

incomparable. I doubt that in any serious computation one would make

things like that:

But unfortunately that point of view can only be taken in standalone

programs but not in a system like GAP. The example I gave you is not

a wild construct, it is a simplification of a real bug. When changing

from GAP 2.4 to 3.0 we experimented for a while with that. And

because of the tempting example above we tried if we can do without

the test in 'AddSet'. But this created a bug in one of the

representation theory programs, where sets were used in a completely

different seting (and sets there are very small). It took the

programmer a long time to find this really nasty bug. That was the

reason why we decided against a faster but insecure 'AddSet' and are

now using a slow but stable one.

On the other hand, and that was the point (e) I tried to explain, this

does not mean that one has to live with an (in some cases slow)

implementation of 'Orbit' (even now, where in most cases the operation

is costly, it is not too bad). But the example above shows that with

very little work involved one can easily speed up things, in that

example it does not even seem necessary to use trees or other

techniques. But in a situtation as Steve has described, which is in

some sense the other extreme because comparison and operation is very

cheap, 4-3-trees, red/black-trees, avl-trees, hashing, or bit-lists

could and should be used. But doing this in 'AddSet' will not help in

your sitution. So one has to do it in 'Orbit' (in which it will work

for both your and Steve's situation). This does not mean that one has

to do it in such a way that it can only be used in 'Orbit'. For

instance, if one would write a small package implementing functions to

create a tree structure, to add a new element, to test membership, and

to test and add, this could easily be used in various places.

Presumably all of this can be done with the existing datastructures

lists and records. But as I said, at the moment none of us here in

Aachen has the time to do it, so experiments/comments (like Steve's

'FastOrbit') from elsewhere are more than welcome. Wouldn't you like

to write such a package that would perform optimally for applications

like yours? We would surely appreaciate that.

best wishes Frank Celler and Joachim Neubueser ^ ^

> < [top]