2015-02-22
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言語上級ハンドブック」を買ってください＞＜
参考
- pcrecpp specification
- Rcpp Attributes (PDF)
- Rcpp Masterclass / Workshop Part III: Rcpp Modules
- Rcppのすすめ
- Tokyo.R 白熱教室「これからのRcppの話をしよう」
追記
@kohske さんより次のようなコメントを頂いたので stringi::stri_match_all_regex も比較対象に入れてみました。
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