> < ^ From:

> < ^ Subject:

if you will take a closer look (actually you will find a comment

"perform the binary search"), you will see that 'AddSet' uses a binary

search, *but* it has to ensure that the list is indeed a set. To the

inexperienced user a simple solution to the problem is

It is not quite clear why faster ways to handle sets, such that the

addition of a new element takes only O(log(N)) operations, are not used

in the GAP implementation.but this naive approach has a drawback, namely that sets in this

proposal could only contain unchangeable data structures like integers

or permutations but not changeable like lists or records without

introducing some amount of overhead for *all* list/record assignments.

To illustrate the point, consider the following examples:

There is another problem, which I outlined to Martin a while ago.

Once it has decided where in the set the new entry is to be added,

AddSet then has to do O(N) work to make room for it by moving half

the set. The constant is pretty low, but it's still O(N).

My solution to this is to use blists rather than sets whenever

possible, and I have functions FastOrbit and FastOrbits which do

this, and differ from Orbit only in that they require the domain to

be given in full. Ideally functions like the Random Schreier-Sims

should use these techniques also.

Steve

> < [top]