28.10 More about Sets

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.

Previous Up Top
Index

GAP 3.4.4
April 1997