Python:是否有可能使这个尾递归阶乘更快？

Question

我正在为涉及组合学的应用程序制作实用程序类。

我做了两个尾递归的阶乘函数。第二个在计算组合数时提高了很多性能(我认为在英语中它们被称为n choose k，我使用 C(n,k) 表示法并制作了一个 nCk 函数)。

所以我测量了时间，并实现了我的目标。我的新组合函数比新函数快得多。

但是当谈到阶乘函数时，我发现我的新阶乘函数 'f' 比第一个 'fact' 慢一点。

有没有办法让这个“f”函数在性能上和“fact”一样好？

您可以在底部看到我机器中的主要测试执行和结果。

源代码

class Utils(object):
    """
    Class with useful functions
    """

    @staticmethod
    def fact(i, _current_factorial=1):
        '''
        The factorial function
        :param i: the number for calculating the factorial
        :param _current_factorial: for internal use, it is the acumulated product
        :return the result
        '''
        if i == 1:
            return _current_factorial
        else:
            return Utils.fact(i - 1, _current_factorial * i)

    @staticmethod
    def f(i, k=None, _current_factorial=1):
        '''
        The factorial function
        If k is given, it calculates the factorial but only with
        the k-th first numbers.
        Example:
            f(6) = 6 · 5 · 4 · 3 · 2 · 1
            f(6, 2) = 6 · 5
            f(6, 3) = 6 · 5 · 4
            f(9, 4) = 9 · 8 · 7 · 6
        :param i: the number for calculating the factorial
        :param k: optional, the number for calculating the factorial
        :param _current_factorial: for internal use, it is the acumulated product
        :return the result
        '''
        if k is None:
            k = i
        if i == 1 or k == 0:
            return _current_factorial
        else:
            return Utils.f(i - 1, k - 1, _current_factorial=_current_factorial * i)

    @staticmethod
    def C(n, k=1):
        '''
        Statistical combinations 'nCk'
        :param n: number of elements to be combined
        :param k: number of elements to be taken for each combination
        :return: the 'n choose k' mathematical result
        '''
        return Utils.fact(n) / (Utils.fact(k) * Utils.fact(n - k))

    @staticmethod
    def nCk(n, k=1):
        '''
        Statistical combinations 'nCk'
        :param n: number of elements to be combined
        :param k: number of elements to be taken for each combination
        :return: the 'n choose k' mathematical result
        '''
        return Utils.f(n, k) / Utils.f(k)



if __name__ == "__main__":
    NUM_TEST_ITERATIONS = 7500
    MAX_NUMBER_WITHOUT_STACKOVERFLOW = 998

    import time

    start = time.process_time()
    for i in range(NUM_TEST_ITERATIONS): Utils.f(MAX_NUMBER_WITHOUT_STACKOVERFLOW)
    elapsed = time.process_time() - start
    print('Function {} took {} to get result {}'.format('f', elapsed, Utils.f(MAX_NUMBER_WITHOUT_STACKOVERFLOW)))

    start = time.process_time()
    for i in range(NUM_TEST_ITERATIONS): Utils.fact(MAX_NUMBER_WITHOUT_STACKOVERFLOW)
    elapsed = time.process_time() - start
    print('Function {} took {} to get result {}'.format('fact', elapsed, Utils.fact(MAX_NUMBER_WITHOUT_STACKOVERFLOW)))

    start = time.process_time()
    for i in range(NUM_TEST_ITERATIONS): Utils.nCk(997, 4)
    elapsed = time.process_time() - start
    print('Function {} took {} to get result {}'.format('nCk', elapsed, Utils.nCk(997, 4)))

    start = time.process_time()
    for i in range(NUM_TEST_ITERATIONS): Utils.C(997, 4)
    elapsed = time.process_time() - start
    print('Function {} took {} to get result {}'.format('C', elapsed, Utils.C(997, 4)))

在屏幕上:

