reduce()--what is it good for?

[Alex Martelli]

JCM wrote:

> Alex Martelli <aleax at aleax.it> wrote:
> ...various good points...
> 
>> if one is in a hurry, recursion and
>> memoization are obviously preferable:
> 
>> def facto(n, _memo={1:1}):
>>     try: return _memo[n]
>>     except KeyError:
>>         result = _memo[n] = (n-1) * facto(n-1)
>>         return result
   ...
>> [alex at lancelot bo]$ timeit.py -c -s'import facs' 'facs.facto(13)'
>> 1000000 loops, best of 3: 1.26 usec per loop
> 
> I'm going off topic, but it's really not fair to compare a memoized
> function to non-memoized implementations using a "best of 3" timing
> test.

The best-of-3 is irrelevant, it's the million loops that help:-).

Of course you can memoize any pure function of hashable args.  But
memoizing a recursive implementation of factorial has a nice property, 
shared by other int functions implemented recursively in terms of their 
values on other ints, such as fibonacci numbers: the memoization you do for 
any value _helps_ the speed of computation for other values.  This nice 
property doesn't apply to non-recursive implementations.

Once you run timeit.py, with its million loops (and the best-of-3, but 
that's not crucial:-), this effect disappears.  But on smaller tests it is 
more easily seen.  You can for example define the memoized functions
by a def nested inside another, so each call of the outer function will undo 
the memoization, and exercise them that way even with timeit.py. E.g.:

import operator

def wireduce(N=23):
    def factorial(x, _memo={0:1, 1:1}):
        try: return _memo[x]
        except KeyError:
            result = _memo[x] = reduce(operator.mul, xrange(2,x+1), 1)
            return result
    for x in range(N, 0, -1): factorial(x)

def wirecurse(N=23):
    def factorial(x, _memo={0:1, 1:1}):
        try: return _memo[x]
        except KeyError:
            result = _memo[x] = x * factorial(x-1)
            return result
    for x in range(N, 0, -1): factorial(x)

[alex at lancelot bo]$ timeit.py -c -s'import aa' 'aa.wireduce()'
1000 loops, best of 3: 710 usec per loop
[alex at lancelot bo]$ timeit.py -c -s'import aa' 'aa.wirecurse()'
1000 loops, best of 3: 280 usec per loop


Alex