[Python-Dev] Re: A `cogen' module [was: Re: PEP 218 (sets); moving set.py to Lib]

[Guido van Rossum]

> Of course, even statisticians cannot afford all subsets of sets having
> 100 elements, or will not scan permutations of 1000 elements.  But 100s
> or 1000s elements are well within the bounds of cartesian products.

Yes, and there the cost of an extra list() copy is neglegeable
(allocate and copy 4K bytes).

> > Or you might use Oren's favorite rule of thumb and listify it when iter(x)
> > is iter(x) (or iter(x) is x).
> 
> I'm a bit annoyed by the idea that `iter(x)' might require some computation
> for producing an iterator, and that we immediately throw away the result.
> Granted that `__iter__(self): return self' is efficient when an object is
> an iterator, but nowhere it is said that `__iter__' has to be efficient
> when the object is a container, and it does not shock me that some complex
> containers require time to produce their iterator.  I much prefer limiting
> the use of `__iter__' for when one intends to use the iterator...

Yes, that's why I prefer to just make a list() copy.

> > def powerset(base):
> >     """Powerset of an iterable, yielding lists."""
> >     pairs = [(2**i, x) for i, x in enumerate(base)]
> >     for n in xrange(2**len(pairs)):
> >         yield [x for m, x in pairs if m&n]
> 
> Thanks!  Hmph!  This does not yield the subsets in "sorted order", like
> the other `cogen' methods do, and I would prefer to keep that promise.

That may be a matter of permuting the bits?

> Hopefully, the optimisation I added this morning will make both algorithms
> more comparable, speed-wise.  I should benchmark them to see.

Yes!  Nothing beats a benchmark as an eye-opener.

--Guido van Rossum (home page: http://www.python.org/~guido/)