Py2.3: Feedback on Sets (fwd)

[David Mertz]

|[David Mertz]
|> Yeah :-).  Which points out that I should have actually READ Raymond's
|> function, rather than just cut-and-paste it.  This seems to point out
|> that even the Python developers are able to make mistakes in
|> implementing powerset().

|It wasn't a mistake.
|I do prefer Alex's improvement because it has a weaker precondition,
|but the basic code and generation method was dead-on.

Well... I'm not sure about dead-on.  For example:

  % cat time_powerset.py
  from sets import Set
  from time import clock

  def rh_powerset(iterable):
      data = list(iterable)
      for i in xrange(2**len(data)):
          yield Set([e for j,e in enumerate(data) if i&(1<<j)])

  def am_powerset(iterable):
      data = Set(iterable)
      for i in xrange(2**len(data)):
          yield Set([e for j,e in enumerate(data) if i&(1<<j)])

  start = clock()
  print Set(rh_powerset('aaaaaaaaaaaaaaaaaaa'))
  print 'rh_powerset(): %.4f seconds' % (clock()-start)

  start = clock()
  print Set(am_powerset('aaaaaaaaaaaaaaaaaaa'))
  print 'rh_powerset(): %.4f seconds' % (clock()-start)

What do you reckon gets output? How about:

  % python time_powerset.py
  Set([ImmutableSet([]), ImmutableSet(['a'])])
  rh_powerset(): 74.9403 seconds
  Set([ImmutableSet([]), ImmutableSet(['a'])])
  rh_powerset(): 0.0000 seconds

So Raymond's version is AT LEAST 750,000 times slower for this
particular iterable than Alex' :-).  (Alex' is just too quick to time on
my machine, I get zero when I extend the decimals in the time display).
Actually, the ratios quickly get even worse if I add a couple more
"a"s... until Raymond's raises an exception (and Alex' keeps producing
the right answer too quickly to measure.

I know Python isn't primarily focused on speed.  But somewhere around
the point where one function is a million times slower than an
algorithmically equivalent one, I start to think the latter is a
smidgeon broken.

--
 mertz@   _/_/_/_/_/_/_/ THIS MESSAGE WAS BROUGHT TO YOU BY:_/_/_/_/ v i
gnosis  _/_/                    Postmodern Enterprises         _/_/  s r
.cx    _/_/  MAKERS OF CHAOS....                              _/_/   i u
      _/_/_/_/_/ LOOK FOR IT IN A NEIGHBORHOOD NEAR YOU_/_/_/_/_/    g s