相关疑难解决方法(0)

任何修补Python足够长的人都被以下问题咬伤(或撕成碎片):

def foo(a=[]):
    a.append(5)
    return a

Python新手希望这个函数总能返回一个只包含一个元素的列表:[5].结果却非常不同,而且非常惊人(对于新手来说):

>>> foo()
[5]
>>> foo()
[5, 5]
>>> foo()
[5, 5, 5]
>>> foo()
[5, 5, 5, 5]
>>> foo()

我的一位经理曾经第一次遇到这个功能,并称其为该语言的"戏剧性设计缺陷".我回答说这个行为有一个潜在的解释,如果你不理解内部,那确实非常令人费解和意想不到.但是,我无法回答(对自己)以下问题:在函数定义中绑定默认参数的原因是什么,而不是在函数执行时？我怀疑经验丰富的行为有实际用途(谁真的在C中使用静态变量,没有繁殖错误？)

编辑:

巴泽克提出了一个有趣的例子.再加上你的大部分评论和特别是Utaal,我进一步阐述了:

>>> def a():
...     print("a executed")
...     return []
... 
>>>            
>>> def b(x=a()):
...     x.append(5)
...     print(x)
... 
a executed
>>> b()
[5]
>>> b()
[5, 5]

对我而言,似乎设计决策是相对于放置参数范围的位置:在函数内部还是"与它一起"？

在函数内部进行绑定意味着在调用函数时x有效地绑定到指定的默认值,而不是定义,这会产生一个深层次的缺陷:def在某种意义上,该行将是"混合"的(部分绑定)函数对象)将在定义时发生,并在函数调用时发生部分(默认参数的赋值).

实际行为更加一致:执行该行时,该行的所有内容都会得到评估,这意味着在函数定义中.

假设我们要计算一些斐波那契数，以 997 为模。

因为n=500在 C++ 中我们可以运行

#include <iostream>
#include <array>

std::array<int, 2> fib(unsigned n) {
    if (!n)
        return {1, 1};
    auto x = fib(n - 1);
    return {(x[0] + x[1]) % 997, (x[0] + 2 * x[1]) % 997};
}

int main() {
    std::cout << fib(500)[0];
}

在 Python 中

def fib(n):
    if n==1:
        return (1, 2)
    x=fib(n-1)
    return ((x[0]+x[1]) % 997, (x[0]+2*x[1]) % 997)

if __name__=='__main__':
    print(fib(500)[0])

两者都可以毫无问题地找到答案 996。我们采用模数来保持合理的输出大小，并使用对来避免指数分支。

对于n=5000，C++ 代码输出 783，但 Python 会抱怨

RecursionError: …

有许多计算任意n的F(n)的方法,其中许多方法具有很大的运行时和内存使用率.

但是,假设我想问相反的问题:

给定F(n)n> 2,n是什么？

(由于F(1)= F(2)= 1并且没有明确的逆,因此n> 2限制在那里.

解决这个问题最有效的方法是什么？通过枚举斐波纳契数并在达到目标数时停止,可以很容易地在线性时间内完成此操作,但有没有比这更快的方法呢？

编辑:目前,这里发布的最佳解决方案使用O(log n)内存在O(log n)时间内运行,假设数学运算在O(1)中运行并且机器字可以在O(1)空间中保存任何数字.我很好奇是否可以降低内存要求,因为你可以使用O(1)空间计算斐波纳契数.