why memoizing is faster

[Terry Reedy]

On 3/25/2011 4:49 AM, Andrea Crotti wrote:
> Terry Reedy<tjreedy at udel.edu>  writes:
>> def fib_iter(n, _cache = [1,1]):
>>    k = len(_cache)
>>    if n>= k:
>>      for i in range(k, n+1):
>>         _cache.append(_cache[i-2] + _cache[i-1])
>>    return _cache[n]

I just realized that the signature really ought to be
     def fib_iter(n, *, _cache = [1,1]):
so that the _cache parameter is keyword only (relatively new feature), 
so that it cannot be overwritten by accident but only by intentional 
resetting of what by its name is obviously intended to be a private, do 
not touch value. This pretty much eliminates one objection people have 
had to this sort of thing.

Actually, it should be
   def fib_iter(n, *, _cache = [0,1]):
to match the standard definition that fib(0)=0, etc.
https://secure.wikimedia.org/wikipedia/en/wiki/Fibonacci_number
I just happened to copy the your initialization.
People who omit 0 from the series also usually leave fib(0) undefined.

> If it had a more "expected" behaviour of instantiating a new cache
> dictionary every time this trick would not be possible.

Next time someone claims that mutable defaults are not useful, I will 
try to remember to show this example again.

-- 
Terry Jan Reedy