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

王林
Release: 2024-08-21 15:21:33
Original
618 people have browsed it

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)
Copy after login

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]
Copy after login

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

Copy after login

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)

Copy after login

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]
Copy after login

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!

source:dev.to
Statement of this Website
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
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template