Rでフィボナッチ数! http://d.hatena.ne.jp/mickey24/20080914/1221334119
syou6162先生が一行でやってくれました http://d.hatena.ne.jp/mickey24/20080914/1221334177
Rでフィボナッチ数!(動的計画法版) http://d.hatena.ne.jp/mickey24/20080914/1221336203
再帰関数として書いたもの これは,おそい
fib1 <- function(n) {
if (n == 0) { return(0) }
if (n == 1) { return(1) }
fib1(n-1) + fib1(n-2)
}
一行野郎で書いたもの これは,作者は心外だろうが,大変大変遅い
なぜおそいかというと,それは,ifelse を使っているから
ifelse は,条件によらず二通りの計算をして,条件によりどちらかを選ぶ だから,とってもとっても遅い
fib2 <- function(n) {
ifelse (n > 1, Recall(n-1) + Recall(n-2), ifelse(n == 1, 1, 0))
}
同じ一行にするのでも,if else を使えば func1 と基本的に同じなのだから,ifelse ほど遅くはない
fib3 <- function(n) {
if (n > 1) Recall(n-1) + Recall(n-2) else if (n == 1) 1 else 0
}
動的計画法版のプログラムだが,ベクトルを使う必要は余り感じられない
fib4 <- function(n) {
if (n == 0) { return(0) }
x <- numeric(max(n,2))
x[1] <- x[2] <- 1
m <- 3
while (m <= n) {
x[m] <- x[m-1] + x[m-2]
m <- m + 1
}
x[n]
}
普通の変数を使って書けば,最速!!
fib5 <- function(n) {
if (n == 0) return(0)
if (n == 1) return(1)
a <- 0
b <- 1
for (i in 2:n) {
c <- a + b
if (i == n) return(c)
a <- b
b <- c
}
}
> n <- 15
> benchmark(fib1(n), fib2(n), fib3(n), fib4(n), fib5(n),
+ columns=c("test", "elapsed", "relative", "replications"),
+ replications=200)
test elapsed relative replications
1 fib1(n) 0.751 125.166667 200
2 fib2(n) 6.229 1038.166667 200
3 fib3(n) 0.803 133.833333 200
4 fib4(n) 0.014 2.333333 200
5 fib5(n) 0.006 1.000000 200
最新の画像[もっと見る]
- 算額(その2135) 10時間前
- 算額(その2134) 17時間前
- 算額(その2133) 1日前
- 算額(その2132) 3日前
- 算額(その2131) 4日前
- 算額(その2130) 4日前
- 算額(その2129) 5日前
- 算額(その2128) 5日前
- 算額(その2127) 6日前
- 算額(その2126) 6日前
※コメント投稿者のブログIDはブログ作成者のみに通知されます