Sejauh Mana Anda Boleh Mengoptimumkan Program untuk Mengira Jujukan Fibonacci?

Sejauh Mana Anda Boleh Mengoptimumkan Program untuk Mengira Jujukan Fibonacci?

pengenalan

Semasa saya belajar Python, guru kami memberi kami kerja rumah -- hitung nombor Nth Jujukan Fibonacci.

Saya rasa ia sangat mudah, jadi saya tulis kod ini:

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

Nanti, saya tahu penyelesaian sebegini memakan masa yang terlalu lama.

Optimumkan Program

Saya menukar penyelesaian kepada lelaran.

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

    return ls[n-1]

Saya menggunakan matplotlib draw masa kosnya:

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

Keputusan Di Sini:

Masa kosnya sangat singkat.

Tetapi saya menulis fib(300000), kos 5.719049899998936 saat. Ia terlalu panjang.

Apabila saya dewasa, saya belajar CACHE, jadi saya menukar penyelesaian untuk menggunakan dict untuk menyimpan hasilnya.

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)

Atau kita boleh tulis CACHE sendiri.

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]

Atas ialah kandungan terperinci Sejauh Mana Anda Boleh Mengoptimumkan Program untuk Mengira Jujukan Fibonacci?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!