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
example the 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
example suppose 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
ridiculous.
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 Set
, Difference
, Intersection
and Union
are known
to be sets by construction, and thus have the flag set upon creation.
If an argument to IsSet
, IsEqualSet
, IsSubset
, Set
, Difference
,
Intersection
or 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.
Note that 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,
Add
or 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 in
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.
GAP 3.4.4