Rでfor文は使うべきでないか？ (R Advent Calendar 2011)

R

この記事はR Advent Calendar 2011 (http://atnd.org/events/22039)への参加記事です。


Rではよく「for文は使うべきでない」と言われます。forではなく、ベクトル単位での処理として記述したり、lapplyやapplyなどのベクトル・行列に対するmap系関数を使うべきとされています。しかし実際には、必ずしもいつもfor文を避ければ良いというものでも無いようです。今回はそのあたり、for文がどのくらい遅いのか(または遅くないのか)を調べてみたいと思います。

lapply関数

通常、for文と対応関係にあるのはlapply関数です。lapplyは

lapply(v,func)

という形で用いられ、その機能は

  • 第一引数のベクトルvの各要素にfuncを適用する
  • 各要素への適用結果をリストにまとめて返す

というものです。
for文で書ける処理はlapplyでも書くことができ、以下のようになります。

for(i in 1:n){
  func(i) #なんらかの処理
}

lapply(1:n,func)

以下ではforとlapplyの速度が、使用ケースによってどのように異なるかを見ていきます。

もったいぶってもあれですので、ネタバレすると次のような構成で話をします。

  • 何もしないforループとlapplyの関係
    • forループとは異なり、lapplyは「何もしない」場合でも関数呼び出しが必要であり、その分forよりも大分遅くなります。
    • forにも同等の関数呼び出しが含まれる場合は、lapplyの方がわずかに速くなります。
  • リストを返すループ
    • lapplyではループ処理を行った結果をリストに格納して返します。結果を捨てるようなforループと比較するとlapplyは遅くなります。
    • 一方、for文で同様のリスト生成を行おうとするとlapplyに比べ圧倒的に低速となります。
  • ベクトル演算とforループ
    • R組み込みのベクトル関数の処理をforループで実現しようとすると圧倒的に低速となります。これは、lapplyの場合と同じく、処理がどこまでC言語実装に含まれているかの問題です。

結論として、「可能な限りC言語実装の関数を使うべき」であり、「無駄な処理の含まれるC言語実装関数は無理に使うべきでない」となります。

テスト関数

テストのため以下のような関数を用意しています。テスト対象の関数funcとテストケースcasesを渡すことで処理時間を測定します。

tester <- function(func,cases){
  results <- c()
  results.names <- c("user","system","elapsed")
  for(case in cases){
    result <- system.time(func(case))
    results <- c(results,result[1:3])
  }
  results <- matrix(results,ncol=3,byrow=T)
  colnames(results) <- results.names
  return(results)
}

何もしないforループとlapply

まずは何もしないforとlapplyについて比較してみます。

cases <- list(1:10^7,1:(2*10^7),1:(3*10^7))

test.lfor.null <- function(v){
  for(i in v){}
}

empty.func <- function(x){}
test.lapply.empty <- function(v){
  lapply(v,empty.func)
}

テスト結果は次のようになります。

> test.lfor.null.result
      user system elapsed
[1,] 0.095      0   0.095
[2,] 0.188      0   0.189
[3,] 0.284      0   0.284

> test.lapply.empty.result
      user system elapsed
[1,] 0.371  0.004   0.375
[2,] 0.740  0.006   0.746
[3,] 1.118  0.003   1.121

for文の方が４倍程度速いという結果になりました。これはlapplyでは処理を関数に包む必要があり、必ず関数呼び出しのコストがかかるためです。実際、for文の方にも関数呼び出しのコストを乗せると

test.lfor.empty <- function(v){
  for(i in v){
    empty.func(i)
  }
}

> test.lfor.empty.result
      user system elapsed
[1,] 0.500  0.002   0.502
[2,] 0.984  0.007   0.992
[3,] 1.470  0.007   1.478

となり、lapplyの方が1.3倍程度速くなります。
従って

  • 関数に包む必要のない処理についてのループでは、for文を使う方が良い

と言えそうです。

何かするforループとlapply

次に、ループ内で何らかの処理をする場合の速度を比較してみます。
ここでは、単純に足し算を行うだけの処理とします。

cases <- list(1:10^7,1:(2*10^7),1:(3*10^7))
plus1.func <- function(x){1+1}

test.lfor.plus1 <- function(v){
  for(i in v){
    plus1.func(i)
  }
}

test.lapply.plus1 <- function(v){
  lapply(v,plus1.func)
}

> test.lfor.plus1.result
       user system elapsed
[1,]  8.806  0.416   9.224
[2,] 15.874  0.017  15.898
[3,] 24.569  0.251  24.829

> test.lapply.plus1.result
       user system elapsed
[1,] 13.626  0.204  13.835
[2,] 30.235  0.519  30.765
[3,] 40.767  3.523  55.877

今度はlapplyの方がかなり遅くなりました。これはlapplyの「結果をリストとして返す」機能のせいだと考えられます。forでは足し算の結果をその都度捨てていますが、lapplyでは逐一リストに追加し、結果として返す操作が加わっています。
for文を使って明示的にリストを生成してみるとどうなるかというと

cases.small <- list(1:10^4,1:(2*10^4),1:(3*10^4))

test.lfor.plus1.list <- function(v){
  result <- list()
  for(i in v){
    result <- c(result,1+1)
  }
  return(result)
}

> test.lfor.plus1.list.result
       user system elapsed
[1,]  2.678  0.090   2.774
[2,] 11.673  0.837  12.558
[3,] 25.148  1.882  27.042

これまで使っていたcasesでは時間がかかりすぎるため、小さいケースで実行しました。ループ数が3桁小さいにも関わらず、lapplyの場合の半分程度の時間がかかっています。すなわち、lapplyで行ったリスト生成と、Rで明示的に記述したリスト生成とでは数百倍程度の速度差があるということが分かりました。
lapplyはRの組み込み関数でありその実装はC言語です。リストの生成操作もC内部で行われており、この部分がpure Rでのリストを返す関数との決定的な速度差を生んでいると考えられます。

  • リストを生成するような処理は可能な限りlapplyで行うべき

と言えます。

ベクトル演算とforループ

最後に、より基本的なテクニックとしてベクトル演算とforループの比較をしてみます。

vs <- list(1:10^7,1:(2*10^7),1:(3*10^7))

test.vfor <- function(v){
  for(i in v){
    i + 1
  }
}

test.vector <- function(v){
  v + 1
}

> test.vfor.result
       user system elapsed
[1,]  4.391  0.050   4.441
[2,]  8.698  0.030   8.727
[3,] 12.863  0.015  12.879

> test.vector.result
      user system elapsed
[1,] 0.032  0.000   0.032
[2,] 0.079  0.043   0.122
[3,] 0.117  0.065   0.182

これは(当然ながら)組み込みのベクトル演算を利用した方が圧倒的に高速です。lapplyの場合と同じように、ループ処理がC言語実装の内部に含まれているためです。

結論

以上の比較から、「Rではfor文を使うべきではない」という説については

  • ループ内の処理を関数に包む必要がない場合はfor文の方が良い
  • リスト生成の必要がないループについてはfor文の方が良い
  • リスト生成、ベクトル演算など、組み込みのループ処理を利用できる場合はそれを用いた方が良い

と言えるだろうと考えられます。結局いかにCで実装された関数を利用できるかという問題ですが、C実装の関数も完璧ではなく、場合によっては不要な処理が含まれていたり、データ構造を上手く処理できない場合などもあります。基本的な特性を押さえつつ、ケースバイケースで使い分ける必要があると言えそうです。

多次元の場合

（Rで多次元ループを書く機会はそれほど多くない気もしますが）多次元の場合も基本的には同じで、いかに組み込みのC実装関数を使うかがポイントとなります。詳しくは下記の参考文献(Chapter 14)を参照して頂きたいのですが、特に注意すべき点として

  • applyはC実装ではなくR上での実装である

という点があります。行列型に整形したデータについてapplyを使えば自動的に速くなるというわけではなく、いかにベクトル演算を使うかという点に注意してコーディングする必要があります。

追記

for文でlistを生成するところについて、yatsutaさんからコメントを頂きました。forの方ではループコストの差異に加えlistの領域を確保するコストが上乗せされている、というものです。これを考慮するには、forで逐次的にリストを大きくしていくのではなく、予め必要なサイズを確保しておいた上で要素のセットにforループを使う必要があります。
実行してみると下記のようになります。

vs <- list(1:10^7,1:(2*10^7),1:(3*10^7))

test.lfor.plus1.list2 <- function(v){
  result <- vector("list",length(v))
  for(i in v){
    result[[i]] <- 1+1
  }
}

> test.lfor.plus1.list2.result
       user system elapsed
[1,] 37.215  0.287  37.503
[2,] 61.647  1.017  63.459
[3,] 90.967  3.785 102.298

元のサイズのテストケースで実行することができ、速度はlapplyの場合の1/2程度となりました。逐次的にlistを拡大していったケースのコストは、ほぼ全てがlistのための領域確保コストであったことになります。
領域確保コストを除いてもforの方が2倍程度遅いということになりましたが、この原因は「ループそのもの」と「代入」による速度差を合わせたものとなります。これらを個別に見るのは、ループまたは代入のみをC実装で行うような関数が(おそらく)Rには無いため、中々難しいかと思います。とはいえ、両方合わせてこのくらいの差があると把握しておけば実用上は十分そうです。

参考文献

プログラミング的な側面からRを解説した資料はあまり多くありませんが、最近出た以下の本は、おそらく本としては最もこの手の話題について詳しいのではないかと思います。Rコードの書き方と速度の関係についても1章割かれています。

The Art of R Programming: A Tour of Statistical Software Design

The Art of R Programming: A Tour of Statistical Software Design