如何找到一个数学方法来解决这个大值递归问题?

2024-03-29 02:27:56 发布

您现在位置:Python中文网/ 问答频道 /正文

带有递归函数的python代码。要计算这一点,PC会减慢速度。那么有没有一种简单的方法来找到这个python代码的答案呢?你知道吗

def rec(n):
    if n<1:
      return 1
    return rec(n//4)+rec(n//2)
print(rec(12345678987654321))

Tags: 方法答案代码returnifdef速度print
3条回答

函数返回第X个斐波那契数,其中X=log(n)+3。因为获得第X个Fibonacci数有一个O(X)性能,我们提供log(n)。这将提供O(log(n))性能,与记忆版本类似,但使用更简单的操作。所以函数应该运行得更快:

def fibo(n):
    a,b=1,1
    for _ in range(n-1): a,b = b,a+b
    return a

from math import log
def rec2(n) : 
    return fibo(int(log(n,2)+3))

print(rec2(12345678987654321)) # 225851433717

对于n=12345678987654321,它的执行速度大约是原始rec()函数的记忆版本的5倍。你知道吗

您还可以通过在每次迭代中不进行两次递归调用来获得性能增益。这将需要返回两个值,以便n//4(下一次迭代)可以被带到调用函数。你知道吗

def rec3(n):
    if n<1 :return 1,1
    a,b = rec3(n//2)
    return a+b,a 

rec3(12345678987654321)[0] # 225851433717

这比斐波那契方法慢,但仍然比记忆的原始方法快。你知道吗

1000次运行的测试结果(2.9 GHz Intel Core i9笔记本电脑):

rec(12345678987654321)     0.027 sec (Memoized on lru_cache, cleared each run)
rec2(12345678987654321)    0.005 sec (Fibonacci)
                           0.002 sec (fastFibo, see EDIT below)
rec3(12345678987654321)[0] 0.013 sec (Single Recursion)

编辑 如果要使Fibonacci方法更快(2x),可以使用此非迭代fastFibo()函数获取第n个Fibonacci数:

from math import sqrt

sqrt5 = sqrt(5)
golden_ratio = (1 + sqrt5) / 2

def fastFibo(n):
    approx = (golden_ratio**n - (1 - golden_ratio)**n) / sqrt5
    return int(round(approx))

这将允许您将函数编写为纯数学公式,没有迭代/递归,性能为O(1):

from math import log,sqrt
sqrt5 = sqrt(5)
golden_ratio = (1 + sqrt5) / 2
def rec4(n):
    n = int(log(n,2)+3)
    result = (golden_ratio**n - (1 - golden_ratio)**n) / sqrt5
    return int(round(result))

注意fastFibo()是一个近似值(好到70),所以这个rec4()解在n=2^67(147573952589676412928)

您可以使用lru_cache模块中的functools
https://docs.python.org/3/library/functools.html
如文件所述

Decorator to wrap a function with a memoizing callable that saves up to the maxsize most recent calls. It can save time when an expensive or I/O bound function is periodically called with the same arguments

如果将maxsize设置为None,则缓存将不受限制地增长。你知道吗

from functools import lru_cache

@lru_cache(maxsize = None)
def rec(n):
    if n < 1:
        return  1
    return rec(n // 4) + rec(n // 2)
print(rec(12345678987654321))

时间度量:

times = timeit.timeit(setup = 'from __main__ import rec',
stmt = 'print(rec(12345678987654321))', number = 1)

lru_cache

225851433717
0.00023956200311658904

没有lru_cache

More than 2 minutes

您可以研究如何扩展递归关系,也可以简单地使用memoization

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper

@memoize
def rec(n):
    if n<1:
      return 1
    return rec(n//4)+rec(n//2)

print(rec(12345678987654321))

上面的步骤在我的电脑上大约需要30毫秒,包括启动Python解释器所需的时间。你知道吗

通过不多次计算rec()相同值的n(原始版本反复重复相同的计算,浪费了大量CPU周期),memoization加快了速度。你知道吗

相关问题 更多 >