फाइबोनैचि अनुक्रम की गणना करने के लिए आप किसी प्रोग्राम को कितनी दूर तक अनुकूलित कर सकते हैं?

परिचय

जब मैं पायथन सीख रहा था, हमारे शिक्षक ने हमें एक होमवर्क दिया - फाइबोनैचि अनुक्रम की Nवीं संख्या की गणना करें।

मुझे लगता है कि यह बहुत आसान है, इसलिए मैं यह कोड लिखता हूं:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1)   fib(n - 2)

बाद में, मुझे पता चला कि इस तरह के समाधान में बहुत अधिक समय लगता है।

किसी प्रोग्राम को अनुकूलित करें

मैं समाधान को पुनरावृत्ति में बदलता हूं।

def fib(n):
    ls = [1,1]
    for i in range(2,n):
        ls.append(ls[i-1] ls[i-2])

    return ls[n-1]

मैं matplotlib का उपयोग उस समय को निकालने के लिए करता हूं जिसकी लागत थी:

import time
import matplotlib.pyplot as plt


def bench_mark(func, *args):
    # calculate the time
    start = time.perf_counter()
    result = func(*args)
    end = time.perf_counter()

    return end - start, result  # return the time and the result

def fib(n):
    ls = [1,1]
    for i in range(2,n):
        ls.append(ls[i-1] ls[i-2])

    return ls[n-1]

mark_list = []

for i in range(1,10000):
    mark = bench_mark(fib,i)
    mark_list.append(mark[0])
    print(f"size : {i} , time : {mark[0]}")

plt.plot(range(1, 10000), mark_list)
plt.xlabel('Input Size')
plt.ylabel('Execution Time (seconds)')
plt.title('Test fot fibonacci')
plt.grid(True)
plt.show()

परिणाम यहां:

इसकी लागत बहुत कम है।

लेकिन मैं फाइब(300000) लिखता हूं, लागत 5.719049899998936 सेकंड। यह बहुत लंबा है।

जब मैं बड़ा होता हूं, तो मैं CACHE सीखता हूं, इसलिए मैं परिणाम को संग्रहीत करने के लिए dict का उपयोग करने के लिए समाधान बदलता हूं।

from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n 



या हम स्वयं CACHE लिख सकते हैं।


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