The following takes about 30 seconds to run whereas I would expect it to be nearly instant. Is there a problem with my code?
下面的程序运行大约需要30秒，而我希望它几乎是即时的。我的代码有问题吗?
x <- fibonacci(35);
fibonacci <- function(seq) {
if (seq == 1) return(1);
if (seq == 2) return(2);
return (fibonacci(seq - 1) + fibonacci(seq - 2));
}
7 个解决方案
#1
26
Patrick Burns gives an example in R Inferno of one way to do memoization in R with local() and <<-. In fact, it's a fibonacci:
Patrick Burns在R Inferno中给出了一个用local()和<-进行R中的记忆处理的例子。事实上，这是斐波那契:
fibonacci <- local({
memo <- c(1, 1, rep(NA, 100))
f <- function(x) {
if(x == 0) return(0)
if(x < 0) return(NA)
if(x > length(memo))
stop("’x’ too big for implementation")
if(!is.na(memo[x])) return(memo[x])
ans <- f(x-2) + f(x-1)
memo[x] <<- ans
ans
}
})
#2
24
That just provided a nice opportunity to plug Rcpp which allows us to add C++ functions easily to R.
这为Rcpp提供了一个很好的机会，Rcpp允许我们轻松地向R添加c++函数。
So after fixing your code slightly, and using the packages inline (to easily compile, load and link short code snippets as dynamically loadable functions) as well as rbenchmark to time and compare functions, we end up with a stunning 700-fold increase in performance:
因此，在稍微修改代码之后，使用内联的包(方便编译、加载和链接短代码片段作为动态可加载的函数)以及rbenchmark和比较函数之后，我们的性能得到了惊人的700倍的提高:
R> print(res)
test replications elapsed relative user.self sys.self
2 fibRcpp(N) 1 0.092 1.000 0.10 0
1 fibR(N) 1 65.693 714.054 65.66 0
R>
Here we see elapsed times of 92 milliseonds versus 65 seconds, for a relative ratio of 714. But by now everybody else told you not to do this directly in R.... The code is below.
在这里，我们看到92毫秒的间隔时间和65秒的间隔时间，相对比是714秒。但是现在其他人告诉你不要做这个直接在R ....下面的代码。
## inline to compile, load and link the C++ code
require(inline)
## we need a pure C/C++ function as the generated function
## will have a random identifier at the C++ level preventing
## us from direct recursive calls
incltxt <- '
int fibonacci(const int x) {
if (x == 0) return(0);
if (x == 1) return(1);
return (fibonacci(x - 1)) + fibonacci(x - 2);
}'
## now use the snipped above as well as one argument conversion
## in as well as out to provide Fibonacci numbers via C++
fibRcpp <- cxxfunction(signature(xs="int"),
plugin="Rcpp",
incl=incltxt,
body='
int x = Rcpp::as<int>(xs);
return Rcpp::wrap( fibonacci(x) );
')
## for comparison, the original (but repaired with 0/1 offsets)
fibR <- function(seq) {
if (seq == 0) return(0);
if (seq == 1) return(1);
return (fibR(seq - 1) + fibR(seq - 2));
}
## load rbenchmark to compare
library(rbenchmark)
N <- 35 ## same parameter as original post
res <- benchmark(fibR(N),
fibRcpp(N),
columns=c("test", "replications", "elapsed",
"relative", "user.self", "sys.self"),
order="relative",
replications=1)
print(res) ## show result
And for completeness, the functions also produce the correct output:
为了完整性，函数还生成正确的输出:
R> sapply(1:10, fibR)
[1] 1 1 2 3 5 8 13 21 34 55
R> sapply(1:10, fibRcpp)
[1] 1 1 2 3 5 8 13 21 34 55
R>
#3
14
Because you are using one of the worst algorithms in the world!
因为你正在使用世界上最糟糕的算法之一!
Complexity of which is O(fibonacci(n)) = O((golden ratio)^n) and golden ratio is 1.6180339887498948482…
复杂度是O(斐波纳契(n))= O((黄金比例)^ n)和黄金比例是1.6180339887498948482……
#4
14
:-) because you use exponential algorithm!!! So for fibonacci number N it has to call the function 2^N times, which 2^35, which is heck of a number.... :-)
因为你使用指数算法!!所以对于斐波纳契数N它必须调用这个函数2 ^ N次,2 ^ 35,....见鬼的号码是:-)
Use linear algorithm:
使用线性算法:
fib = function (x)
{
if (x == 0)
return (0)
n1 = 0
n2 = 1
for (i in 1:(x-1)) {
sum = n1 + n2
n1 = n2
n2 = sum
}
n2
}
Sorry, edit: the complexity of the exponential recursive algorithm is not O(2^N) but O(fib(N)), as Martinho Fernandes greatly joked :-) Really a good note :-)
对不起,编辑:指数递归算法的复杂性不是O(2 ^ N),但O(fib(N)),费尔南德斯Martinho极大地开玩笑说:-)一个非常好的注意:-)
#5
5
Because the memoise package was already mentioned here is a reference implementation:
因为前面已经提到了memoise包装，所以这里有一个参考实现:
fib <- function(n) {
if (n < 2) return(1)
fib(n - 2) + fib(n - 1)
}
system.time(fib(35))
## user system elapsed
## 36.10 0.02 36.16
library(memoise)
fib2 <- memoise(function(n) {
if (n < 2) return(1)
fib2(n - 2) + fib2(n - 1)
})
system.time(fib2(35))
## user system elapsed
## 0 0 0
Source: Wickham, H.: Advanced R, p. 238.
资料来源:韦翰,H。:高级R，第238页。
In general memoization in computer science means that you save the results of a function so that when you call it again with the same arguments it returns the saved value.
一般来说，计算机科学中的记忆化意味着你保存一个函数的结果，这样当你用相同的参数再次调用它时，它会返回保存的值。
#6
4
A recursive implementation with linear cost:
线性成本的递归实现:
fib3 <- function(n){
fib <- function(n, fibm1, fibm2){
if(n==1){return(fibm2)}
if(n==2){return(fibm1)}
if(n >2){
fib(n-1, fibm1+fibm2, fibm1)
}
}
fib(n, 1, 0)
}
Comparing with the recursive solution with exponential cost:
与指数代价递归解比较:
> system.time(fibonacci(35))
usuário sistema decorrido
14.629 0.017 14.644
> system.time(fib3(35))
usuário sistema decorrido
0.001 0.000 0.000
This solution can be vectorized with ifelse:
这个解决方案可以用ifelse向量化:
fib4 <- function(n){
fib <- function(n, fibm1, fibm2){
ifelse(n<=1, fibm2,
ifelse(n==2, fibm1,
Recall(n-1, fibm1+fibm2, fibm1)
))
}
fib(n, 1, 0)
}
fib4(1:30)
## [1] 0 1 1 2 3 5 8
## [8] 13 21 34 55 89 144 233
## [15] 377 610 987 1597 2584 4181 6765
## [22] 10946 17711 28657 46368 75025 121393 196418
## [29] 317811 514229
The only changes required are changing == to <= for the n==1 case, and changing each if block to the equivalent ifelse.
对于n== =1的情况，只需要更改== <= ==，并将每个if块更改为等效的ifelse。
#7
2
If you are truly looking to return Fibonacci numbers and aren't using this example to explore how recursion works then you can solve it non-recursively by using the following:
如果你真的想要返回斐波那契数，而不是用这个例子来探究递归是如何工作的，那么你可以用下面的方法来非递归地解决它:
fib = function(n) {round((1.61803398875^n+0.61803398875^n)/sqrt(5))}
#1
26
Patrick Burns gives an example in R Inferno of one way to do memoization in R with local() and <<-. In fact, it's a fibonacci:
Patrick Burns在R Inferno中给出了一个用local()和<-进行R中的记忆处理的例子。事实上，这是斐波那契:
fibonacci <- local({
memo <- c(1, 1, rep(NA, 100))
f <- function(x) {
if(x == 0) return(0)
if(x < 0) return(NA)
if(x > length(memo))
stop("’x’ too big for implementation")
if(!is.na(memo[x])) return(memo[x])
ans <- f(x-2) + f(x-1)
memo[x] <<- ans
ans
}
})
#2
24
That just provided a nice opportunity to plug Rcpp which allows us to add C++ functions easily to R.
这为Rcpp提供了一个很好的机会，Rcpp允许我们轻松地向R添加c++函数。
So after fixing your code slightly, and using the packages inline (to easily compile, load and link short code snippets as dynamically loadable functions) as well as rbenchmark to time and compare functions, we end up with a stunning 700-fold increase in performance:
因此，在稍微修改代码之后，使用内联的包(方便编译、加载和链接短代码片段作为动态可加载的函数)以及rbenchmark和比较函数之后，我们的性能得到了惊人的700倍的提高:
R> print(res)
test replications elapsed relative user.self sys.self
2 fibRcpp(N) 1 0.092 1.000 0.10 0
1 fibR(N) 1 65.693 714.054 65.66 0
R>
Here we see elapsed times of 92 milliseonds versus 65 seconds, for a relative ratio of 714. But by now everybody else told you not to do this directly in R.... The code is below.
在这里，我们看到92毫秒的间隔时间和65秒的间隔时间，相对比是714秒。但是现在其他人告诉你不要做这个直接在R ....下面的代码。
## inline to compile, load and link the C++ code
require(inline)
## we need a pure C/C++ function as the generated function
## will have a random identifier at the C++ level preventing
## us from direct recursive calls
incltxt <- '
int fibonacci(const int x) {
if (x == 0) return(0);
if (x == 1) return(1);
return (fibonacci(x - 1)) + fibonacci(x - 2);
}'
## now use the snipped above as well as one argument conversion
## in as well as out to provide Fibonacci numbers via C++
fibRcpp <- cxxfunction(signature(xs="int"),
plugin="Rcpp",
incl=incltxt,
body='
int x = Rcpp::as<int>(xs);
return Rcpp::wrap( fibonacci(x) );
')
## for comparison, the original (but repaired with 0/1 offsets)
fibR <- function(seq) {
if (seq == 0) return(0);
if (seq == 1) return(1);
return (fibR(seq - 1) + fibR(seq - 2));
}
## load rbenchmark to compare
library(rbenchmark)
N <- 35 ## same parameter as original post
res <- benchmark(fibR(N),
fibRcpp(N),
columns=c("test", "replications", "elapsed",
"relative", "user.self", "sys.self"),
order="relative",
replications=1)
print(res) ## show result
And for completeness, the functions also produce the correct output:
为了完整性，函数还生成正确的输出:
R> sapply(1:10, fibR)
[1] 1 1 2 3 5 8 13 21 34 55
R> sapply(1:10, fibRcpp)
[1] 1 1 2 3 5 8 13 21 34 55
R>
#3
14
Because you are using one of the worst algorithms in the world!
因为你正在使用世界上最糟糕的算法之一!
Complexity of which is O(fibonacci(n)) = O((golden ratio)^n) and golden ratio is 1.6180339887498948482…
复杂度是O(斐波纳契(n))= O((黄金比例)^ n)和黄金比例是1.6180339887498948482……
#4
14
:-) because you use exponential algorithm!!! So for fibonacci number N it has to call the function 2^N times, which 2^35, which is heck of a number.... :-)
因为你使用指数算法!!所以对于斐波纳契数N它必须调用这个函数2 ^ N次,2 ^ 35,....见鬼的号码是:-)
Use linear algorithm:
使用线性算法:
fib = function (x)
{
if (x == 0)
return (0)
n1 = 0
n2 = 1
for (i in 1:(x-1)) {
sum = n1 + n2
n1 = n2
n2 = sum
}
n2
}
Sorry, edit: the complexity of the exponential recursive algorithm is not O(2^N) but O(fib(N)), as Martinho Fernandes greatly joked :-) Really a good note :-)
对不起,编辑:指数递归算法的复杂性不是O(2 ^ N),但O(fib(N)),费尔南德斯Martinho极大地开玩笑说:-)一个非常好的注意:-)
#5
5
Because the memoise package was already mentioned here is a reference implementation:
因为前面已经提到了memoise包装，所以这里有一个参考实现:
fib <- function(n) {
if (n < 2) return(1)
fib(n - 2) + fib(n - 1)
}
system.time(fib(35))
## user system elapsed
## 36.10 0.02 36.16
library(memoise)
fib2 <- memoise(function(n) {
if (n < 2) return(1)
fib2(n - 2) + fib2(n - 1)
})
system.time(fib2(35))
## user system elapsed
## 0 0 0
Source: Wickham, H.: Advanced R, p. 238.
资料来源:韦翰,H。:高级R，第238页。
In general memoization in computer science means that you save the results of a function so that when you call it again with the same arguments it returns the saved value.
一般来说，计算机科学中的记忆化意味着你保存一个函数的结果，这样当你用相同的参数再次调用它时，它会返回保存的值。
#6
4
A recursive implementation with linear cost:
线性成本的递归实现:
fib3 <- function(n){
fib <- function(n, fibm1, fibm2){
if(n==1){return(fibm2)}
if(n==2){return(fibm1)}
if(n >2){
fib(n-1, fibm1+fibm2, fibm1)
}
}
fib(n, 1, 0)
}
Comparing with the recursive solution with exponential cost:
与指数代价递归解比较:
> system.time(fibonacci(35))
usuário sistema decorrido
14.629 0.017 14.644
> system.time(fib3(35))
usuário sistema decorrido
0.001 0.000 0.000
This solution can be vectorized with ifelse:
这个解决方案可以用ifelse向量化:
fib4 <- function(n){
fib <- function(n, fibm1, fibm2){
ifelse(n<=1, fibm2,
ifelse(n==2, fibm1,
Recall(n-1, fibm1+fibm2, fibm1)
))
}
fib(n, 1, 0)
}
fib4(1:30)
## [1] 0 1 1 2 3 5 8
## [8] 13 21 34 55 89 144 233
## [15] 377 610 987 1597 2584 4181 6765
## [22] 10946 17711 28657 46368 75025 121393 196418
## [29] 317811 514229
The only changes required are changing == to <= for the n==1 case, and changing each if block to the equivalent ifelse.
对于n== =1的情况，只需要更改== <= ==，并将每个if块更改为等效的ifelse。
#7
2
If you are truly looking to return Fibonacci numbers and aren't using this example to explore how recursion works then you can solve it non-recursively by using the following:
如果你真的想要返回斐波那契数，而不是用这个例子来探究递归是如何工作的，那么你可以用下面的方法来非递归地解决它:
fib = function(n) {round((1.61803398875^n+0.61803398875^n)/sqrt(5))}