why memoizing is faster

[Tim Wintle]

On Fri, 2011-03-25 at 09:49 +0100, Andrea Crotti wrote:
> Terry Reedy <tjreedy at udel.edu> writes:
> >
> > For the reason Stefan explained and hinted above. Try the following instead:
> >
> > 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 don't get what's the difference between that and:
> 
> def fib_iter(n):
>     ls = [0, 1]
>     for i in range(2, n+1):
>         ls.append(ls[i-2] + ls[i-1])
> 
>     return ls[n]

> How can passing a default "_cache" argument can make such a difference?

Default values are initialised at definition time.

Since lists are mutable, the _cache variable really is a cache - the
following time you call the function it will store all the previous
calculations.

e.g.

>>> def default_value(_cache=[]):
...   _cache.append(len(_cache))
...   print _cache
... 
>>> default_value()
[0]
>>> default_value()
[0, 1]
>>> default_value()
[0, 1, 2]
>>> default_value()
[0, 1, 2, 3]