Greg Wilson: Meta-question: do people want to continue to discuss sets on the general python-dev list, or take it out-of-line (e.g. to an egroups list)? I'm finding all of the discussion very useful, but I realize that many readers might prefer to concentrate on the 2.1 release...
Jeremy Hylton <jeremy@alum.mit.edu>:
The tests showed that dictionary-based sets were always faster. small tests (3 operations), the difference was about 10 percent. larger tests (88 operations), the difference ranged from 180 to almost 700 percent.
Eric Raymond <esr@thyrsus.com>: Not surprising. 88 elements is getting pretty large.
Greg Wilson: Really? I was testing my implementation with sets of email addresses grep'd out of old mail folders --- typical sizes were several thousand elements.
From: Christopher Petrilli <petrilli@amber.org> Unfortunately, for me, a Python implementation of Sets is only interesting academicaly. Any time I've needed to work with them at a large scale, I've needed them *much* faster than Python could achieve without a C extension.
Greg Wilson: I had been expecting to implement this in C, not in pure Python, for performance.
From: Christopher Petrilli <petrilli@amber.org> In the "scripting" problem domain, I would agree that Sets would rarely reach large sizes, and so a algorithm which performed in quadratic time might be fine,
Greg Wilson: I strongly disagree (see the email address example above --- it was the first thing that occurred to me to try). I am still hoping to find a sub-quadratic (preferably sub-linear) implementation. I can do it in C++ with observer/observable (contained items notify containers of changes in value, sets store all equivalent items in the same bucket), but that doesn't really help...
From: Ka-Ping Yee <ping@lfw.org> The only change that needs to be made to support sets of immutable elements is to provide "in" on dictionaries...
and:
From: Neil Schemenauer <nas@arctrix.com> ...if sets are added to the core...we would use the implementation of PyDict but drop the values.
Unfortunately, if values are required to be immutable, then sets of sets aren't possible... :-( Thanks, everyone, Greg