R
正規表現

Rでは量指定子を変えても正規表現の実行速度にほとんど影響しない

はじめに

pythonでは

【メモ】量指定子を変えると正規表現の実行速度が桁で変わる(仮)

という話があるので、Rでも試してみた。

  • +{1, }
  • *{0, }
  • ?{0, 1}

を比較する。

結果としてはbase::grepstringr::str_detectも大差ないか、{m, n}で指定する方が若干遅い。

残念。

実験開始

準備

require(stringr)
require(microbenchmark)
require(knitr)

x <- 'bbbbbbbbbbbbbbbbbb'

base::grepの場合

kable(summary(microbenchmark(
  grep('b+', x),
  grep('b{1,}', x),
  grep('b*', x),
  grep('b{0,}', x),
  grep('b?', x),
  grep('b{0,1}', x)
)))
expr min lq mean median uq max neval
grep("b+", x) 4.790 5.4740 8.80653 5.4750 9.5795 67.057 100
grep("b{1,}", x) 4.790 5.4740 7.33539 5.8165 10.2640 14.369 100
grep("b*", x) 5.474 5.4740 7.52007 6.1580 7.1850 34.213 100
grep("b{0,}", x) 5.474 5.4745 9.04599 6.1580 10.2640 116.322 100
grep("b?", x) 4.790 5.4740 8.36862 6.1580 10.2640 56.109 100
grep("b{0,1}", x) 5.474 5.4740 9.29229 6.1580 6.8430 95.110 100

stringr::str_detectの場合

kable(summary(microbenchmark(
  str_detect(x, 'b+'),
  str_detect(x, 'b{1,}'),
  str_detect(x, 'b*'),
  str_detect(x, 'b{0,}'),
  str_detect(x, 'b?'),
  str_detect(x, 'b{0,1}')
)))
expr min lq mean median uq max neval
str_detect(x, "b+") 34.212 36.2650 51.34606 37.6340 60.5560 216.222 100
str_detect(x, "b{1,}") 35.581 37.6340 51.42818 39.6870 64.6615 172.430 100
str_detect(x, "b*") 34.896 36.2655 53.82303 39.3445 63.9770 169.693 100
str_detect(x, "b{0,}") 35.581 37.6340 54.09672 46.1875 66.3725 110.164 100
str_detect(x, "b?") 33.528 34.8970 54.08311 41.7390 59.8715 460.498 100
str_detect(x, "b{0,1}") 34.212 35.5810 59.48179 52.0030 59.1875 632.243 100

感想

  • {m, n}の方が、明示的で分かりよいと思う
  • grepの方が速いのは意外だった