why memoizing is faster

[Terry Reedy]

On 3/24/2011 9:48 AM, Andrea Crotti wrote:

>    def fib_iter(n):
>        ls = {0: 1, 1:1}

Storing a linear array in a dict is a bit bizarre

>        for i in range(2, n+1):
>            ls[i] = ls[i-1] + ls[i-2]
>
>        return ls[max(ls)]

So is using max(keys) to find the highest index, which you already know 
(it is n). Actually, fib_iter(0) will return fib_iter(1), and in general 
that would be wrong. Above should just be ls[n].

Third, why toss away the array only to recalculate with each call?
Memoizing *is* faster ;-). So do it for the iterative version too.

> and what happens is surprising, this version is 20 times slower then the
> recursive memoized version.

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]

This should be slightly faster than the crazy-key cache for the memoized 
recursive version.

-- 
Terry Jan Reedy