Не понимаю, почему программа «тяжелая»?

Question

[1vopros]

def F(n):
    if n <= 1:
        return n
    if n>1: 
        return F(n-1)+F(n-2)

i = 0
for k in range (0,40000000-1):
    if F(k)%2==0:
        i += F(k)
print(i)

Почему данная программа "съедает" много памяти? Подобные через while работают в разы быстрее...

Comments

[Vindicar]

Ну для начала...

if F(k)%2==0:  # раз вызов
    i += F(k)  # два вызов

ты себе на ровном месте удвоил нагрузку.

[1vopros]

Vindicar, он и без этого не грузил, поэтому я думал что так наоборот облегчаю задачу

Видимо нет

Answer 1

[Максим Припадчев]

Потому что вызовов рекурсивной функции происходит больше раз чем ты ожидаешь, и растет все это дело не линейно с увеличением n. Нужно оптимизировать рекурсивную функцию.

from functools import lru_cache
@lru_cache
def F(n):
    print(n)
    if n <= 1:
        return n
    if n>1: 
        return F(n-1)+F(n-2)
F(8)

Вот твоя функция в точности, я добавил кеширование результатов, и print(n). Запусти с ним и без него и посмотри сколько лишних вызовов происходит. Если владеешь английским вот хорошая статья почитай как сделать своими руками, без встроенного декоратора, различные стратегии и т.д. https://realpython.com/lru-cache-python/

Comments

[1vopros]

Спасибо

Answer 2

[Alexandroppolus]

40000000 чисел Фибоначчи - это лютая вещь со всех сторон. Даже если ты врубишь мемоизацию, как посоветовал Максим Припадчев , то там дохрена вычислений, потому что числа будут длиной в миллионы цифр.

Мы суммируем только четные числа Фибоначчи.
Легко заметить, что F(n) четное, только если n делится на 3, т.е. n = 3m.
То есть тебе нужна сумма F(3*m) для всех m от 0 до floor((40000000-2) / 3) включительно, если правильно понимаю этот ваш range.

я тут пояндексил и промыслил формулы:
1) F(3*n) = F(n+1)^3 + F(n)^3 + F(n-1)^3 (из википедии)
2) sum[0...N] F(i)^3 = (1/2)*(F(n)*F(n+1)^2 + (-1)^(n-1)*F(n-1) + 1) отсюда

сумму F(3*n) можно выразить через сумму F(n)^3 и потом применить формулу (2)

в итоге получается

sum[0...N] F(3*i) = (1/2)*(F(n)*F(n+1)^2 + (-1)^(n-1)*F(n-1) + 1) - 1 + F(n)^3 + F(n+1)^3

для этого выражения нам нужны F(n), F(n+1) и F(n-1) = F(n+1) - F(n)

F(n) и F(n+1) вычисляем методом "fast doubling", который делает O(ln(n)) действий вместо O(n) стандартного способа. Ускорение знатное.

Итого:

const fib = (n, a = []) => {
    if (n < 1) {
        a[0] = 0n;
        a[1] = 1n;
    } else {
        const m = Math.floor(n/2);
        fib(m, a);
        const x = a[0] * (2n * a[1] - a[0]);
        const y = a[0] * a[0] + a[1] * a[1];
        if (n % 2) {
            a[0] = y;
            a[1] = x + y;
        } else {
            a[0] = x;
            a[1] = y;
        }
        
    }
    return a;
}

const sumFib3n = (n) => {
    if (n < 1) { return 0n; }

    const [fn, fnp1] = fib(n); // fn = fib(n), fnp1 = fib(n+1), 
    const fnm1 = fnp1 - fn;  // fnm1 = fib(n-1), 
    const sgn = n % 2 ? 1n : -1n;
    const sumPow3 = (fn * fnp1 * fnp1 + sgn * fnm1 + 1n) / 2n;
    
    return sumPow3 - 1n + fn * fn * fn + fnp1 * fnp1 * fnp1;
}

console.log(sumFib3n(Math.floor((40000000 - 2)/3)));

Comments

[Александр]

Это же не пайтон?!)

[Alexandroppolus]

Александр, да, это JS (в моей ленте это вывалилось по тегу "рекурсия")

ради интереса попробовал переложить на пайтон, и даже получилось(!)

кодъ

def fib(n, a):
    if (n < 1):
        a[0] = 0
        a[1] = 1
    else:
        m = n // 2
        fib(m, a)
        x = a[0] * (2 * a[1] - a[0])
        y = a[0] * a[0] + a[1] * a[1]
        if (n % 2):
            a[0] = y
            a[1] = x + y
        else:
            a[0] = x
            a[1] = y
    return a

def sumFib3n(n):
    if (n < 1):
        return 0

    arr = [0, 0]
    [fn, fnp1] = fib(n, arr)
    fnm1 = fnp1 - fn
    sgn = 1 if n % 2 else -1
    sumPow3 = (fn * fnp1 * fnp1 + sgn * fnm1 + 1) // 2
    
    return sumPow3 - 1 + fn * fn * fn + fnp1 * fnp1 * fnp1

print(sumFib3n((40000000 - 2)//3))