Как модернизировать код, чтобы он не считал долго?

Question

def F(n):
    if n<3:
        return 1
    elif n>2 and n%2!=0:
        return F(n-1)-F(n-2)
    elif n>2 and n%2==0:
        k=0
        for i in range(1,n):
            k+=F(i)
        return(k)

print(F(20))

Answer 1

Время приведённой функции экспоненциальное, как у рекурсивного вычисления Фибоначчи в лоб.

А вот алгоритм гораздо быстрее, квадратичный. Но его можно сделать линейным, если модифицировать расчёт суммы.

def FF(n):
    a = [1]*(n+1)
    for i in range(3, n+1):
        if i%2:
            a[i] = a[i-1]-a[i-2]
        else:
            a[i] = sum(a[1:i])
    return a[n]

Для того, чтобы не пересчитывать всю сумму, можно завести список частичных сумм и обновлять его при каждом расчете. Однако нетрудно заметить, что последняя четная ячейка уже содержит сумму элементов левее нее, так что можно обойтись без дополнительного хранилища.

Линейный алгоритм:

def FF(n):
    a = [1]*(n+1)
    for i in range(3, n+1):
        if i%2:
            a[i] = a[i-1]-a[i-2]
        else:
            a[i] = a[i-1] + 2 * a[i-2]
    return a[n]

Answer 2

Т.к. в коде почти все значения вычисляются по многу раз, например, F(18) будет вычисляться 4 раза (если я не ошибся), и чем ниже аргумент функции F(), тем больше раз он будет вычисляться снова и снова, причем количество этих раз растет в геометрической прогрессии. Т.е. каждый их этих 4 раз влечет за собой десятки и сотни вычислений F() для чисел меньше 18. Поэтому нужно использовать мемоизацию, т.е. сохранять значения F() для каждого числа в список или словарь и брать потом сразу готовое, чтобы не вычислять по сотне раз одно и то же.

Answer 3

"Ленивый" вариант - добавить к функции кеширующий декоратор:

from functools import lru_cache

@lru_cache(None)
def F(n):
    ...

В этом случае F(1000) вычисляет за 100мс.

БЛОГ НА HUSL

Как модернизировать код, чтобы он не считал долго?

Ответы (3 шт):