Как сделать так, чтобы эта функция работала быстрее?

Question

# a very ineffecient way to calculate a factorial 

from functools import lru_cache 

def partition(k, lmax=None):
    if lmax is None:
        lmax = k
    if k == 0:
        yield []
    for i in range(min(k, lmax), 0, -1):
        for p in partition(k - i, i):
            p.append(i)
            yield p
            
@lru_cache(maxsize=48000)                                          
def d(p):
    if not p:
        return 1
    p = list(p)
    if p[0] == 1:
        res = d(tuple(p[1:]))
    else:
        p[0] -= 1
        res = d(tuple(p))
        p[0] += 1
    for i in range(1, len(p)):
        if p[i - 1] < p[i]:
            p[i] -= 1
            res += d(tuple(p))
            p[i] += 1
    return res
    

def Q(n, r, s):
    if r > s:
        r, s = s, r 
    if (s - r) % n != 0:
        return 0
    qq = (s - r) // n
    sm = 0
    for p in partition(r):
        if len(p) <= n:
            pp = tuple(p)
            p2 = tuple(x + qq for x in p)
            sm += d(pp) * d(p2)
    return sm
    
print(Q(5,100,105))

Answer 1

Поставьте перед каждой вашей функцией такой же декоратор, который уже имеется на одной из функций:

@lru_cache(maxsize=48000)
def ...

И тогда код отработает моментально. Результат:

3533343320884635898708258511468514257188006702535057407220

А в целом не очень понятно, что делают эти функции и что вы вообще хотите от этого кода.

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

БЛОГ НА HUSL

Как сделать так, чтобы эта функция работала быстрее?

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