Function f    took 7.854962716 to get result 402790050127220994538240674597601587306681545756471103647447357787726238637266286878923131618587992793273261872069265323955622495490298857759082912582527118115540044131204964883707335062250983503282788739735011132006982444941985587005283378024520811868262149587473961298417598644470253901751728741217850740576532267700213398722681144219777186300562980454804151705133780356968636433830499319610818197341194914502752560687555393768328059805942027406941465687273867068997087966263572003396240643925156715326363340141498803019187935545221092440752778256846166934103235684110346477890399179387387649332483510852680658363147783651821986351375529220618900164975188281042287183543472177292257232652561904125692525097177999332518635447000616452999984030739715318219169707323799647375797687367013258203364129482891089991376819307292252205524626349705261864003453853589870620758596211518646408335184218571196396412300835983314926628732700876798309217005024417595709904449706930796337798861753941902125964936412501007284147114260935633196107341423863071231385166055949914432695939611227990169338248027939843597628903525815803809004448863145157344706452445088044626373001304259830129153477630812429640105937974761667785045203987508259776060285826091261745049275419393680613675366264232715305430889216384611069135662432391043725998805881663054913091981633842006354699525518784828195856033032645477338126512662942408363494651203239333321502114252811411713148843370594801145777575035630312885989779863888320759224882127141544366251503974910100721650673810303577074640154112833393047276025799811224571534249672518380758145683914398263952929391318702517417558325636082722982882372594816582486826728614633199726211273072775131325222240100140952842572490801822994224069971613534603487874996852498623584383106014533830650022411053668508165547838962087111297947300444414551980512439088964301520461155436870989509667681805149977993044444138428582065142787356455528681114392680950815418208072393532616122339434437034424287842119316058881129887474239992336556764337968538036861949918847009763612475872782742568849805927378373244946190707168428807837146267156243185213724364546701100557714520462335084082176431173346929330394071476071813598759588818954312394234331327700224455015871775476100371615031940945098788894828812648426365776746774528000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Function fact took 6.757415364 to get result 402790050127220994538240674597601587306681545756471103647447357787726238637266286878923131618587992793273261872069265323955622495490298857759082912582527118115540044131204964883707335062250983503282788739735011132006982444941985587005283378024520811868262149587473961298417598644470253901751728741217850740576532267700213398722681144219777186300562980454804151705133780356968636433830499319610818197341194914502752560687555393768328059805942027406941465687273867068997087966263572003396240643925156715326363340141498803019187935545221092440752778256846166934103235684110346477890399179387387649332483510852680658363147783651821986351375529220618900164975188281042287183543472177292257232652561904125692525097177999332518635447000616452999984030739715318219169707323799647375797687367013258203364129482891089991376819307292252205524626349705261864003453853589870620758596211518646408335184218571196396412300835983314926628732700876798309217005024417595709904449706930796337798861753941902125964936412501007284147114260935633196107341423863071231385166055949914432695939611227990169338248027939843597628903525815803809004448863145157344706452445088044626373001304259830129153477630812429640105937974761667785045203987508259776060285826091261745049275419393680613675366264232715305430889216384611069135662432391043725998805881663054913091981633842006354699525518784828195856033032645477338126512662942408363494651203239333321502114252811411713148843370594801145777575035630312885989779863888320759224882127141544366251503974910100721650673810303577074640154112833393047276025799811224571534249672518380758145683914398263952929391318702517417558325636082722982882372594816582486826728614633199726211273072775131325222240100140952842572490801822994224069971613534603487874996852498623584383106014533830650022411053668508165547838962087111297947300444414551980512439088964301520461155436870989509667681805149977993044444138428582065142787356455528681114392680950815418208072393532616122339434437034424287842119316058881129887474239992336556764337968538036861949918847009763612475872782742568849805927378373244946190707168428807837146267156243185213724364546701100557714520462335084082176431173346929330394071476071813598759588818954312394234331327700224455015871775476100371615031940945098788894828812648426365776746774528000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Function nCk took 0.021283503999999454 to get result 40921610765.0
Function C   took 13.261998684000002   to get result 40921610765.0

Answer 1

我最终删除了类代码并使用了 math.factorial，但我用“fact”名称导入了它。

我还在源代码文档中解释的公式中使用了快捷方式

这比原来的好多了。谢谢

源代码(为了简洁省略了主要部分):

# Importing math.factorial with shorter name
from math import factorial as fact
from functools import reduce
from operator import mul


def C(n, k=1):
    '''
    Statistical combinations 'nCk'
    :param n: number of elements to be combined
    :param k: number of elements to be taken for each combination
    :return: the 'n choose k' mathematical result
    '''
    '''
        Original formula: fact(n) / (fact(k) * fact(n-k))

        Performance shortcut (about 40% faster): 
            1.- Calculates the numerator as the product over the first k-th elements of fact(n)
            Let's call this f'(n,k), we store it in fnkProduct variable
            Example:
                n = 6, k = 2 => f'(n,k) =   30 = 6 · 5
                n = 6, k = 3 => f'(n,k) =  120 = 6 · 5 · 4
                n = 9, k = 4 => f'(n,k) = 3024 = 9 · 8 · 7 · 6
            2.- Then divide it by fact(k)

        New formula: f'(n,k) / fact(k)

        '''
    # C(n,k) == C(n,n-k), but the second is best when k is much bigger
    k = n - k if k > (n // 2) else k
    fnkProduct = reduce(mul, range(n, n - k, -1), 1)
    return fnkProduct // fact(k)

在屏幕上(这是我在决定 1500 万次迭代之前所做的最后一次比较)

Function C took 0.01638609299999999 to get result 40921610765.0
Function nCk took 0.016534930000000003 to get result 40921610765.0