[Python-Dev] Re: A `cogen' module [was: Re: PEP 218 (sets); moving set.py to Lib]
Guido van Rossum
Wed, 28 Aug 2002 15:41:00 -0400
> 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/)