Dictionary

[Peter Otten]

Phu Sam wrote:

> The condition  'if not fibs.get(n):'  will not work because
> n = 0
>       fibs.get(0) is 0 so not 0 is 1
> 
> Here is the modified code that works:
> 
> fibs={0:0,1:1}
> def rfib(n):
>       if n == 0 or n == 1:
>           return fibs[n]
>       else:
>         fibs[n]=rfib(n-2)+rfib(n-1)
>         return fibs[n]
> 
>>>> rfib(8)
> 21
>>>> fibs
> {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21}
> 
> 
> Cheers,

The problem with this implementation is that it recalculates the results for 
n > 1 over and over again. You construct that nice lookup table and then you 
don't use it.

Compare:

$ cat rfib.py
fibs={0:0,1:1}

def rfib(n):
      if n == 0 or n == 1:
          return fibs[n]
      else:
        fibs[n]=rfib(n-2)+rfib(n-1)
        return fibs[n]

sfibs = {0: 0, 1: 1}

def sfib(n):
    try:
        return sfibs[n]
    except KeyError:
        pass
    result = sfibs[n] = sfib(n-1) + sfib(n-2)
    return result

for i in range(10):
    assert rfib(i) == sfib(i)

$ python3 -m timeit -s 'import rfib' 'rfib.rfib(25)'
10 loops, best of 3: 102 msec per loop
$ python3 -m timeit -s 'import rfib' 'rfib.sfib(25)'
1000000 loops, best of 3: 0.371 usec per loop