diff options
| -rw-r--r-- | Doc/lib/lib.tex | 1 | ||||
| -rw-r--r-- | Doc/lib/libsets.tex | 219 |
2 files changed, 220 insertions, 0 deletions
diff --git a/Doc/lib/lib.tex b/Doc/lib/lib.tex index 671c106..6b52d63 100644 --- a/Doc/lib/lib.tex +++ b/Doc/lib/lib.tex @@ -122,6 +122,7 @@ and how to embed it in other applications. \input{libbisect} \input{libheapq} \input{libarray} +\input{libsets} \input{libcfgparser} \input{libfileinput} \input{libxreadlines} diff --git a/Doc/lib/libsets.tex b/Doc/lib/libsets.tex new file mode 100644 index 0000000..65ca8e7 --- /dev/null +++ b/Doc/lib/libsets.tex @@ -0,0 +1,219 @@ +\section{\module{sets} --- + Unordered collections of unique elements} + +\declaremodule{standard}{sets} +\modulesynopsis{Implementation of sets of unique elements.} +\moduleauthor{Greg V. Wilson}{gvwilson@nevex.com} +\moduleauthor{Alex Martelli}{aleax@aleax.it} +\moduleauthor{Guido van Rossum}{guido@python.org} +\sectionauthor{Raymond D. Hettinger}{python@rcn.com} + +\versionadded{2.3} + +The \module{sets} module provides classes for constructing and manipulating +unordered collections of unique elements. Common uses include membership +testing, removing duplicates from a sequence, and computing standard math +operations on sets such as intersection, union, difference, and symmetric +difference. + +Like other collections, sets support \code{x in s}, \code{len(s)}, and +\code{for x in s}. Being an unordered collection, sets do not record element +position or order of insertion. Accordingly, sets do not support indexing, +slicing or other sequence-like behavior. + +Most set applications use the \class{Set} class which provides every set +method except for \method{__hash__()}. For advanced applications requiring +a hash method, the \class{ImmutableSet} class adds a \method{__hash__()} +method but omits methods which alter the contents of the set. Both +\class{Set} and \class{ImmutableSet} derive from \class{BaseSet}, an +abstract class useful for determining whether something is a set: +\code{isinstance(x, BaseSet)}. + +The set classes are implemented using dictionaries. As a result, sets cannot +contain mutable elements such as lists or dictionaries. However, they can +contain immutable collections such as tuples or instances of +\class(ImmutableSet). For convenience in implementing sets of sets, +inner sets are automatically converted to immutable form, for example, +\code{Set([Set(['dog'])])} is transformed to +\code{Set([ImmutableSet(['dog'])])}. + +\begin{classdesc}{Set}{\optional{iterable}} +Constructs a new empty \class{Set} object. If the optional \var{iterable} +parameter is supplied, updates the set with elements obtained from iteration. +All of the elements in \var{iterable} should be immutable or be transformable +to an immutable using the protocol described at \ref{immutable-transforms}. +\end{classdesc} + +\begin{classdesc}{ImmutableSet}{\optional{iterable}} +Constructs a new empty \class{ImmutableSet} object. If the optional +\var{iterable} parameter is supplied, updates the set with elements obtained +from iteration. All of the elements in \var{iterable} should be immutable or +be transformable to an immutable using the protocol described at +\ref{immutable-transforms}. + +Because \class{ImmutableSet} objects provide a \method{__hash__()} method, +they can be used as set elements or as dictionary keys. \class{ImmutableSet} +objects do not have methods for adding or removing elements, so all of the +elements must be known when the constructor is called. +\end{classdesc} + + +\subsection{set Objects} + +Instances of \class{Set} and \class{ImmutableSet} both provide +the following operations: + +\begin{tableiii}{c|l|c}{code}{Operation}{Result}{Notes} + \lineiii{len(\var{s})}{cardinality of set \var{s}}{} + + \hline + \lineiii{\var{x} in \var{s}} + {test \var{x} for membership in \var{s}}{} + \lineiii{\var{x} not in \var{s}} + {test \var{x} for non-membership in \var{s}}{} + \lineiii{\var{s}.issubset(\var{t})} + {test whether every element in \var{s} is in \var{t}}{} + \lineiii{\var{s}.issuperset(\var{t})} + {test whether every element in \var{t} is in \var{s}}{} + + \hline + \lineiii{\var{s} | \var{t}} + {new set with elements from both \var{s} and \var{t}}{} + \lineiii{\var{s}.union(\var{t})} + {new set with elements from both \var{s} and \var{t}}{} + \lineiii{\var{s} & \var{t}} + {new set with elements common to \var{s} and \var{t}}{} + \lineiii{\var{s}.intersection(\var{t})} + {new set with elements common to \var{s} and \var{t}}{} + \lineiii{\var{s} - \var{t}} + {new set with elements in \var{s} but not in \var{t}}{} + \lineiii{\var{s}.difference(\var{t})} + {new set with elements in \var{s} but not in \var{t}}{} + \lineiii{\var{s} ^ \var{t}} + {new set with elements in either \var{s} or \var{t} but not both}{} + \lineiii{\var{s}.symmetric_difference(\var{t})} + {new set with elements in either \var{s} or \var{t} but not both}{} + \lineiii{\var{s}.copy()} + {new set with a shallow copy of \var{s}}{} +\end{tableiii} + +In addition to the above operations, both \class{Set} and \class{ImmutableSet} +support set to set comparison operators based on the contents of their +internal dictionaries. Two sets are equal if and only if every element of +each set is contained in the other. + +The following table lists operations available in \class{ImmutableSet} +but not found in \class{Set}: + +\begin{tableiii}{c|l|c}{code}{Operation}{Result}{Notes} + \lineiii{hash(\var{s})}{returns a hash value for \var{s}}{} +\end{tableiii} + +The following table lists operations available in \class{Set} +but not found in \class{ImmutableSet}: + +\begin{tableiii}{c|l|c}{code}{Operation}{Result}{Notes} + \lineiii{\var{s} |= \var{t}} + {return set \var{s} with elements added from \var{t}}{} + \lineiii{\var{s}.union_update(\var{t})} + {return set \var{s} with elements added from \var{t}}{} + \lineiii{\var{s} &= \var{t}} + {return set \var{s} keeping only elements also found in \var{t}}{} + \lineiii{\var{s}.intersection_update(\var{t})} + {return set \var{s} keeping only elements also found in \var{t}}{} + \lineiii{\var{s} -= \var{t}} + {return set \var{s} after removing elements found in \var{t}}{} + \lineiii{\var{s}.difference_update(\var{t})} + {return set \var{s} after removing elements found in \var{t}}{} + \lineiii{\var{s} ^= \var{t}} + {return set \var{s} with elements from \var{s} or \var{t} but not both}{} + \lineiii{\var{s}.symmetric_difference_update(\var{t})} + {return set \var{s} with elements from \var{s} or \var{t} but not both}{} + + \hline + \lineiii{\var{s}.add(\var{x})} + {Add element \var{x} to set \var{s}}{} + \lineiii{\var{s}.remove(\var{x})} + {Remove element \var{x} from set \var{s}}{} + \lineiii{\var{s}.discard(\var{x})} + {Removes element \var{x} from set \var{s} like \var{s}.remove(\var{x}) + but does not raise a KeyError if \var{x} is not in \var{s}}{} + \lineiii{\var{s}.pop()} + {Remove and return a randomly-chosen element from \var{s}}{} + \lineiii{\var{s}.update(\var{t})} + {Add elements from \var{t} to set \var{s}}{} + \lineiii{\var{s}.clear()} + {Remove all elements from set \var{s}}{} +\end{tableiii} + + +\subsection{Example} + +\begin{verbatim} +>>> from sets import Set +>>> engineers = Set(['John', 'Jane', 'Jack', 'Janice']) +>>> programmers = Set(['Jack', 'Sam', 'Susan', 'Janice']) +>>> management = Set(['Jane', 'Jack', 'Susan', 'Zack']) +>>> employees = engineers | programmers | management # union +>>> engineering_management = engineers & programmers # intersection +>>> fulltime_management = management - engineers - programmers # difference +>>> engineers.add('Marvin') # add element +>>> print engineers +Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack']) +>>> employees.issuperset(engineers) # superset test +False +>>> employees.update(engineers) # update from another set +>>> employees.issuperset(engineers) +True +>>> for group in [engineers, programmers, management, employees]: + group.discard('Susan') # unconditionally remove element + print group + +Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack']) +Set(['Janice', 'Jack', 'Sam']) +Set(['Jane', 'Zack', 'Jack']) +Set(['Jack', 'Sam', 'Jane', 'Marvin', 'Janice', 'John', 'Zack']) +\end{verbatim} + + +\subsection{Protocol for automatic conversion to immutable + \label{immutable-transforms}} + +Sets can only contain immutable elements. For convenience, mutable +\class{Set} objects are automatically copied to an \class{ImmutableSet} +before being added as a set element. + +The mechanism is to always add a hashable element, or if it is not hashable, +the element is checked to see if it has an \method{_as_immutable()} method +which returns an immutable equivalent. + +Since \class{Set} objects have a \method{_as_immutable()} method +returning an instance of \class{ImmutableSet}, it is possible to +construct sets of sets. + +A similar mechanism is needed by the \method{__contains__()} and +\method{remove()} methods which need to hash an element to check +for membership in a set. Those methods check an element for hashability +and, if not, check for a \method{_as_Temporarily_Immutable} method +which returns the element wrapped by a class that provides temporary +methods for \method{__hash__()}, \method{__eq__()}, and \method{__ne__()}. + +The alternate mechanism spares the need to build a separate copy of +the original mutable object. + +\class{Set} objects implement the \method{_as_Temporarily_Immutable} method +which returns the \class{Set} object wrapped by a new class +\class{_TemporarilyImmutableSet}. + +The two mechanisms for adding hashability are normally invisible to the +user; however, a conflict can arise in a multi-threaded environment +where one thread is updating a Set while another has temporarily wrapped it +in \class{_TemporarilyImmutableSet}. In other words, sets of mutable sets +are not thread-safe. + + + + + + + |