R 속도비교: loop, apply, vectorization

이 실험은 R version 2.14.0 (2011-10-31)에서 이루어진 것이다.

R version 2.14.0 (2011-10-31)
Copyright (C) 2011 The R Foundation for Statistical Computing
ISBN 3-900051-07-0
Platform: x86_64-apple-darwin9.8.0/x86_64 (64-bit)

컴퓨터는 iMac 3.06GHz Intel Core 2 Duo, 메모리는 12GB 1067 MHz DDR3. 운영체제는 Mac OS X Lion 10.7.2이다.

loop를 돌릴 때

우선, 결과값을 저장할 벡터를 미리 크기를 정해서 만들어 놓는 것과 아닌 것에는 엄청난 차이가 난다.

> x <- 1:(10^5)
> y <- c()
> system.time(for(i in 1:length(x)) y[i] <- x[i]^2)
   user  system elapsed 
 13.054  33.554  65.792
> y <- numeric(length(x))
> system.time(for(i in 1:length(x)) y[i] <- x[i]^2)
   user  system elapsed 
  0.312   0.008   0.455 

loop를 돌리며 결과를 벡터에 저장하려고 할 때는 반드시 해당 벡터를 먼저 초기화해야 한다.

loop, apply, vectorization

이제 계산할 벡터의 크기를 10배 늘려서 loop, apply, vectorization을 비교해 보자. apply 함수를 사용할 때는 결과값이 저장될 벡터를 미리 초기화할 필요가 없다. vectorization의 속도가 엄청나게 빠른 것을 확인할 수 있다.

> x <- 1:(10^6)
> y <- numeric(length(x))
> system.time(for(i in 1:length(x)) y[i] <- x[i]^2)
   user  system elapsed 
  3.019   0.045   4.533 
> rm(y)
> system.time(y <- sapply(x, function(i) i^2))
   user  system elapsed 
  3.248   0.071   4.605 
> rm(y)
> system.time(y <- x^2)
   user  system elapsed 
  0.006   0.000   0.006 

흔히 for loop보다 apply()가 "훨씬" 빠르다고 이야기하는 경우가 있는데 그건 사실이 아니다. 혹시 S-Plus에서는 그렇다는 말이 있는데 사실인지 모르겠다. R에서는 루프도 apply만큼 빠르다. 단 결과를 저장할 벡터를 초기화하는 것을 잊어서는 안 된다. 둘의 속도 차이는 경우에 따라 없을 수도 있고 루프가 빠를 수도 있고 apply가 빠를 수도 있다. 물론, apply()를 쓰는 것이 코드가 더 깔끔하다.

Vectorization의 엄청난 속도

경우에 따라 다르겠지만 원소들의 제곱으로 이루어진 벡터를 만드는 바로 이 문제의 경우, 루프나 apply와 비교했을 때 vectoriation이 500배 이상 빠른 속도를 보이는 것을 확인할 수 있다. 벡터의 크기를 늘려가며 vectorization을 해 보았다. 1천만(10^8)개까지는 큰 문제가 없이 산술적으로 속도가 증가한다. 1억개(10^9)부터는 연산에 걸린 시간은 정상적으로 증가했지만 elapsed가 갑자기 시간이 오래 걸렸는데 메모리 부족 문제인 듯하다.

> x <- 1:(10^6)
> system.time(y <- x^2)
   user  system elapsed 
  0.005   0.000   0.005 
> x <- 1:(10^7)
> system.time(y <- x^2)
   user  system elapsed 
  0.059   0.001   0.065 
> x <- 1:(10^8)
> system.time(y <- x^2)
   user  system elapsed 
  0.575   0.509   1.246 
> x <- 1:(10^9)
> system.time(y <- x^2)
   user  system elapsed 
  6.266   8.735 155.847 
> x <- 1:(10^10)
이하에 에러1:(10^10) : 결과의 벡터가 너무 깁니다

마지막 에러가 난 것은 벡터의 크기가 너무 크기 때문이다. R에서 허용하는 벡터의 최대 크기는 2^31 - 1, 약 2*10^9이다.

matrix, array의 경우: rowSums(), colSums() 사용하기

vectoriation을 모든 경우에 할 수 있는 것은 아니다. 행렬(matrix)이나 배열(array)에서 행이나 열의 합을 구하는 경우에 루프나 apply보다는 rowSums(), colSums()를 쓰는 것이 빠르다.

> x <- matrix(runif(10^8), ncol=10^4)
> str(x)
 num [1:10000, 1:10000] 0.3492 0.0621 0.2593 0.8765 0.5281 ...
> y <- numeric(10000)
> system.time(for(i in 1:10000) y[i] <- sum(x[i,]))
   user  system elapsed 
  6.836   0.755   9.653 
> rm(y)
> system.time(y <- apply(x, 1, sum))
   user  system elapsed 
  6.597   1.512  10.263 
> rm(y)
> system.time(y <- rowSums(x))
   user  system elapsed 
  0.263   0.003   0.326 

list의 경우: lapply()

list는 vector가 아니라 list이니까 Vectorizatioin하다는 것은 이름 그대로 말이 안 되지 않는가? 루프나 apply를 써야 하는데, list를 대상으로 할 때는 루프보다 lapply()의 코드가 효율적이라고 알려져 있고 실제로도 조금 빠른 것 같다.

> x <- list()
> for(i in 1:10000) x[[i]] <- runif(10000)
> y <- numeric(10000)
> system.time(for(i in 1:10000) y[i] <- sum(x[[i]]))
   user  system elapsed 
  0.257   0.004   0.390 
> system.time(y <- lapply(x, sum))
   user  system elapsed 
  0.228   0.005   0.281 

약간 다르게:

> x <- list()
> for(i in 1:100000) x[[i]] <- runif(10)
> y <- numeric(100000)
> system.time(for(i in 1:100000) y[i] <- sum(x[[i]]))
   user  system elapsed 
  0.393   0.007   0.543 
> system.time(y <- lapply(x, sum))
   user  system elapsed 
  0.147   0.003   0.229 

누적 계산이 필요한 경우

> x <- runif(1000000)
> system.time(y <- cumsum(x))
   user  system elapsed 
  0.032   0.006   0.102 
> system.time({y[1] <- x[1]; for(i in 2:length(x)) y[i] <- y[i-1] + x[i]})
   user  system elapsed 
  4.140   0.029   4.330