Home Original page

reduce()--what is it good for? (was: Re: reduce() anomaly?)

Terry Reedy tjreedy at udel.edu
Fri Nov 7 21:38:57 EST 2003 
"Alex Martelli" <aleaxit at yahoo.com> wrote in message
news:aKVqb.109736$e5.3978380 at news1.tin.it...
> above.  Try:
> x = reduce(operator.add, listoflists, x)
> vs:
> for L in listoflists: x.extend(L)
> for a sufficiently big listoflists, and you'll see... (the latter if
need be
> can get another nice little multiplicative speedup by hoisting the
x.extend
> lookup, but the key issue is O(N**2) reduce vs O(N) loop...).

Right: however that issue and the possibility of hoisting x.extend
have *nothing* to do with reduce vs. for.  For a fair comparison of
the latter pair, try the following, which is algorithmicly equivalent
to your sped-up for loop.

>>> xs=[[i] for i in range(10)]
>>> x=[]
>>> xtend=x.extend
>>> reduce(lambda dum,L: xtend(L), xs, x)
>>> x
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


[timeits snipped]...
> See what I mean?

That you hate reduce?

I am sure that the O(N) reduce would be similarly faster than an
O(N**2) operator.add for loop: what would *that* mean?

> Already for a mere 999 1-item lists, the plain Python
> code is 10 times faster than reduce,

No, you have only shown that for N=999, O(N) can be O(N**2)/10, and
that smart programmers who understand that can write better (faster)
code than those who do not.

Terry J. Reedy

PS: for practical rather than didactic programming, I am pretty sure I
would have written a for loop 'reduced' with xtend.
More information about the Python-list mailing list