피보나치 수열을 계산하기 위해 프로그램을 어디까지 최적화할 수 있나요?

王林
풀어 주다: 2024-08-21 15:21:33
원래의
607명이 탐색했습니다.

피보나치 수열을 계산하기 위해 프로그램을 어디까지 최적화할 수 있습니까?

소개

파이썬을 배울 때 선생님께서 피보나치 수열의 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()

로그인 후 복사

결과:

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

소요되는 시간이 매우 짧습니다.

하지만 저는 fib(300000)을 썼고, 비용은 5.719049899998936초였습니다. 너무 길어요.

어른이 되면 CACHE를 배워서 결과를 저장하기 위해 dict를 사용하도록 솔루션을 변경합니다.

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)

로그인 후 복사

아니면 CACHE를 직접 작성할 수도 있습니다.

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]
로그인 후 복사

위 내용은 피보나치 수열을 계산하기 위해 프로그램을 어디까지 최적화할 수 있나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:dev.to
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!