On Tue, Aug 27, 2002 at 09:26:00PM -0400, Guido van Rossum wrote:
> It occurred to me that this is rather ineffecient because it invokes
> itself recursively many time (once for each element in the first
> sequence). This version is much faster, because iterating over a
> built-in sequence (like a list) is much faster than iterating over a
> generator:
>
> def cartesian(*sequences):
> if len(sequences) == 0:
> yield []
> else:
> head, tail = sequences[:-1], sequences[-1]
> for x in cartesian(*head):
> for y in tail:
> yield x + [y]
My implementation from http://www.tothink.com/python/dataflow/xlazy.py:
def xcartprod(arg1, *args):
if not args:
for x in arg1:
yield (x,)
elif len(args) == 1:
arg2 = args[0]
for x in arg1:
for y in arg2:
yield x, y
else:
for x in arg1:
for y in xcartprod(args[0], *args[1:]):
yield (x,) + y
Special-casing the 2 argument case helps a lot. It brings the performace
within 50% of nested loops which means that if you actually do something
inside the loop the overhead is quite negligible.
The 'x' prefix is shared with other functions in this module: a lazy xmap,
xzip and xfilter.
> I also wonder if perhaps ``tail = list(tail)'' should be inserted
> just before the for loop, so that the arguments may be iterators as
> well.
Ahh... re-iterability again...
This is a good example of a function that *fails silently* for non
re-iterable arguments.
Slurping the tail into a list loses the lazy efficiency of this function.
One of the ways I've used this function is to scan combinations until a
condition is satisfied. The iteration is always terminated before reaching
the end. Reading ahead may waste computation and memory.
All I want is something that will raise an exception if any argument but
the first is not re-iterable (e.g. my reiter() proposal). I'll add list()
to the argument myself if I really want to. Don't try to guess what I
meant.
Oren
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4