In the previous section we defined a proper set as a sorted list without
holes or duplicates. This representation is not only nice to use, it is
also a good internal representation supporting efficient algorithms. For
in operator can use binary instead of a linear search since
a set is sorted. For another example
Union only has to merge the sets.
However, all those set functions also allow lists that are not proper
sets, silently making a copy of it and converting this copy to a set.
Suppose all the functions would have to test their arguments every time,
comparing each element with its successor, to see if they are proper
sets. This would chew up most of the performance advantage again. For
in would have to run over the whole list, to see if it
is a proper set, so it could use the binary search. That would be
To avoid this a list that is a proper set may, but need not, have an internal flag set that tells those functions that this list is indeed a proper set. Those functions do not have to check this argument then, and can use the more efficient algorithms. This section tells you when a proper set obtains this flag, so you can write your functions in such a way that you make best use of the algorithms.
The results of
Union are known
to be sets by construction, and thus have the flag set upon creation.
If an argument to
Union is a proper set, that does not yet have the
flag set, those functions will notice that and set the flag for this set.
in will use linear search if the right operand does not have
the flag set, will therefore not detect if it is a proper set and will,
unlike the functions above, never set the flag.
If you change a proper set, that does have this flag set, by assignment,
Append the set will generally lose it flag, even if the
change is such that the resulting list is still a proper set. However if
the set has more than 100 elements and the value assigned or added is not
a list and not a record and the resulting list is still a proper set than
it will keep the flag. Note that changing a list that is not a proper
set will never set the flag, even if the resulting list is a proper set.
Such a set will obtain the flag only if it is passed to a set function.
Suppose you have built a proper set in such a way that it does not have
the flag set, and that you now want to perform lots of membership tests.
Then you should call
IsSet with that set as an argument. If it is
indeed a proper set
IsSet will set the flag, and the subsequent
operations will use the more efficient binary search. You can think of
the call to
IsSet as a hint to GAP that this list is a proper set.
There is no way you can set the flag for an ordinary list without going
through the checking in
IsSet. The internal functions depend so much
on the fact that a list with this flag set is indeed sorted and without
holes and duplicates that the risk would be too high to allow setting the
flag without such a check.
Previous Up Top