[Python-Dev] Re: set() and frozenset()
David Eppstein
eppstein at ics.uci.edu
Sun Nov 16 13:42:09 EST 2003
In article <001401c3aba5$28a8a3c0$183ac797 at oemcomputer>,
"Raymond Hettinger" <raymond.hettinger at verizon.net> wrote:
> The C implementation of sets is now ready for your experimentation and
> comment. If fulfills most of Greg's proposal at:
> http://www.python.org/peps/pep-0218.html
...
> The differences from sets.py are:
>
> . The containers are now named set() and frozenset(). The lowercase
> convention is used to make the names consistent with other builtins like
> list() and dict(). User feedback said that the name ImmutableSet was
> unwieldy (?sp), so frozenset() was chosen as a more succinct
> alternative.
I for one found it difficult to remember whether it was Immutable or
Immutible.
> . There is no automatic conversion from the mutable type to the
> non-mutable type. User feedback revealed that this was never needed.
More than never needed, I would find it confusing to put a set into a
dictionary or whatever and then find that some other object has been put
there in its place.
> Also, removing it simplified the code considerably. The result is more
> straight-forward and a lot less magical. David Eppstein provided code
> examples demonstrating that set() and frozenset() are just right for
> implementing common graph algorithms and NFA/DFAs.
Well, I used Set and ImmutableSet, but yes, they're very useful.
Thanks to Raymond for adding the backward compatibility to Python 2.2
needed for me to try this out.
FWIW, I wrote another one yesterday, using a set partition refinement
technique for recognizing chordal graphs; the code is at
http://www.ics.uci.edu/~eppstein/PADS/Chordal.py, with subroutines in
LexBFS.py, PartitionRefinement.py, and Sequence.py. The same partition
refinement technique shows up in other algorithms including DFA
minimization and would be quite painful without sets.
Sets seems to me to be as fundamental a data structure as lists and
dictionaries, and I'm enthusiastic about this becoming built in and
faster. I would have liked to see {1,2,3} type syntax for sets, but the
set/frozenset issue makes that a little problematic and perhaps the new
iterator expressions make it unnecessary.
--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
More information about the Python-Dev
mailing list