"Collapsing" a list into a list of changes

[Peter Otten]

John Lenton wrote:

> On Mon, Feb 07, 2005 at 07:07:10PM +0100, Francis Girard wrote:
>> Zut !
>> 
>> I'm very sorry that there is no good use case for the "reduce" function
>> in Python, like Peter Otten pretends. That's an otherwise very useful
>> tool for many use cases. At least on paper.
>> 
>> Python documentation should say "There is no good use case for the reduce
>> function in Python and we don't know why we bother you offering it."
> 
> I am guessing you are joking, right? I think Peter exaggerates when he
> says that "there will be no good use cases for reduce"; it is very
> useful, in writing very compact code when it does exactly what you
> want (and you have to go through hoops to do it otherwise). It also
> can be the fastest way to do something. For example, the fastest way
> to get the factorial of a (small enough) number in pure python is
> 
>   factorial = lambda n: reduce(operator.mul, range(1, n+1))
 
I see that you are seduced by the beauty of the expression. Otherwise, if
you would really care for speed:

$ cat factorial.py

#ugly but efficient
factorial = [1]
for i in range(1, 50):
    factorial.append(i*factorial[-1])


import operator
def factorial_reduce(n):
    return reduce(operator.mul, xrange(1, n+1), 1)

if __name__ == "__main__":
    assert factorial[0] == factorial_reduce(0) == 1
    assert factorial[5] == factorial_reduce(5) == 1*2*3*4*5

$ python2.4 -m timeit -s'import factorial as f' 'f.factorial_reduce(30)'
100000 loops, best of 3: 13.3 usec per loop
$ python2.4 -m timeit -s'import factorial as f' 'f.factorial[30]'
1000000 loops, best of 3: 0.328 usec per loop

Having factorial raise a UseStirlingsFormulaError for large values is left
as an exercise to the reader :-)


Peter