Home Original page

To Reduce or Not To Reduce

Moshe Zadka moshez at math.huji.ac.il
Fri Feb 25 10:08:44 EST 2000 
On Fri, 25 Feb 2000, Gerrit Holl wrote:

> First, I had this code:
> 
> >>> def fib(n):
> >>>  retval = 0
> >>>  for i in range(n):
> >>>      retval = retval + i
> >>>  return retval
> 
> I thought: this must be slow, because it redefines 'retval' for every n.

Well, actually, local variable access is done via array indexing, which
is very fast.

> So I rewrote it using reduce:
> 
> >>> def fib(n):
> >>>  return reduce(operator.add, xrange(n))

operator.add is slightly slower then the + operator. It's the C function
call arg parsing that's killing you.

> Timing turns out, however, that this version is actually _slower_! Maybe
> this is because it has to look up 'add' in another namespace. Getting 'add'
> in the local namespace only optimizes it a little bit. 

Of course! It only looks up operator.add once. I'm surprised you managed
to see a difference!

> What am I missing? When should I use reduce?

Not this time:

How about 

def fib(n):
	return (n*(n-1))/2

This function, of course, has nothing to do with the fibonacci function.

BTW: When comparing, try not to let noise into the system. Either
consistently use "range" or consistently use "xrange".
--
Moshe Zadka <mzadka at geocities.com>. 
INTERNET: Learn what you know.
Share what you don't.
More information about the Python-list mailing list