为什么以不同方式编写的相同函数会产生如此不同的结果时间?
Why does the same function written in different ways have such different results time?
我一直在玩 wolfram 语言并注意到一件事:以不同方式编写的相同函数在时间方面有很大不同。
考虑这两个函数:
NthFibonacci[num_] :=
If [num == 0 || num == 1, Return[ 1],
Return[NthFibonacci[num - 1] + NthFibonacci[num - 2]]
]
Fibn[num_] := {
a = 1;
b = 1;
For[i = 0, i < num - 1, i++,
c = a + b;
a = b;
b = c;
];
Return [b];
}
NthFibonacci[30]
大约需要 5 秒来评估。
Fibn[900 000]
也需要大约 5 秒来评估。
内置的 Fibonacci[50 000 000]
也是如此
我实在想不通为什么三者之间的速度会有这么大的差异。理论上,递归应该或多或少等同于 for 循环。这是什么原因造成的?
这是因为你提供的递归版本做了很多很多的重复计算。构建函数调用树以了解我的意思。即使对于一个小到 4 的参数,也要查看生成了多少函数调用才能到达每个逻辑链的基本情况。
f(1)
/
f(2)
/ \
f(3) f(0)
/ \
/ f(1)
/
f(4)
\
\ f(1)
\ /
f(2)
\
f(0)
通过递归,函数调用的数量随参数 num
呈指数增长。
相比之下,您的循环版本在 num
中呈线性增长。在 n
比 2n 少 lot 之前,它不需要非常大的 n
值。
实现递归的方法有很多种;斐波那契函数就是一个很好的例子。正如 pjs 已经指出的那样,经典的双递归定义呈指数级增长。基数是
φ = (sqrt(5)+1) / 2 = 1.618+
您的 NthFibonacci 实现以这种方式工作。它是 φ^n 的阶数,意味着对于大的 n,调用 f(n+1) 需要 φ 次,只要 f(n).
更温和的方法在执行流中只计算每个函数值一次。它不是指数时间,而是线性时间,这意味着调用 f(2n) 的时间是 f(n) 的 2 倍。
还有其他方法。例如,动态规划 (DP) 保留先前结果的缓存。在 pjs f(4) 的情况下,DP 实现只会计算 f(2) 一次;第二次调用会看到第一次的结果在缓存中,return 结果而不是进一步调用 f(0) 和 f(1)。这趋向于线性时间。
也有创建检查点的实现,例如缓存 f(k) 和 f(k)+1,因为 k 可以被 1000 整除。这些实现通过起点不低于期望值太远来节省时间,给出他们是 998 次迭代的上限以找到所需的值。
最终,最快的实现使用直接计算(至少对于较大的数字)并在恒定时间内工作。
φ = (1+sqrt(5)) / 2 = 1.618...
ψ = (1-sqrt(5)) / 2 = -.618...
f(n) = (φ^n - ψ^n) / sqrt(5)
@pjs 指出的问题可以在一定程度上通过让递归函数记住先前的值来解决。 (消除 If
也有帮助)
Clear[NthFibonacci]
NthFibonacci[0] = 1
NthFibonacci[1] = 1
NthFibonacci[num_] :=
NthFibonacci[num] = NthFibonacci[num - 1] + NthFibonacci[num - 2]
NthFibonacci[300] // AbsoluteTiming
{0.00201479, 3.59 10^62}
同时清理你的循环版本(你几乎不应该在 mathematica 中使用 Return
):
Fibn[num_] := Module[{a = 1, b = 1,c},
Do[c = a + b; a = b; b = c, {num - 1}]; b]
Fibn[300] // AbsoluteTiming
{0.000522175 ,3.59 10^62}
你看到递归形式比较慢,但并不可怕。 (注意递归形式也达到了 1000 左右的深度限制)
我一直在玩 wolfram 语言并注意到一件事:以不同方式编写的相同函数在时间方面有很大不同。
考虑这两个函数:
NthFibonacci[num_] :=
If [num == 0 || num == 1, Return[ 1],
Return[NthFibonacci[num - 1] + NthFibonacci[num - 2]]
]
Fibn[num_] := {
a = 1;
b = 1;
For[i = 0, i < num - 1, i++,
c = a + b;
a = b;
b = c;
];
Return [b];
}
NthFibonacci[30]
大约需要 5 秒来评估。
Fibn[900 000]
也需要大约 5 秒来评估。
内置的 Fibonacci[50 000 000]
我实在想不通为什么三者之间的速度会有这么大的差异。理论上,递归应该或多或少等同于 for 循环。这是什么原因造成的?
这是因为你提供的递归版本做了很多很多的重复计算。构建函数调用树以了解我的意思。即使对于一个小到 4 的参数,也要查看生成了多少函数调用才能到达每个逻辑链的基本情况。
f(1)
/
f(2)
/ \
f(3) f(0)
/ \
/ f(1)
/
f(4)
\
\ f(1)
\ /
f(2)
\
f(0)
通过递归,函数调用的数量随参数 num
呈指数增长。
相比之下,您的循环版本在 num
中呈线性增长。在 n
比 2n 少 lot 之前,它不需要非常大的 n
值。
实现递归的方法有很多种;斐波那契函数就是一个很好的例子。正如 pjs 已经指出的那样,经典的双递归定义呈指数级增长。基数是
φ = (sqrt(5)+1) / 2 = 1.618+
您的 NthFibonacci 实现以这种方式工作。它是 φ^n 的阶数,意味着对于大的 n,调用 f(n+1) 需要 φ 次,只要 f(n).
更温和的方法在执行流中只计算每个函数值一次。它不是指数时间,而是线性时间,这意味着调用 f(2n) 的时间是 f(n) 的 2 倍。
还有其他方法。例如,动态规划 (DP) 保留先前结果的缓存。在 pjs f(4) 的情况下,DP 实现只会计算 f(2) 一次;第二次调用会看到第一次的结果在缓存中,return 结果而不是进一步调用 f(0) 和 f(1)。这趋向于线性时间。
也有创建检查点的实现,例如缓存 f(k) 和 f(k)+1,因为 k 可以被 1000 整除。这些实现通过起点不低于期望值太远来节省时间,给出他们是 998 次迭代的上限以找到所需的值。
最终,最快的实现使用直接计算(至少对于较大的数字)并在恒定时间内工作。
φ = (1+sqrt(5)) / 2 = 1.618...
ψ = (1-sqrt(5)) / 2 = -.618...
f(n) = (φ^n - ψ^n) / sqrt(5)
@pjs 指出的问题可以在一定程度上通过让递归函数记住先前的值来解决。 (消除 If
也有帮助)
Clear[NthFibonacci]
NthFibonacci[0] = 1
NthFibonacci[1] = 1
NthFibonacci[num_] :=
NthFibonacci[num] = NthFibonacci[num - 1] + NthFibonacci[num - 2]
NthFibonacci[300] // AbsoluteTiming
{0.00201479, 3.59 10^62}
同时清理你的循环版本(你几乎不应该在 mathematica 中使用 Return
):
Fibn[num_] := Module[{a = 1, b = 1,c},
Do[c = a + b; a = b; b = c, {num - 1}]; b]
Fibn[300] // AbsoluteTiming
{0.000522175 ,3.59 10^62}
你看到递归形式比较慢,但并不可怕。 (注意递归形式也达到了 1000 左右的深度限制)