-1

I tried to implement an efficient function to return the Fibonacci value for a given index. Once I discovered the cons of implementing a basic/simple recursion function to return the Fibonacci series, I realized that the computation time required starts scaling exponentially for larger values of N as it keeps repeating calculations, leading to redundancy.

However, I later discovered that there is a technique to mitigate said problem... "Memoization". Basically, my understanding of what it does is that it caches previously calculated values and uses them for subsequent calculations, thereby mitigating any redundancy.

I’m curious about which implementation is more efficient - mine or the one I found online. I know that there can be small differences in the time it takes to run code, but the difference between my code and the other one seems pretty big when N is large.

Here's my code: [06_fibo_dict.py]

import timeit

my_dict = {}

def fibonacci(n):
    """ To print the fibonacci series efficiently """
    if n == 1:
        x = 0
        my_dict[n] = x
        return x

    elif n == 2:
        fibonacci(1)
        x = 1
        my_dict[n] = x
        return x

    elif n == 3:
        fibonacci(2)
        x = 1
        my_dict[n] = x
        return x

    elif n > 3:
        fibonacci(n-1)
        x = my_dict[n-2] + my_dict[n-1]
        my_dict[n] = x
        return x

number = int(input("Enter N: "))

t = timeit.timeit(lambda: fibonacci(number), number=10)

fib = fibonacci(number)

print(f"Number: {fib}\n Time: {t:.32f}")

Output for my code:

$ python 06_fibo_dict.py
Enter N: 100
Number: 218922995834555169026
Time: 0.00059320009313523769378662109375


$ python 06_fibo_dict.py
Enter N: 200
Number: 173402521172797813159685037284371942044301
Time: 0.00105599989183247089385986328125

Here's the code I found online: [07_fibo_memo.py]

import timeit

def fibonacci(n, cache={}):
    if n in cache:
        return cache[n]

    if n == 1:
        result = 0

    elif n == 2:
        result = 1

    else:
        result = fibonacci(n-1) + fibonacci(n-2)

    cache[n] = result
    return result

number = int(input("Enter N: "))

t = timeit.timeit(lambda: fibonacci(number), number=10)

fib = fibonacci(number)

print(f"Number: {fib}\n Time: {t:.32f}")

Output for code I found online:

$ python 07_fibo_memo.py
Enter N: 100
Number: 218922995834555169026
Time: 0.00000469991937279701232910156250


$ python 07_fibo_memo.py
Enter N: 200
Number: 173402521172797813159685037284371942044301
Time: 0.00000709993764758110046386718750
N00B_141
  • 11
  • 3
  • If you are going to create your own dictionary to cache results, initialize it properly so you don't have to handle the special cases in code: See : https://stackoverflow.com/a/76836917/218663 – JonSG Aug 12 '23 at 14:54
  • 2
    I don't think `time.time` is recommended for timing code, use `timeit`. – Mark Ransom Aug 12 '23 at 15:11
  • 1
    Since you fixed the bug pointed out by @KellyBundy the timings seem a lot closer, probably within the error margin of your timing method. Is this question even still relevant? – Mark Ransom Aug 12 '23 at 15:28
  • Well I changed it from using `time.time` to `timeit.timeit` and the difference seems to show now... Btw, why is `timeit.timeit` more accurate than `time.time`? – N00B_141 Aug 12 '23 at 15:44

1 Answers1

1

Because your code is recursing all the way down to 0, without a shortcut when it already has the lesser values in the map, it's doing unnecessary work. The version you found elsewhere will only need to do the work from 700 down to 500 on your second call.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622