Python 中的递归函数调用如何能够在空字典中找到键? [英] how are Recursive function calls in Python are able to find keys in an empty dictionary?

问题描述

所以在玩 memory_profiler 模块时发现了一些奇怪的东西.我正在研究一个用于使用递归查找 nCr 组合的函数.我制作了我的功能的 2 个版本:

版本 1:

<块引用>

@profiledef c( n , r , 备忘录 ={} ):对 = (n,r)如果在备忘录中配对:返回备忘录[对]如果 r==1 :返回 n如果 n-r <:返回 c(n , n -r )如果 r==0 或 r==n:返回 1返回 c( n-1 , r-1 ) + c(n-1, r )打印( c( 20 , 10 ) )

第 2 版:

<块引用>

@profiledef c( n , r , memo ={} ):

 pair = (n,r)如果在备忘录中配对:返回备忘录[对]如果 r==1 :返回 n如果 n-r <:返回 c(n , n -r )如果 r==0 或 r==n:返回 1备忘录[对] = c( n-1 , r-1 ) + c(n-1, r )返回备忘录[对]打印( c( 20 , 10 ) )

内存分析器:

1. 版本1:
2. ver 2 :

如您所见，除了函数的最后两行之外，版本 1 和版本 2 是相同的.但是在它们上运行 memory_profiler 它们在性能上有很大的不同.最让我困惑的是，虽然我忘记在函数调用中传递备忘录，但它仍然导致如此巨大的性能提升.

每个函数调用都会为该函数生成一个新的空备忘录.那么为什么版本 1 中的第 8 行评估为 False 并且无法返回，而版本 2 中的同一行评估为 True 并返回 36 次.当我试图在空字典中查找键时，它们实际上不应该都是假的吗?难道性能上几乎没有可观察到的差异吗?

解决方案

你的假设

<块引用>

每个函数调用都会为该函数生成一个新的空备忘录.

不正确.与 JavaScript 不同，在 Python 中，默认参数值在定义时评估一次.如果 c 函数在没有 memo 参数的情况下被调用，则在定义时构造的 dict 实例每次都将用作其值.在构造时它是空的，但随后的调用可能会改变它.请注意以下事项:

defaccumulate(a, b=[]):b.append(a)打印(b)累积(1)累积('富')累积(无)

上面会打印[1]，然后是[1, 'foo']，然后是[1, 'foo', None].

使用默认参数值进行记忆是一个非常糟糕的主意.它不仅相当晦涩难懂，而且还允许调用者通过为 memo 参数实际提供一个值来破坏函数.一个更好的主意是使用全局/非本地绑定，或装饰器，例如 functools.cache 或 functools.lru_cache.

So was playing around with memory_profiler module and noticed something weird. I was working on a function used to find nCr combinations using recursion. I made 2 version of of my function :

ver 1:

@profile
def c( n , r , memo ={} ):

    pair = (n,r)
    if pair in memo:
        return memo[pair]

    if r==1 :
        return n
    if n-r < r :
        return c(n , n -r )
    
    if r==0 or r==n:
        return 1

    return  c( n-1 , r-1   ) + c(n-1, r )
    
print( c( 20 , 10 ) )

ver 2:

@profile def c( n , r , memo ={} ):

    pair = (n,r)
    if pair in memo:
        return memo[pair]

    if r==1 :
        return n
    if n-r < r :
        return c(n , n -r )
    
    if r==0 or r==n:
        return 1

    memo[pair] = c( n-1 , r-1   ) + c(n-1, r )
    return memo[pair]

print( c( 20 , 10 ) )

memory_profiler :

1. ver 1 :
2. ver 2 :

As you can see ver 1 and ver 2 are the same except for the last 2 lines of the function. But running memory_profiler on them they have great difference in performance. The thing I'm most puzzled by is although I forgot to pass memo in the function call it still results in such great performance improvement.

Each function call results in a new empty memo dict for that function. So why does line 8 in version 1 evaluates as False and fails to return whereas the same line in ver 2 evaluates True and returns 36 times. Shouldn't they both realistically be false as I'm trying to find key in an empty dictionary ? Shouldn't there be virtually no observable difference in performance ?

解决方案

Your assumption that

Each function call results in a new empty memo dict for that function.

is incorrect. Unlike in JavaScript, in Python default parameter values are evaluated at definition time, once. If the c function is called without a value for the memo parameter, the instance of the dict constructed at definition time will be used as its value each time. At construction time it is empty, but subsequent invocations may mutate it. Observe the following:

def accumulate(a, b=[]):
    b.append(a)
    print(b)

accumulate(1)
accumulate('foo')
accumulate(None)

The above will print [1], then [1, 'foo'], then [1, 'foo', None].

Using default parameter values for memoisation is a pretty bad idea. Not only is it rather obscure and confusing, it also allows the caller to break the function by actually providing a value for the memo parameter. A better idea would be to use a global/non-local binding, or a decorator such as functools.cache or functools.lru_cache.

这篇关于Python 中的递归函数调用如何能够在空字典中找到键?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！