Rcpp と PCRE で R での文字列抽出を 20 倍速くした

R で最も辛い処理の一つに文字列抽出が挙げられるでしょう。
「R言語上級ハンドブック」では regmatches, str_match_all, strapply などによる文字列抽出の方法を紹介しましたが、やはり他の言語と比べると辛いものがあります。1

というのも、R は何でもベクトル単位で処理することを前提としており、そうでないとめちゃくちゃ重くなるからです。
マッチするパターンに応じて処理を変えたい場合、パターン 1 にマッチしたやつのうち、2 箇所でマッチしたやつはこの処理、1 箇所でマッチしたやつはこの処理、マッチしなかったやつはパターン 2 の処理をして…、みたいなことを高速化するためにベクトル単位で処理すると読む気もしない鬼畜なコードになります。
また、正規表現をコンパイルした状態で保持する方法が(私の知る限り)ないのも問題です。

というわけで、普通の言語と同じように各文字列単位で処理しても高速に処理できるように Rcpp と PCRE を使って実装してみました。

Rcpp を使ったのはほぼ初めてなのと、C++ まともに書いたことないのでアドバイスもらえると嬉しいです!!

使い方

devtools を使って読み込むのが手軽で良いと思います。要 Rcpp、PCRE です。

> devtools::source_gist("https://gist.github.com/abicky/58ea79b01d9e394d5076")
Sourcing https://gist.githubusercontent.com/abicky/58ea79b01d9e394d5076/raw/83f9992f55235fe4f79423914b4546d3850a29c2/regex.R
SHA-1 hash of file is 1ac0bcd68cfe415b0c2f58126914cb59552ae0ea
> # まずは Regex インスタンスを生成
> regex <- Regex$new("foo(.\\w+)")
> # Regex#scan でマッチする文字列を抽出
> # リストの 1 つ目のベクトルが最初にマッチした内容で、ベクトルの 1 つ目がマッチした文字列全体、2 つ目がキャプチャグループ 1
> regex$scan("foobar foobaz")
[[1]]
[1] "foobar" "bar"   

[[2]]
[1] "foobaz" "baz"   

> # regexquote でメタ文字をエスケープできる
> regex <- Regex$new(regexquote("(^.^)"))
> regex$scan("(^o^) (^_^) (^.^)")
[[1]]
[1] "(^.^)"

ベンチマーク

regmatches はキャプチャグループに対応していないので、str_match_all と strapply と比較してみます。

# R 3.1.2
library(devtools)

library(rbenchmark)
library(gsubfn)  # gsubfn 0.6.6
library(stringr)   # stringr 0.6.2
source_gist("https://gist.github.com/abicky/58ea79b01d9e394d5076")

# 「R言語上級ハンドブック」に載ってる例とほぼ同じやつ
filename <- system.file("DESCRIPTION")
text <- paste(readLines(filename, n = 5), collapse = "\n")
pattern <- "((?::|\\w)+)\\s+R\\s+(\\w+)"

regex <- Regex$new(pattern)
benchmark(
    replications = 10000,
    regex = regex$scan(text),
    str_match_all = str_match_all(text, pattern),
    strapply = strapply(text, pattern, c, backref = 2, combine = list)
)

それぞれ次のような結果を返します。

> regex$scan(text)
[[1]]
[1] "The R Base" "The"        "Base"      

[[2]]
[1] "Author: R Core" "Author:"        "Core"          

> str_match_all(text, pattern)
[[1]]
     [,1]             [,2]      [,3]  
[1,] "The R Base"     "The"     "Base"
[2,] "Author: R Core" "Author:" "Core"

> strapply(text, pattern, c, backref = 2, combine = list)
[[1]]
[[1]][[1]]
[1] "The R Base" "The"        "Base"      

[[1]][[2]]
[1] "Author: R Core" "Author:"        "Core"          


結果

           test replications elapsed relative user.self sys.self user.child sys.child
1         regex        10000   0.432    1.000     0.413    0.015          0         0
2 str_match_all        10000   8.602   19.912     7.632    0.618          0         0
3      strapply        10000  11.733   27.160    10.282    0.637          0         0

約 20 倍速くなってますね!!
これで R を使う上でのストレスが 1 つ解消された気がします。

regmatches, str_match_all, strapply の使い方が気になった方は「R言語上級ハンドブック」を買ってください><

参考

追記

@kohske さんより次のようなコメントを頂いたので stringi::stri_match_all_regex も比較対象に入れてみました。

20150223010942

stringi の存在を初めて知ったんですが、archive の情報を見る限り 2014 年 3 月から提供されている割りと新しいパッケージみたいですね。

っで、結果ですが・・・

> benchmark(
+     replications = 10000,
+     regex = regex$scan(text),
+     str_match_all = str_match_all(text, pattern),
+     strapply = strapply(text, pattern, c, backref = 2, combine = list),
+     stri_match_all_regex = stri_match_all_regex(text, pattern)
+ )
                  test replications elapsed relative user.self sys.self user.child sys.child
1                regex        10000   0.446    1.000     0.423    0.020          0         0
2        str_match_all        10000   8.742   19.601     7.765    0.676          0         0
3             strapply        10000  10.938   24.525     9.834    0.611          0         0
4 stri_match_all_regex        10000   0.651    1.460     0.601    0.016          0         0

stringi、速いですね・・・。毎回正規表現をコンパイルしているはずなのにほとんど差がないです。R も捨てたもんじゃないですね!

ちなみに、繰り返し回数が 1,000 回だと何故かもうちょっと差が開きます。

> benchmark(
+     replications = 1000,
+     regex = regex$scan(text),
+     str_match_all = str_match_all(text, pattern),
+     strapply = strapply(text, pattern, c, backref = 2, combine = list),
+     stri_match_all_regex = stri_match_all_regex(text, pattern)
+ )
                  test replications elapsed relative user.self sys.self user.child sys.child
1                regex         1000   0.027    1.000     0.025    0.002          0         0
2        str_match_all         1000   0.820   30.370     0.734    0.061          0         0
3             strapply         1000   1.038   38.444     0.936    0.067          0         0
4 stri_match_all_regex         1000   0.064    2.370     0.063    0.002          0         0
  1. じゃあ文字列処理は他の言語を使えばいいかというと、そのためだけにいちいち R で処理した結果を別の言語に食わせてその結果を R で読み込むとか面倒じゃないですか。