Home  >  Article  >  Backend Development  >  How Far You Can Optimize a Program to Compute the Fibonacci Sequence?

How Far You Can Optimize a Program to Compute the Fibonacci Sequence?

王林
王林Original
2024-08-21 15:21:33608browse

How Far Can You Optimize a Program to Compute the Fibonacci Sequence?

Introduction

When I was learning Python, our teacher gave us a homework -- calculate the Nth number of Fibonacci Sequence.

I think it's very easy, so I write this code:

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

Later, I know this kind of solution cost too much time.

Optimize a Program

I change the solution to iteration.

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

    return ls[n-1]

I use matplotlib draw the time it cost:

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()

Result Here:

How Far You Can Optimize a Program to Compute the Fibonacci Sequence?

The time it cost is very short.

But I write fib(300000), cost 5.719049899998936 seconds. It's too long.

When I grow up, I learn CACHE, so I change the solution to use dict to store the result.

from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

Or we can write the CACHE by ourself.

def fib(n, cache={}):
    if n in cache:
        return cache[n]
    elif n < 2:
        return 1
    else:
        ls = [1, 1]
        for i in range(2, n):
            next_value = ls[-1] + ls[-2]
            ls.append(next_value)
            cache[i] = next_value
        cache[n-1] = ls[-1]
        return ls[-1]

The above is the detailed content of How Far You Can Optimize a Program to Compute the Fibonacci Sequence?. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn