2008/06/23

なぜ速くなったのか?

Rprof()を使って調べてみる。結論から言うとマトリックスをつくるところで遅いわけではないようだ。
<<<
my.prof <- function(x) {
Rprof()
x
Rprof(NULL)
print( summaryRprof() )
}

my.prof( montecarlo(100000) )
my.prof( montecarlo_vec(100000) )
my.prof( montecarlo_vec2(100000) )
my.prof( montecarlo_vec3(100000) )
>>>
まずは for() バージョン
<<<
by.self
self.time self.pct total.time total.pct
"runif" 0.80 57.1 0.80 57.1
"montecarlo" 0.54 38.6 1.40 100.0
"+" 0.04 2.9 0.04 2.9
"<" 0.02 1.4 0.02 1.4
"my.prof" 0.00 0.0 1.40 100.0
>>>
四則演算やrunifが for() で繰り返されているのでそのぶん遅くなっている。

次は replicate バージョン
<<<
$by.self
self.time self.pct total.time total.pct
"runif" 0.90 60.0 0.90 60.0
"FUN" 0.26 17.3 1.26 84.0
"lapply" 0.22 14.7 1.48 98.7
"^" 0.06 4.0 0.06 4.0
"sum" 0.04 2.7 0.04 2.7
"unlist" 0.02 1.3 0.24 16.0
"montecarlo_vec" 0.00 0.0 1.50 100.0
"my.prof" 0.00 0.0 1.50 100.0
"replicate" 0.00 0.0 1.50 100.0
"sapply" 0.00 0.0 1.50 100.0
"unique" 0.00 0.0 0.22 14.7
>>>
unlistやlapplyが出てきている。replicate は sapply とほとんど同じ。sapply = lapply + unlist っぽいのでそこがボトルネックになっているのだろう。ここはあとでソース確認したいが、どうやってみるんだっけ? さらに runifが繰り返されているので遅くなる。

乱数のマトリックスを先に作っておくバージョン
<<<
$by.self
self.time self.pct total.time total.pct
"runif" 0.04 50 0.04 50
"montecarlo_vec2" 0.02 25 0.08 100
"+" 0.02 25 0.02 25
"my.prof" 0.00 0 0.08 100
"as.vector" 0.00 0 0.04 50
"matrix" 0.00 0 0.04 50
>>>
runifの繰り返しがなくなったので速くなっている。

乱数のベクターを2つ用意しておくバージョンを見てみる。
<<<
$by.self
self.time self.pct total.time total.pct
"^" 0.02 50 0.02 50
"runif" 0.02 50 0.02 50
"montecarlo_vec3" 0.00 0 0.04 100
"my.prof" 0.00 0 0.04 100
>>>
一見、2回 runif したほうが matrix をつくるよりもましに見える。ところが良くわからないのが、マトリックスをつくる部分が遅いのか、それとも添字でカラムを取り出しているところが遅いのか? というところ。 まずはマトリックス作成が遅いのか調べてみよう。
<<<
> vec <- function(n) {
+ x <- runif(n)
+ y <- runif(n)
+ }
>
> mat1 <- function(n) {
+ x <- runif(n*2)
+ }
>
> mat2 <- function(n) {
+ x <- matrix(runif(n*2), ncol=2)
+ }
>
> mat3 <- function(n) {
+ x <- runif(n*2)
+ y <- matrix(x, ncol=2)
+ }
>
> my.prof <- function(x) {
+ Rprof()
+ x
+ Rprof(NULL)
+ print( summaryRprof() )
+ }
>
> my.prof( vec(1000000) )
$by.self
self.time self.pct total.time total.pct
"runif" 0.22 100 0.22 100
"my.prof" 0.00 0 0.22 100
"vec" 0.00 0 0.22 100

$by.total
total.time total.pct self.time self.pct
"runif" 0.22 100 0.22 100
"my.prof" 0.22 100 0.00 0
"vec" 0.22 100 0.00 0

$sampling.time
[1] 0.22

> my.prof( mat1(1000000) )
$by.self
self.time self.pct total.time total.pct
"runif" 0.2 100 0.2 100
"mat1" 0.0 0 0.2 100
"my.prof" 0.0 0 0.2 100

$by.total
total.time total.pct self.time self.pct
"runif" 0.2 100 0.2 100
"mat1" 0.2 100 0.0 0
"my.prof" 0.2 100 0.0 0

$sampling.time
[1] 0.2

> my.prof( mat2(1000000) )
$by.self
self.time self.pct total.time total.pct
"runif" 0.20 66.7 0.20 66.7
"matrix" 0.06 20.0 0.30 100.0
"as.vector" 0.04 13.3 0.24 80.0
"mat2" 0.00 0.0 0.30 100.0
"my.prof" 0.00 0.0 0.30 100.0

$by.total
total.time total.pct self.time self.pct
"matrix" 0.30 100.0 0.06 20.0
"mat2" 0.30 100.0 0.00 0.0
"my.prof" 0.30 100.0 0.00 0.0
"as.vector" 0.24 80.0 0.04 13.3
"runif" 0.20 66.7 0.20 66.7

$sampling.time
[1] 0.3

> my.prof( mat3(1000000) )
$by.self
self.time self.pct total.time total.pct
"runif" 0.20 76.9 0.20 76.9
"matrix" 0.04 15.4 0.06 23.1
"as.vector" 0.02 7.7 0.02 7.7
"mat3" 0.00 0.0 0.26 100.0
"my.prof" 0.00 0.0 0.26 100.0

$by.total
total.time total.pct self.time self.pct
"mat3" 0.26 100.0 0.00 0.0
"my.prof" 0.26 100.0 0.00 0.0
"runif" 0.20 76.9 0.20 76.9
"matrix" 0.06 23.1 0.04 15.4
"as.vector" 0.02 7.7 0.02 7.7

$sampling.time
[1] 0.26
>>>
あれ? matrixのほうが速い? これは添字でカラムを取り出しているところが遅いに違いない。
<<<
vec <- function(n) {
x <- runif(n)
y <- runif(n)
x^2
}

mat1 <- function(n) {
x <- matrix(runif(n*2), ncol=2)
x[1,]^2
}

> my.prof( vec(1000000) )
$by.self
self.time self.pct total.time total.pct
"runif" 0.22 78.6 0.22 78.6
"^" 0.06 21.4 0.06 21.4
"my.prof" 0.00 0.0 0.28 100.0
"vec" 0.00 0.0 0.28 100.0

$by.total
total.time total.pct self.time self.pct
"my.prof" 0.28 100.0 0.00 0.0
"vec" 0.28 100.0 0.00 0.0
"runif" 0.22 78.6 0.22 78.6
"^" 0.06 21.4 0.06 21.4

$sampling.time
[1] 0.28

> my.prof( mat1(1000000) )
$by.self
self.time self.pct total.time total.pct
"runif" 0.20 66.7 0.20 66.7
"matrix" 0.06 20.0 0.30 100.0
"as.vector" 0.04 13.3 0.24 80.0
"mat1" 0.00 0.0 0.30 100.0
"my.prof" 0.00 0.0 0.30 100.0

$by.total
total.time total.pct self.time self.pct
"matrix" 0.30 100.0 0.06 20.0
"mat1" 0.30 100.0 0.00 0.0
"my.prof" 0.30 100.0 0.00 0.0
"as.vector" 0.24 80.0 0.04 13.3
"runif" 0.20 66.7 0.20 66.7

$sampling.time
[1] 0.3
>>>
as.vectorの部分が遅くなっている。原因はこれか。ということは列和をベクトル演算する関数colSums()使えば速くなるかも! colSums忘れてたorz... しかも2乗もベクトル演算しちゃうよ。
<<<
montecarlo_vec4 <- function(n) {
y <- matrix(runif(n*2),nrow=2)
4*sum(colSums(y^2) < 1)/n
}

[1] 1.4855 # for
[1] 1.5224 # replicate
[1] 0.0482 # matrix
[1] 0.0138 # vector
[1] 0.0379 # matrix + colSums
>>>
くっ、届かないか。Rprofしてみるとas.vectorが縮まってない >< 単純に足し算は速くなったという感じ。

結論: マトリックスにカラムごとにアクセスするぐらいなら、2つのベクターを使ったほうが良い。colSumsとかでも追いつかない><