This is an addition to Caridorc's answer.
The usual reason for using
itertools is that you don't want to construct lists when you don't need to. For example, in Python 2, you'd write
for i in xrange(100) instead of
for i in range(100) so that you don't have to construct a whole list of 100 numbers when you don't need it. If this doesn't make sense to you, familiarize yourself with the difference between generator expressions (genexprs) and list types.
In your case, however, there's a much more serious problem. You've got a Shlemiel the painter's algorithm!
When you write
reduce(list.__add__, list_of_lists), you're essentially writing
list_1 + ... + list_n. Python will evaluate this as follows:
list_2. Create a new list object of the proper size, and copy the elements from lists 1 and 2 into this new list. Call it
list_3. Create a new list of the proper size, and copy the elements from these two lists into the new list. Call it
list_n. Create a new list of the proper size, and copy the elements from these two lists into the new list. This is the final result.
Do you see the problem? This code is quadratic in both runtime and memory usage.
Here's some hard data. Consider the following function:
lists = [ * 10000 for i in xrange(n)]
combined = reduce(list.__add__, lists)
I ran this for values of
n of 1, 10, 100, 200, 250, 300, 400, and 500 (using IPython's
%timeit fn(100), which does proper timing), and got the following results:
This definitely looks quadratic, and the coefficient of determination is R2 = 0.99655, which indicates an extremely strong correlation.
When we instead use
combined = list(itertools.chain.from_iterable(
 * 10000 for i in xrange(n)))
the time for
fast(500) is just 65.8 ms instead of 7.42 s. (This shows that it is indeed the Shlemiel factor and not just large lists that's causing the slowdown.)
So, tl;dr, yes, use iterators—but make sure you know why!
So when use
Just a review of what
reduce does for binary operators:
reduce(int.__add__, [x1, x2, x3], x0) = (((x0 + x1) + x2) + x3)
This is extended to general functions as follows:
reduce(f, [x1, x2, x3], x0) = f(f(f(x0, x1), x2), x3)
You should use
reduce when you want to write code that looks like either of the above examples. Basically,
reduce just saves you a loop.
Conceptually, you use reduce when you want to collapse a bunch of things into one value.
It may help to think of
reduce in comparison with its other core functional operations:
map when you want to transform a bunch of values to other things (like "reverse all these strings"). You use
map in list comprehensions when you write
[s[::-1] for s in strings].
filter when you want to take a bunch of values and keep just some of them (like "take just the strings that are palindromes"). You use
reduce in list comprehensions when you write
[s for s in strings if s == s[::-1]].
reduce when you want to collapse a bunch of things into one value (like "concatenate all these strings"). You can't use
reduce in list comprehensions, because you're not creating a new list (just a value).
- The problem in your case is that the version with
list_1 + ... + list_n is just as bad in terms of efficiency.
reduce wasn't your problem; it was what
reduce expanded to.
reduce, you can omit the third argument
reduce will use the first element of the sequence, or raise a
TypeError if the sequence is empty.
Before noting some examples, it may be helpful to realize that some operations from
__builtins__ are just
reduce under the hood. For example:
sum(ints) = reduce(int.__add__, ints, 0);
all(bools) = reduce(lambda x, y: x and y, bools, True), and, similarly;
any(bools) = reduce(lambda x, y: x or y, bools, False);
min(ints) is like
reduce(lambda x, y: x if x < y else y, ints) (it's actually a bit smarter), and, similarly;
max(ints) is like
reduce(lambda x, y: x if x > y else y, ints).
A few quick examples:
return reduce(int.__mul__, xrange(1, n + 1), 1)
return reduce(lambda board, move: board.then(move),
return reduce(lambda head, commit: head.cherry_pick(commit),
I don't use reduce all that much in Python, but you should definitely know when to use it.