sys/src/cmd/python/Doc/lib/libsets.tex

   1 \section{\module{sets} ---
   2          Unordered collections of unique elements}
   3
   4 \declaremodule{standard}{sets}
   5 \modulesynopsis{Implementation of sets of unique elements.}
   6 \moduleauthor{Greg V. Wilson}{gvwilson@nevex.com}
   7 \moduleauthor{Alex Martelli}{aleax@aleax.it}
   8 \moduleauthor{Guido van Rossum}{guido@python.org}
   9 \sectionauthor{Raymond D. Hettinger}{python@rcn.com}
  10
  11 \versionadded{2.3}
  12
  13 The \module{sets} module provides classes for constructing and manipulating
  14 unordered collections of unique elements.  Common uses include membership
  15 testing, removing duplicates from a sequence, and computing standard math
  16 operations on sets such as intersection, union, difference, and symmetric
  17 difference.
  18
  19 Like other collections, sets support \code{\var{x} in \var{set}},
  20 \code{len(\var{set})}, and \code{for \var{x} in \var{set}}.  Being an
  21 unordered collection, sets do not record element position or order of
  22 insertion.  Accordingly, sets do not support indexing, slicing, or
  23 other sequence-like behavior.
  24
  25 Most set applications use the \class{Set} class which provides every set
  26 method except for \method{__hash__()}. For advanced applications requiring
  27 a hash method, the \class{ImmutableSet} class adds a \method{__hash__()}
  28 method but omits methods which alter the contents of the set. Both
  29 \class{Set} and \class{ImmutableSet} derive from \class{BaseSet}, an
  30 abstract class useful for determining whether something is a set:
  31 \code{isinstance(\var{obj}, BaseSet)}.
  32
  33 The set classes are implemented using dictionaries.  Accordingly, the
  34 requirements for set elements are the same as those for dictionary keys;
  35 namely, that the element defines both \method{__eq__} and \method{__hash__}.
  36 As a result, sets
  37 cannot contain mutable elements such as lists or dictionaries.
  38 However, they can contain immutable collections such as tuples or
  39 instances of \class{ImmutableSet}.  For convenience in implementing
  40 sets of sets, inner sets are automatically converted to immutable
  41 form, for example, \code{Set([Set(['dog'])])} is transformed to
  42 \code{Set([ImmutableSet(['dog'])])}.
  43
  44 \begin{classdesc}{Set}{\optional{iterable}}
  45 Constructs a new empty \class{Set} object.  If the optional \var{iterable}
  46 parameter is supplied, updates the set with elements obtained from iteration.
  47 All of the elements in \var{iterable} should be immutable or be transformable
  48 to an immutable using the protocol described in
  49 section~\ref{immutable-transforms}.
  50 \end{classdesc}
  51
  52 \begin{classdesc}{ImmutableSet}{\optional{iterable}}
  53 Constructs a new empty \class{ImmutableSet} object.  If the optional
  54 \var{iterable} parameter is supplied, updates the set with elements obtained
  55 from iteration.  All of the elements in \var{iterable} should be immutable or
  56 be transformable to an immutable using the protocol described in
  57 section~\ref{immutable-transforms}.
  58
  59 Because \class{ImmutableSet} objects provide a \method{__hash__()} method,
  60 they can be used as set elements or as dictionary keys.  \class{ImmutableSet}
  61 objects do not have methods for adding or removing elements, so all of the
  62 elements must be known when the constructor is called.
  63 \end{classdesc}
  64
  65
  66 \subsection{Set Objects \label{set-objects}}
  67
  68 Instances of \class{Set} and \class{ImmutableSet} both provide
  69 the following operations:
  70
  71 \begin{tableiii}{c|c|l}{code}{Operation}{Equivalent}{Result}
  72   \lineiii{len(\var{s})}{}{cardinality of set \var{s}}
  73
  74   \hline
  75   \lineiii{\var{x} in \var{s}}{}
  76          {test \var{x} for membership in \var{s}}
  77   \lineiii{\var{x} not in \var{s}}{}
  78          {test \var{x} for non-membership in \var{s}}
  79   \lineiii{\var{s}.issubset(\var{t})}{\code{\var{s} <= \var{t}}}
  80          {test whether every element in \var{s} is in \var{t}}
  81   \lineiii{\var{s}.issuperset(\var{t})}{\code{\var{s} >= \var{t}}}
  82          {test whether every element in \var{t} is in \var{s}}
  83
  84   \hline
  85   \lineiii{\var{s}.union(\var{t})}{\var{s} \textbar{} \var{t}}
  86          {new set with elements from both \var{s} and \var{t}}
  87   \lineiii{\var{s}.intersection(\var{t})}{\var{s} \&\ \var{t}}
  88          {new set with elements common to \var{s} and \var{t}}
  89   \lineiii{\var{s}.difference(\var{t})}{\var{s} - \var{t}}
  90          {new set with elements in \var{s} but not in \var{t}}
  91   \lineiii{\var{s}.symmetric_difference(\var{t})}{\var{s} \^\ \var{t}}
  92          {new set with elements in either \var{s} or \var{t} but not both}
  93   \lineiii{\var{s}.copy()}{}
  94          {new set with a shallow copy of \var{s}}
  95 \end{tableiii}
  96
  97 Note, the non-operator versions of \method{union()},
  98 \method{intersection()}, \method{difference()}, and
  99 \method{symmetric_difference()} will accept any iterable as an argument.
 100 In contrast, their operator based counterparts require their arguments to
 101 be sets.  This precludes error-prone constructions like
 102 \code{Set('abc') \&\ 'cbs'} in favor of the more readable
 103 \code{Set('abc').intersection('cbs')}.
 104 \versionchanged[Formerly all arguments were required to be sets]{2.3.1}
 105
 106 In addition, both \class{Set} and \class{ImmutableSet}
 107 support set to set comparisons.  Two sets are equal if and only if
 108 every element of each set is contained in the other (each is a subset
 109 of the other).
 110 A set is less than another set if and only if the first set is a proper
 111 subset of the second set (is a subset, but is not equal).
 112 A set is greater than another set if and only if the first set is a proper
 113 superset of the second set (is a superset, but is not equal).
 114
 115 The subset and equality comparisons do not generalize to a complete
 116 ordering function.  For example, any two disjoint sets are not equal and
 117 are not subsets of each other, so \emph{all} of the following return
 118 \code{False}:  \code{\var{a}<\var{b}}, \code{\var{a}==\var{b}}, or
 119 \code{\var{a}>\var{b}}.
 120 Accordingly, sets do not implement the \method{__cmp__} method.
 121
 122 Since sets only define partial ordering (subset relationships), the output
 123 of the \method{list.sort()} method is undefined for lists of sets.
 124
 125 The following table lists operations available in \class{ImmutableSet}
 126 but not found in \class{Set}:
 127
 128 \begin{tableii}{c|l}{code}{Operation}{Result}
 129   \lineii{hash(\var{s})}{returns a hash value for \var{s}}
 130 \end{tableii}
 131
 132 The following table lists operations available in \class{Set}
 133 but not found in \class{ImmutableSet}:
 134
 135 \begin{tableiii}{c|c|l}{code}{Operation}{Equivalent}{Result}
 136   \lineiii{\var{s}.update(\var{t})}
 137          {\var{s} \textbar= \var{t}}
 138          {return set \var{s} with elements added from \var{t}}
 139   \lineiii{\var{s}.intersection_update(\var{t})}
 140          {\var{s} \&= \var{t}}
 141          {return set \var{s} keeping only elements also found in \var{t}}
 142   \lineiii{\var{s}.difference_update(\var{t})}
 143          {\var{s} -= \var{t}}
 144          {return set \var{s} after removing elements found in \var{t}}
 145   \lineiii{\var{s}.symmetric_difference_update(\var{t})}
 146          {\var{s} \textasciicircum= \var{t}}
 147          {return set \var{s} with elements from \var{s} or \var{t}
 148           but not both}
 149
 150   \hline
 151   \lineiii{\var{s}.add(\var{x})}{}
 152          {add element \var{x} to set \var{s}}
 153   \lineiii{\var{s}.remove(\var{x})}{}
 154          {remove \var{x} from set \var{s}; raises \exception{KeyError}
 155           if not present}
 156   \lineiii{\var{s}.discard(\var{x})}{}
 157          {removes \var{x} from set \var{s} if present}
 158   \lineiii{\var{s}.pop()}{}
 159          {remove and return an arbitrary element from \var{s}; raises
 160           \exception{KeyError} if empty}
 161   \lineiii{\var{s}.clear()}{}
 162          {remove all elements from set \var{s}}
 163 \end{tableiii}
 164
 165 Note, the non-operator versions of \method{update()},
 166 \method{intersection_update()}, \method{difference_update()}, and
 167 \method{symmetric_difference_update()} will accept any iterable as
 168 an argument.
 169 \versionchanged[Formerly all arguments were required to be sets]{2.3.1}
 170
 171 Also note, the module also includes a \method{union_update()} method
 172 which is an alias for \method{update()}.  The method is included for
 173 backwards compatibility.  Programmers should prefer the
 174 \method{update()} method because it is supported by the builtin
 175 \class{set()} and \class{frozenset()} types.
 176
 177 \subsection{Example \label{set-example}}
 178
 179 \begin{verbatim}
 180 >>> from sets import Set
 181 >>> engineers = Set(['John', 'Jane', 'Jack', 'Janice'])
 182 >>> programmers = Set(['Jack', 'Sam', 'Susan', 'Janice'])
 183 >>> managers = Set(['Jane', 'Jack', 'Susan', 'Zack'])
 184 >>> employees = engineers | programmers | managers           # union
 185 >>> engineering_management = engineers & managers            # intersection
 186 >>> fulltime_management = managers - engineers - programmers # difference
 187 >>> engineers.add('Marvin')                                  # add element
 188 >>> print engineers
 189 Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack'])
 190 >>> employees.issuperset(engineers)           # superset test
 191 False
 192 >>> employees.union_update(engineers)         # update from another set
 193 >>> employees.issuperset(engineers)
 194 True
 195 >>> for group in [engineers, programmers, managers, employees]:
 196 ...     group.discard('Susan')                # unconditionally remove element
 197 ...     print group
 198 ...
 199 Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack'])
 200 Set(['Janice', 'Jack', 'Sam'])
 201 Set(['Jane', 'Zack', 'Jack'])
 202 Set(['Jack', 'Sam', 'Jane', 'Marvin', 'Janice', 'John', 'Zack'])
 203 \end{verbatim}
 204
 205
 206 \subsection{Protocol for automatic conversion to immutable
 207             \label{immutable-transforms}}
 208
 209 Sets can only contain immutable elements.  For convenience, mutable
 210 \class{Set} objects are automatically copied to an \class{ImmutableSet}
 211 before being added as a set element.
 212
 213 The mechanism is to always add a hashable element, or if it is not
 214 hashable, the element is checked to see if it has an
 215 \method{__as_immutable__()} method which returns an immutable equivalent.
 216
 217 Since \class{Set} objects have a \method{__as_immutable__()} method
 218 returning an instance of \class{ImmutableSet}, it is possible to
 219 construct sets of sets.
 220
 221 A similar mechanism is needed by the \method{__contains__()} and
 222 \method{remove()} methods which need to hash an element to check
 223 for membership in a set.  Those methods check an element for hashability
 224 and, if not, check for a \method{__as_temporarily_immutable__()} method
 225 which returns the element wrapped by a class that provides temporary
 226 methods for \method{__hash__()}, \method{__eq__()}, and \method{__ne__()}.
 227
 228 The alternate mechanism spares the need to build a separate copy of
 229 the original mutable object.
 230
 231 \class{Set} objects implement the \method{__as_temporarily_immutable__()}
 232 method which returns the \class{Set} object wrapped by a new class
 233 \class{_TemporarilyImmutableSet}.
 234
 235 The two mechanisms for adding hashability are normally invisible to the
 236 user; however, a conflict can arise in a multi-threaded environment
 237 where one thread is updating a set while another has temporarily wrapped it
 238 in \class{_TemporarilyImmutableSet}.  In other words, sets of mutable sets
 239 are not thread-safe.
 240
 241
 242 \subsection{Comparison to the built-in \class{set} types
 243             \label{comparison-to-builtin-set}}
 244
 245 The built-in \class{set} and \class{frozenset} types were designed based
 246 on lessons learned from the \module{sets} module.  The key differences are:
 247
 248 \begin{itemize}
 249 \item \class{Set} and \class{ImmutableSet} were renamed to \class{set} and
 250       \class{frozenset}.
 251 \item There is no equivalent to \class{BaseSet}.  Instead, use
 252       \code{isinstance(x, (set, frozenset))}.
 253 \item The hash algorithm for the built-ins performs significantly better
 254       (fewer collisions) for most datasets.
 255 \item The built-in versions have more space efficient pickles.
 256 \item The built-in versions do not have a \method{union_update()} method.
 257       Instead, use the \method{update()} method which is equivalent.
 258 \item The built-in versions do not have a \method{_repr(sorted=True)} method.
 259       Instead, use the built-in \function{repr()} and \function{sorted()}
 260       functions:  \code{repr(sorted(s))}.
 261 \item The built-in version does not have a protocol for automatic conversion
 262       to immutable.  Many found this feature to be confusing and no one
 263       in the community reported having found real uses for it.
 264 \end{itemize}